ARC102E Stop. Otherwise... 题解

· · 题解

这是一个没有必要的复杂做法，但我考场上第一时间想到的就是这个做法。

分析

首先观察样例。发现答案有对称性，所以我们只需要求出 \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;
}