[学军20201104CSP模拟赛] 二维码

简要题意：

对于(n imes m)的网格图，初始时全部为白色，现在通过下面的方法染色

每次选择一个行或者列，把它全部染成黑色或者全部染成白色

求任意操作的情况下，可以得到的不同网格图的数量(mod 998244353)

[ ]

判定一个染色方案是否有解的条件是：

染色完成的矩阵不包含一个子矩阵满足四个角分别为

或者

但是这样看这个条件似乎比较抽象，如果具体对于一个行上考虑，就是满足

每一行所包含的1的位置的集合之间 互为子集

显然一个方案可以任意交换行/列，不妨把按照每一行1的个数将每一行排序，设每一行有(a_i)个1，边界条件为(a_0=0)

那么对于行上的1考虑排列，方案数为(egin{aligned} prod inom{m-a_{i-1}}{a_i-a_{i-1}}end{aligned})，即从空的(m-a_{i-1})个位置里选出多出的(a_i-a_{i-1})个位置

而对于列之间的排列需要考虑(a_i)与(a_{i+1})的关系，因为如果(a_i=a_{i+1})时，必然满足这两行相同

设所有的(a_i)构成若干个相同的组，每一组包含(b_i(iin[1,k]))个元素，则方案数显然为(egin{aligned} frac{n!}{prod b_i!}end{aligned})

而组内的(a_i)之间显然是没有(egin{aligned} sum inom{m-a_{i-1}}{a_i-a_{i-1}}end{aligned})的贡献的，可以跳过

由此，不妨令(dp_{i,j})表示(dp)了前(i)行，最后一行(a_i=j)，每次枚举每个组(b_i)转移

复杂度为(O(n^4))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
const int N=2010,P=998244353;
int n,m,C[N][N],dp[N][N],I[N],J[N];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int main(){
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-2,0) I[i]=1ll*I[i+1]*(i+1)%P;
	rep(i,0,N-1) rep(j,C[i][0]=1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;

	scanf("%d%d",&n,&m);
	rep(i,0,n) dp[i][0]=I[i]; // 第一个块
	rep(i,1,n) rep(j,1,m) {
		rep(a,0,i-1) rep(b,0,j-1) {
			dp[i][j]=(dp[i][j]+1ll*dp[a][b]*I[i-a]%P*C[m-b][j-b])%P;
		}
	}
	int ans=0;
	rep(i,0,m) ans=(ans+dp[n][i])%P;
	ans=1ll*ans*J[n]%P;
	printf("%d
",ans);
}

优化：

发现两维(dp)之间是相互独立的，分别是把(n,m)分组

令(F_{i,j})表示把(n)分成了(i)个组，当前总和为(j)的方案数，(G_{i,j})表示把(m)分成(i)组，当前总和为(j)

按照上面的系数转移，最后(O(n))合并，复杂度为(O(n^3))

[ ]

进一步优化：

为了方便下面的叙述，不妨先整理一下(a_i)之间转移的系数，不妨设边界(a_{n+1}=m)

(egin{aligned} prod inom{m-a_{i-1}}{a_i-a_{i-1}}=prod_{i=1}^n frac{(m-a_{i-1})!}{(a_i-a_{i-1})!(m-a_{i})!}= frac{m!}{prod_{i=1}^{n+1} (a_{i}-a_{i-1})!}end{aligned})

发现实际上和列之间的系数是类似的，每次枚举(a_i-a_{i-1})即可

而实际上只有(k)个(b_i)直接相交的位置(a_{i}-a_{i-1})有效，因此行和列实际上分别是将(n,m)分成了(k)组

观察上面的转移系数，行构成的块，首个块大小可以为(0)，而列构成的块最后一个块大小可以为(0)，所以这个并不是严格分成(k)组，下面会讨论这个问题

我们计算答案的复杂度消耗在计算分成若干块的方案，而实际上，把(n)分成(k)块的方案数就是(egin{Bmatrix} n\ kend{Bmatrix}cdot k!)

用(n^2)递推第二类斯特林数的方法即可计算

对于并不是严格分成(k)组的问题，可以考虑把开头/结尾那一个大小为(0)的块删掉，即同时还要考虑(egin{Bmatrix}n \ k-1end{Bmatrix}(k-1)!)

最后再枚举(k)，复杂度为(O(n^2))

更优化的就是( ext{NTT})计算斯特林数，带入通项公式

(egin{aligned} egin{Bmatrix}n\ mend{Bmatrix}m!=sum_{i=0}^m i^n(-1)^{m-i}inom{m}{i} end{aligned})

显然把组合数拆开( ext{NTT})即可

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=1<<18|10,P=998244353;

int n,m,ans;
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int I[N],J[N];

int rev[N];
int Init(int n){ 
	int R=2,c=0;
	while(R<=n) R<<=1,c++;
	rep(i,0,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<c);
	return R;
}

void NTT(int n,int *a,int f){
	static int e[N>>1];
	rep(i,1,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=e[0]=1;i<n;i<<=1) {
		ll t=qpow(f==1?3:(P+1)/3,(P-1)/i/2);
		for(int j=i-2;j>=0;j-=2) e[j+1]=(e[j]=e[j>>1])*t%P;
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=1ll*a[j+i]*e[j-l]%P;
				a[j+i]=a[j]-t,Mod2(a[j+i]);
				a[j]+=t,Mod1(a[j]);
			}
		}
	}
	if(f==-1) {
		ll base=qpow(n);
		rep(i,0,n-1) a[i]=a[i]*base%P;
	}
}

int A[N],B[N],C[N];

int main(){
	scanf("%d%d",&n,&m);
	if(n<m) swap(n,m);
	rep(i,J[0]=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-2,0) I[i]=1ll*I[i+1]*(i+1)%P;

	int R=Init(n+n+2);
	rep(i,0,n) A[i]=qpow(i,n)*I[i]%P;
	rep(i,0,n) B[i]=(i&1)?P-I[i]:I[i];
	NTT(R,A,1),NTT(R,B,1);
	rep(i,0,R-1) A[i]=1ll*A[i]*B[i]%P;
	NTT(R,A,-1);
	rep(i,n+1,R) A[i]=0;

	rep(i,0,m) C[i]=qpow(i,m)*I[i]%P;
	NTT(R,C,1);
	rep(i,0,R-1) C[i]=1ll*C[i]*B[i]%P;
	NTT(R,C,-1);
	rep(i,m+1,R) C[i]=0;

	int ans=0;
	rep(i,0,min(n,m)) ans=(ans+1ll*(1ll*A[i]*J[i]%P+1ll*A[i+1]*J[i+1]%P)*(1ll*C[i]%P*J[i]%P+1ll*C[i+1]*J[i+1]%P))%P;
	printf("%d
",ans);
}