0%

loj#6275 题解 - 棋盘

题目链接

首先考虑辣鸡 DP $f_{i,s,j}$,表示考虑前 $i$ 列,第 $i$ 列状态为 $s$,有 $j$ 个连通块。

(有 $7$ 种状态:□□□,■□□ 和镜像,□■□,■■□ 和镜像,不连通的 ■□■,连通的 ■□■,■■■)

考虑它的 OGF $F_{i,s}(x)$,$F_{i,s}$ 的 $s$ 那维可以矩乘(当然矩阵的系数是多项式),即 $F_{i}=AF_{i-1}$。为了防止混淆我再强调一遍:其中 $F_{i}$ 是一个七维向量,每一维坐标都是一个多项式。

所以答案就是 $\sum_{s}[x^k] (A^mB)_s$。但是多项式乘法无法接受,所以我们只考虑点值表示然后 IDFT 回去即可。

$A$ 的值我是贺的,所以 $s$ 的顺序和我说的可能不一样,我也不想核验了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;

const int p=998244353,maxN=262144,g=3,ig=332748118,inv2=(p+1)/2;
int W[maxN],iW[maxN];
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
int ans=1;
while(k){
if(k&1) ans=1LL*ans*a%p;
a=1LL*a*a%p;
k>>=1;
}
return ans;
}
void init(){
int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN);
W[0]=iW[0]=1;
for(int i=1;i<maxN;i++)
W[i]=1LL*W[i-1]*w%p,
iW[i]=1LL*iW[i-1]*iw%p;
fac[0]=ifac[0]=fac[1]=ifac[1]=inv[1]=1;
for(int i=2;i<maxN;i++)
fac[i]=1LL*fac[i-1]*i%p,
inv[i]=1LL*(p-p/i)*inv[p%i]%p,
ifac[i]=1LL*ifac[i-1]*inv[i]%p;
}
int R[maxN];
void NTT(int d[],bool flg,int n0){
int x=1,len=0;while(x<n0) x<<=1,len++;
for(int i=0;i<x;i++){
R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
if(i<R[i]) swap(d[i],d[R[i]]);
}
for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1)
for(int j=0;j<x;j+=(i<<1))
for(int k=0,u=0;k<i;k++,u+=l){
int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p;
d[j|k]=(a0+a1)%p;d[j|i|k]=a0-a1+p;
if(d[j|i|k]>=p)d[j|i|k]-=p;
}
if(flg){
int invx=qpow(x,p-2);
for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p;
}
}

int n;
int N,M,K;

struct Mat{
int a[7][7];
Mat(){memset(a,0,sizeof(a));}
Mat operator *(const Mat b)const{
Mat c;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
c.a[i][k]=(c.a[i][k]+1LL*a[i][j]*b.a[j][k]%p)%p;
return c;
}
void init(int x){
int ix=qpow(x,p-2),x2=1LL*x*x%p,_2x=(x+x)%p,_1x=(x+1)%p;
if(N==1){
a[0][0]=a[1][1]=a[0][1]=1;
a[1][0]=x;
}
if(N==2){
a[0][0]=1,a[0][1]=1,a[0][2]=1,a[0][3]=1;
a[1][0]=x,a[1][1]=1,a[1][2]=x,a[1][3]=1;
a[2][0]=x,a[2][1]=x,a[2][2]=1,a[2][3]=1;
a[3][0]=x,a[3][1]=1,a[3][2]=1,a[3][3]=1;
}
if(N==3){
a[0][0]=1 ,a[0][1]=1 ,a[0][2]=1 ,a[0][3]=1 ,a[0][4]=1 ,a[0][5]=1 ,a[0][6]=1;
a[1][0]=_2x,a[1][1]=_1x,a[1][2]=_2x,a[1][3]=_1x,a[1][4]=2 ,a[1][5]=2 ,a[1][6]=2;
a[2][0]=x ,a[2][1]=x ,a[2][2]=1 ,a[2][3]=1 ,a[2][4]=x ,a[2][5]=x ,a[2][6]=1;
a[3][0]=_2x,a[3][1]=_1x,a[3][2]=2 ,a[3][3]=2 ,a[3][4]=2 ,a[3][5]=2 ,a[3][6]=2;
a[4][0]=0 ,a[4][1]=0 ,a[4][2]=0 ,a[4][3]=0 ,a[4][4]=1 ,a[4][5]=0 ,a[4][6]=1;
a[5][0]=x2 ,a[5][1]=x ,a[5][2]=x2 ,a[5][3]=x ,a[5][4]=0 ,a[5][5]=1 ,a[5][6]=0;
a[6][0]=x ,a[6][1]=1 ,a[6][2]=1 ,a[6][3]=1 ,a[6][4]=1 ,a[6][5]=ix ,a[6][6]=1;
}
}
}ans,A;
Mat QPOW(Mat a,int k){
Mat c;
for(int i=0;i<n;i++) c.a[i][i]=1;
while(k){
if(k&1) c=c*a;
a=a*a;
k>>=1;
}
return c;
}
int F[maxN];

int main(){
init();
scanf("%d%d%d",&N,&M,&K);
if(K>(N*M+1)/2){printf("0\n");return 0;}
if(N==1) n=2;if(N==2) n=4;if(N==3) n=7;
int n0=1,len=0;while(n0<=(N*M+1)/2) n0<<=1,len++;
int x=qpow(g,(p-1)/n0),xn=1;
for(int i=0;i<n0;i++){
A.init(xn);
ans=QPOW(A,M);
for(int j=0;j<n;j++) F[i]=(F[i]+ans.a[j][0])%p;
xn=1LL*xn*x%p;
}
NTT(F,1,n0);
printf("%d\n",F[K]);
return 0;
}