题解：AT_abc273_g [ABC273G] Row Column Sums 2

做过 CF489F 但做不出这题的蒟蒻这辈子有了。

再怎么说也不该有

2400+

啊！

设

dp_{cnt1,cnt2}

代表抵达还剩 $cnt1$ 列为 $1$ 、 $cnt2$ 列为 $2$ 这个状态的方案数。注意

cnt1

和

cnt2

都必须动态更新。

考虑逐行填写剩下的位置，注意必须填

0/1/2

。

当这一列总和为

1

时，可以考虑以下操作：

将一个 $1$ 变成 $0$ 。方案数 $cnt1$ 。 $dp_{cnt1-1,cnt2}\gets dp_{cnt1-1,cnt2}+dp_{cnt1,cnt2}\times cnt1$ 。
将一个 $2$ 变成 $1$ 。方案数 $cnt2$ 。 $dp_{cnt1+1,cnt2-1}\gets dp_{cnt1+1,cnt2-1}+dp_{cnt1,cnt2}\times cnt2$ 。

当这一列总和为

2

时，可以考虑以下操作：

（也是我凭 CF489F 的经验漏掉的）将一个 $2$ 变成 $0$ 。方案数 $cnt2$ 。 $dp_{cnt1,cnt2-1}\gets dp_{cnt1,cnt2-1}+dp_{cnt1,cnt2}\times cnt2$ 。
将两个 $2$ 变成 $1$ 。方案数 $\frac{cnt2(cnt2-1)}{2}$ 。 $dp_{cnt1+2,cnt2-2}\gets dp_{cnt1+2,cnt2-2}+dp_{cnt1,cnt2}\times \frac{cnt2(cnt2-1)}{2}$ 。
将两个 $1$ 变成 $0$ 。方案数 $\frac{cnt1(cnt1-1)}{2}$ 。 $dp_{cnt1-2,cnt2}\gets dp_{cnt1-2,cnt2}+dp_{cnt1,cnt2}\times \frac{cnt1(cnt1-1)}{2}$ 。
将一个 $1$ 变成 $0$ ，将一个 $2$ 变成 $1$ 。方案数 $cnt1\times cnt2$ 。 $dp_{cnt1,cnt2-1}\gets dp_{cnt1,cnt2-1}+dp_{cnt1,cnt2}\times cnt1\times cnt2$ 。

预处理组合数的逆元可以得到

O(n^2)

的时间复杂度。注意转移时应先递减枚举

cnt2

，再递减枚举

cnt1

。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	} 
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar(); 
	} 
	return a*b;
} 
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
const int N=5005;
const int mod=998244353;
int n;
int a[N],b[N];
int cnt1,cnt2;
int dp[N][N];

int jc[N],inv_[N];
inline int qpow(int x,int y){
	if(y==0)	return 1;
	if(y==1)	return x;
	int ret=qpow(x,y/2);
	ret=ret*ret%mod;
	if(y&1)	ret=ret*x%mod;
	return ret;
}
inline int inv(int x){
	return qpow(x,mod-2);
}
inline int C(int x,int y){
	if(y<0||y>x)	return 0;
	return jc[x]*inv_[y]%mod*inv_[x-y]%mod;
}
void init(){
	jc[0]=inv_[0]=1;
	for(int i=1;i<=5000;i++){
		jc[i]=jc[i-1]*i%mod;
		inv_[i]=inv(jc[i]);
	}
}

int sum[N*4];
#undef int
int main(){
	#define int long long
	init();
	n=read();
	int A=0,B=0;
	for(int i=1;i<=n;i++){
		a[i]=read(),A+=a[i];
		if(a[i]==1)	cnt1++;
		if(a[i]==2)	cnt2++;
	}
	for(int i=1;i<=n;i++){
		b[i]=read(),B+=b[i];
//		b[i]+=b[i-1];
		if(!sum[B])	sum[B]=i;
	}
	if(A!=B){
		// cout<<"谭总的世界-071"<<endl;
		write2(0);
		return 0;
	}
	
	//无解情况一： sum a[i]!=sum b[i] 
	dp[cnt1][cnt2]=1;	//代表最初计数 
//	for(int _=n;_>=0;_--){
		for(int j=n;j>=0;j--){
			for(int i=n;i>=0;i--){
				if((sum[i+j*2]!=0)||(i==0&&j==0)){
	//				cout<<'#'<<now<<' '<<i<<' '<<j<<' '<<dp[i][j]<<endl;
					int now=b[sum[i+j*2]];
//					cout<<'#'<<sum[i+j*2]<<' '<<b[sum[i+j*2]]<<' '<<i<<' '<<j<<' '<<dp[i][j]<<endl;
					if(now==1){
						//第一种是把 1 减少一个 
						if(i>=1){
							dp[i-1][j]+=dp[i][j]*C(i,1)%mod;
							dp[i-1][j]%=mod;
						} 
						//第二种是把 2 减少一个 把 1 增加一个！
						if(j>=1){
							dp[i+1][j-1]+=dp[i][j]*C(j,1)%mod;
							dp[i+1][j-1]%=mod;
						} 
					}
					else{
						//第一种是处理两个 1 
						if(i>=2){
							dp[i-2][j]+=dp[i][j]*C(i,2)%mod;
							dp[i-2][j]%=mod;
						} 
						//第二种 处理两个 2 然后剩下两个 1  
						if(j>=2){
							dp[i+2][j-2]+=dp[i][j]*C(j,2)%mod;
							dp[i+2][j-2]%=mod;
						}
						//第三种？处理一个 1 一个 2 留下一个 1 
						if(i>=1&&j>=1){
							dp[i][j-1]+=dp[i][j]*C(i,1)%mod*C(j,1)%mod;
							dp[i][j-1]%=mod;
						} //第四种 处理一个 2  
						if(j>=1){
							dp[i][j-1]+=dp[i][j]*C(j,1)%mod;
							dp[i][j-1]%=mod; 
						}
					}
				}
			}
		} 
//		cout<<endl;	
//	}
	 
	write2(dp[0][0]);
	return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！ 

/*
18
2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0
1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2
*/

题解：AT_abc273_g [ABC273G] Row Column Sums 2

文章操作

相关推荐

评论

题解：AT_abc273_g [ABC273G] Row Column Sums 2