这是一个没有必要的复杂做法,但我考场上第一时间想到的就是这个做法。
分析
首先观察样例。发现答案有对称性,所以我们只需要求出 \(\left[2,k+1\right]\) 区间内的答案。又发现相邻两项答案是一样的,所以只需要处理其中奇数情况的答案。
推式子
设 \(f_s\) 表示点数和不为 \(2s+1\) 时的方案数,此时有 \(s\) 对不能同时出现的点数,写出暴力计算的式子。
\[f_s = \sum\limits_{i=1}^{k-s}\sum\limits_{j=1}^{s}\binom{n-1}{i-1}\binom{s}{j}\binom{k-2s}{i-j}2^{j}
\]
上面的式子中,\(i\) 表示总共出现了 \(i\) 种点数,其中互斥的 \(s\) 对点数中出现了 \(j\) 对。
发现两个含有 \(i\) 的组合数似乎可以范德蒙德卷积,于是交换一下 \(i\) 和 \(j\) 的位置。
\[\begin{aligned}
f_s
&= \sum\limits_{i=1}^{s}2^{i}\binom{s}{i}\sum\limits_{j=1}^{k-s}\binom{n-1}{j-1}\binom{k-2s}{j-i}\\
&= \sum\limits_{i=1}^{s}2^{i}\binom{s}{i}\sum\limits_{j=1}^{k-s}\binom{n-1}{n-j}\binom{k-2s}{j-i}\\
&= \sum\limits_{i=1}^{s}2^{i}\binom{s}{i}\binom{n+k-2s-1}{n-i}\\
\end{aligned}
\]
在用过范德蒙德卷积后,这个式子求和的复杂度为 \(\mathrm{O(k)}\) ,我们要计算 \(\mathrm{O(n)}\) 个询问,所以总复杂度为 \(\mathrm{O(nk)}\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
const int MOD=998244353;
void exgcd(int a,int &x,int b,int &y){
if(!b){
x=1;
y=0;
}else{
exgcd(b,y,a%b,x);
y-=a/b*x;
}
}
int Inv(int x){
int res,y;
exgcd(x,res,MOD,y);
return (res%MOD+MOD)%MOD;
}
int Add(int a,int b){
return a+b>=MOD?a+b-MOD:a+b;
}
int Sub(int a,int b){
return a-b<0?a-b+MOD:a-b;
}
int Mul(int a,int b){
return 1ll*a*b%MOD;
}
int Div(int a,int b){
return 1ll*a*Inv(b)%MOD;
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=Mul(res,a);
}
a=Mul(a,a);
b>>=1;
}
return res;
}
int n,k,f[2*N],fac[2*N],infac[2*N];
int C(int n,int m){
return n>=m?Mul(fac[n],Mul(infac[m],infac[n-m])):0;
}
int main(){
scanf("%d%d",&k,&n);
fac[0]=1;
for(int i=1;i<=n+k;i++){
fac[i]=Mul(fac[i-1],i);
}
infac[n+k]=Inv(fac[n+k]);
for(int i=n+k-1;i>=0;i--){
infac[i]=Mul(infac[i+1],i+1);
}
for(int i=1;2*i<=k+1;i++){
for(int j=0;j<=min(i,n);j++){
f[2*i]=Add(f[2*i],Mul(Mul(qpow(2,j),C(i,j)),C(n+k-2*i-1,n-j)));
}
}
for(int i=1;2*i<=k;i++){
f[2*i+1]=f[2*k+2-2*i]=f[2*k+2-2*i-1]=f[2*i];
}
for(int i=2;i<=2*k;i++){
printf("%d\n",f[i]);
}
return 0;
}