题解：AT_abc273_g [ABC273G] Row Column Sums 2

include13_fAKe · 2025-10-27 21:22:35 · 题解

做过 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。

#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
*/