ARC102C 题解

intel_core · 2023-04-13 22:01:38 · 题解

考虑两数相加不为 m 条件的等价条件。注意到可以算出两数相加为 m 的数对的数量，再单独讨论一下不能选两次的数即可。

在计算 m 的答案时，先处理出 x,y 依次表示二选一的数对数量和只能选一个的数是否存在。

然后考虑容斥，钦定 i 个二选一的数对不能选，贡献是 (-1)^i2^{x-i}(C_{k-x-y-i+n-1}^{k-x-y-i-1}+yC_{k-x-y-i+n-2}^{k-x-y-i-1})。

预处理组合数即可 O(n^2) 计算。

#include<bits/stdc++.h>
using namespace std;
const int NR=4e3+10;
#define int long long
const int MOD=998244353;
int n,m,c[NR][NR],pw[NR];

void add(int &x,int y){x=(x+y)%MOD;}
signed main(){
    cin>>n>>m;
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2%MOD;
    for(int i=0;i<=n+m;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
    }
    for(int i=2;i<=2*n;i++){
        int x=min((i-1)/2,n-i/2),y=n-2*x-(i%2==0),z=(i%2==0),ans=0;
        for(int j=0;j<=x;j++){
            if(j&1)add(ans,-c[x][j]*pw[x-j]%MOD*(c[n-j-z-x+m-1][n-j-z-x-1]+z*c[n-j-z-x+m-2][n-j-z-x-1])%MOD);
            else add(ans,c[x][j]*pw[x-j]%MOD*(c[n-j-z-x+m-1][n-j-z-x-1]+z*c[n-j-z-x+m-2][n-j-z-x-1])%MOD);
        }
        cout<<(ans+MOD)%MOD<<endl;
    }
    return 0;
}