题面
题解
现场得分：50/100
注意点：压位高精度输出一定要弄好，不要缺少前导零。
- 把这个平面图，抽象成类似一个等高线地形图的东西，每一个圈就代表一个节点（方便起见，从这个块里面最高的节点当中任意指定一个作为代表），然后你就得到了一个树形结构。
- 于是你发现可以用排序之后并查集的套路来维护这样一个过程。这就很自然。
- 然后对于一个块，你会发现只考虑这一个块的方案数是他的所有儿子的方案数乘起来再加上他到他的父亲的距离。
- 就可以直接抽象出来之后，树形dp了事。
- 但是你还发现这个答案太大了，你就要用高精度。
- 但是我不知道什么高精度快，所以写了一个不熟练的压位任意模数。然后就只写了这一道题。
代码
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define MAXN 111
using namespace std;
template<typename T>void Read(T &cn)
{
char c;int sig = 1;
while(!isdigit(c = getchar()))if(c == '-')sig = -1; cn = c-48;
while(isdigit(c = getchar()))cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T>void Write_f(T cn, int cf)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10; cf--;
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(cf > wei) putchar('0'), cf--;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
LL ksm(LL cn, LL cm, LL MOD) {LL ans = 1; while(cm) ans = ans * (1+(cn-1)*(cm&1))%MOD, cn = cn*cn%MOD, cm>>=1; return ans; }
namespace Num{
const int MAXNUM = 1000000;
const int MAXNTT = MAXNUM*4+1;
const int MAXGE = MAXN*MAXN+1;
const int MOD1 = 998244353, MOD2 = 469762049, MOD3 = 645922817;
const LL MOD4 = 9284603221569121;
const int YG = 3;
const int FG = 100000;
struct num {int l,r; };
LL N[MAXNUM+1];
num a[MAXGE];
int alen, nlen;
LL A[MAXNTT], B[MAXNTT], yA[MAXNTT], yB[MAXNTT];
LL C1[MAXNTT], C2[MAXNTT], C3[MAXNTT];
int n,m,Mn;
int fan[MAXNTT], omg[MAXNTT], inv[MAXNTT];
void nong(int cn, int cm, LL A[], int &n) {n = -1; for(int i = cn;i<=cm;i++) A[++n] = N[i], N[i] = 0; }
int erwei(int cn) {int guo = 0; while(cn) guo++, cn>>=1; return guo; }
LL Crt(LL a1,LL p1,LL a2,LL p2,LL a3,LL p3,LL p,LL lin1,LL lin2)
{
LL a4 = ((a2%p2 - a1%p2 + p2)%p2 * lin1%p2 * p1 + a1)%(p1*p2);
LL a5 = ((a3%p3 - a4%p3 + p3)%p3 * lin2%p3%p*p1%p*p2%p + a4%p)%p;
return a5;
}
void yuchu(int cn, int MOD)
{
omg[0] = inv[0] = 1;
omg[1] = ksm(YG, MOD/cn, MOD); inv[1] = ksm(omg[1], MOD-2, MOD);
for(int i = 2;i<cn;i++) omg[i] = 1ll*omg[i-1]*omg[1]%MOD, inv[i] = 1ll*inv[i-1]*inv[1]%MOD;
fan[0] = 0; int lin = erwei(cn)-2;
for(int i = 1;i<cn;i++) fan[i] = (fan[i>>1]>>1) | ((i&1)<<lin);
}
void do_ntt(LL a[], int n, int omg[], int MOD)
{
for(int i = 0;i<n;i++) if(fan[i] > i) swap(a[fan[i]], a[i]);
for(int i = 2, m = 1;i<=n;i = (m = i)<<1)
for(int j = 0;j<n;j+=i)
for(int k = 0;k<m;k++)
{
LL lin1 = a[j+k], lin2 = 1ll*a[j+k+m]*omg[n/i*k]%MOD;
if(lin1 + lin2 >= MOD) a[j+k] = lin1+lin2-MOD; else a[j+k] = lin1+lin2;
if(lin1 < lin2) a[j+k+m] = lin1-lin2+MOD; else a[j+k+m] = lin1-lin2;
}
}
void ntt1(int MOD)
{
yuchu(Mn,MOD); do_ntt(A,Mn,omg,MOD); do_ntt(B,Mn,omg,MOD);
for(int i = 0;i<Mn;i++) A[i] = 1ll*A[i] * B[i]%MOD;
do_ntt(A,Mn,inv,MOD); LL lin = ksm(Mn,MOD-2,MOD);
for(int i = 0;i<Mn;i++) A[i] = 1ll*A[i]*lin%MOD;
}
void ntt()
{
Mn = 1<<(erwei(n+m));
if(1ll*n*m <= 1ll*Mn*erwei(Mn)*3) {
for(int i = 0;i<=n+m;i++) C1[i] = 0;
for(int i = 0;i<=n;i++) for(int j = 0;j<=m;j++) C1[i+j] = C1[i+j] + 1ll*A[i]*B[j];
for(int i = 0;i<=n+m;i++) A[i] = C1[i]; n = n+m;
return;
}
for(int i = n+1;i<Mn;i++) A[i] = 0;
for(int i = m+1;i<Mn;i++) B[i] = 0;
n = n+m;
for(int i = 0;i<Mn;i++) yA[i] = A[i], yB[i] = B[i];
for(int i = 0;i<Mn;i++) A[i] = yA[i], B[i] = yB[i]; ntt1(MOD1); for(int i = 0;i<Mn;i++) C1[i] = A[i];
for(int i = 0;i<Mn;i++) A[i] = yA[i], B[i] = yB[i]; ntt1(MOD2); for(int i = 0;i<Mn;i++) C2[i] = A[i];
for(int i = 0;i<Mn;i++) A[i] = yA[i], B[i] = yB[i]; ntt1(MOD3); for(int i = 0;i<Mn;i++) C3[i] = A[i];
LL lin1 = ksm(MOD1%MOD2,MOD2-2,MOD2);
LL lin2 = ksm(1ll*MOD1*MOD2%MOD3,MOD3-2,MOD3);
for(int i = 0;i<=n;i++) A[i] = Crt(C1[i],MOD1,C2[i],MOD2,C3[i],MOD3,MOD4,lin1,lin2);
}
void build() {alen = nlen = 0; a[0].r = a[0].l = 0; }
void set() {++alen; N[++nlen] = 1; a[alen].l = a[alen].r = nlen; }
void jinwei()
{
for(int i = a[alen].l;i<=a[alen].r;i++) N[i+1] += N[i]/FG, N[i] %= FG;
while(N[nlen+1] > 0) nlen++, N[nlen+1]+=N[nlen]/FG, N[nlen]%=FG;
a[alen].r = nlen;
}
void zeng(int cm)
{
int xian = a[alen].l;
while(cm) N[xian] = N[xian] + cm%FG, cm/=FG, xian++;
jinwei();
}
void cheng()
{
nong(a[alen-1].l, a[alen-1].r, A, n); nong(a[alen].l, a[alen].r, B, m);
ntt();
alen--; nlen = a[alen-1].r;
for(int i = 0;i<=n;i++) N[++nlen] = A[i];
a[alen].l = a[alen-1].r+1; a[alen].r = nlen;
jinwei();
}
void outit() {Write(N[nlen]); for(int i = nlen-1;i>=1;i--) Write_f(N[i],5); puts(""); }
};
struct qwe{
int a,b,ne;
void mk(int cn, int cm, int cx) {a = cn; b = cm; ne = cx; }
};
qwe a[MAXN*MAXN+1];
int alen;
int head[MAXN*MAXN+1];
struct qwer{
int x,y;
int zhi;
void mk(int cn, int cm, int cx) {x = cn; y = cm; zhi = cx; }
inline friend bool operator <(qwer a, qwer b) {return a.zhi < b.zhi; }
};
int n,m;
int yuan[MAXN+1][MAXN+1];
int fa[MAXN*MAXN+1];
qwer xu[MAXN*MAXN+1];
int zhi[MAXN*MAXN+1];
void lian(int cn, int cm) {a[++alen].mk(cn,cm,head[cn]); head[cn] = alen; }
int zh(int cn, int cm) {return (cn-1)*n + cm; }
int nzh(int cn) {int cx = (cn-1)/n+1, cy = (cn-1)%n+1; return yuan[cx][cy]; }
int get_fa(int cn) {return fa[cn] == cn ? cn : fa[cn] = get_fa(fa[cn]); }
void bcj_lian(int cn, int cm)
{
cn = get_fa(cn); cm = get_fa(cm);
if(cn == cm) return;
zhi[cm] = nzh(cn) - nzh(cm);
fa[cm] = cn; lian(cn,cm);
}
void jian()
{
alen = 0; memset(head,0,sizeof(head));
for(int i = 1;i<=n*n;i++) fa[i] = i;
for(int i = 1;i<=n*n;i++)
{
int bx = xu[i].x, by = xu[i].y;
if(1 < bx && yuan[bx-1][by] <= yuan[bx][by]) bcj_lian(zh(bx,by), zh(bx-1,by));
if(1 < by && yuan[bx][by-1] <= yuan[bx][by]) bcj_lian(zh(bx,by), zh(bx,by-1));
if(bx < n && yuan[bx+1][by] <= yuan[bx][by]) bcj_lian(zh(bx,by), zh(bx+1,by));
if(by < n && yuan[bx][by+1] <= yuan[bx][by]) bcj_lian(zh(bx,by), zh(bx,by+1));
}
for(int i = 1;i<=n*n;i++) if(fa[i] == i) zhi[i] = m-nzh(i), lian(n*n+1,i);
zhi[n*n+1] = 0;
}
void dfs(int cn)
{
Num::set();
for(int i = head[cn];i;i = a[i].ne) dfs(a[i].b), Num::cheng();
Num::zeng(zhi[cn]);
}
int main()
{
freopen("stage.in","r",stdin);
freopen("stage.out","w",stdout);
Read(n); Read(m);
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) Read(yuan[i][j]), Min(yuan[i][j], m);
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) xu[zh(i,j)].mk(i,j,yuan[i][j]);
sort(xu+1,xu+n*n+1); jian(); Num::build(); dfs(n*n+1); Num::outit();
return 0;
}