【容斥】【数学】Atcoder ARC102 Stop. Otherwise...

题意：

有N个K个面的骰子，当i=2，3，4……2*k时，
求所有骰子的点数中，没有任何两个之和为i的方案数。这N个骰子不互相区分（即1，2与2，1是同一种情况）

分析：

很简单的一道容斥题（无奈D看错题意调太久。。。）

任何两个加起来不为i，所以这题就简单了。无非就是说对于$j$，要求$i-j$与它不能同时出现（i为偶数时,分两种情况讨论，即存在一个$\frac i 2$和不存在$\frac i 2$）。然后就可以算出矛盾的对数，即$k2=min\{k-\lfloor \frac i 2 \rfloor,\lfloor \frac {i-1} 2 \rfloor \}$。

然后没有影响的种类就有$k1=k-k2*2-[i\%2==0]$

现在问题转化为：求（k1+k2种颜色，N个骰子的方案数，即$C_{N+k1+k2-1}^{k1+k2-1}$）$\times 2^{k2}$，但就这样算会出现重复，因为可能那$k2$种颜色中，并没有全部用过，因此在乘上$2^{k2}$后，对某个方案而言，有$j$个没用过，就会重复计算$2^j$次。

所以就可以开心地容斥啦
下面给一个总式子

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 2010
#define MOD 998244353
using namespace std;
typedef long long ll;
ll C[2*MAXN][2*MAXN],bits[2*MAXN];
int n,k;
ll count(int s,int tot){return C[s+tot-1][s-1]; 
}
ll solve(int i,int tot){int k2=min(k-i/2,(i-1)/2);int k1=k-k2*2-((i%2)==0);ll flag=1;ll res=0;for(int l=k2;l+k1>0&&l>=0;l--,flag=-flag){res+=flag*count(l+k1,tot)*bits[l]%MOD*C[k2][l]%MOD;res%=MOD;}return (res+MOD)%MOD;
}
int main(){SF("%d%d",&k,&n);int sum=0;bits[0]=1;for(int i=1;i<=4000;i++)bits[i]=bits[i-1]*2ll%MOD;C[0][0]=1;for(int i=1;i<=4000;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;}ll ans=0;for(int i=2;i<=2*k;i++){if(i%2==0){ans=(solve(i,n)+solve(i,n-1))%MOD;}else{ans=solve(i,n);}PF("%lld\n",ans);}
}