[数学记录]AT4362 [ARC102C] Stop. Otherwise...

· · 个人记录

题意 ：有 n 个骰子，每个骰子有 k 个面，上面有 1\sim k。

现在对于 [2,2k] 中的每一个数 x，求出任意投这个 n 个骰子使得不存在任意两个骰子的点数和为 x 的方案数。

骰子之间本质相同（无标号）。

答案对 998244353 取模。

------------ 只考虑 $x\leq k+1$ 时的情况，另一侧的方案数是对称的。 对于一个给定的 $x$ ，将数 $i,i-x$ 两两配对，两者中只能出现一个。 特殊地，$x/2$ 至多只能出现一次。 其余没有配对的数则无限制。 对子的个数是 $\lfloor (x-1)/2\rfloor$ ，而没配对的数的个数是 $k-x+1$。 无标号计数，使用 OGF。 对于至多出现一次的数 ： $F_{\rm one}(x)=1+x

对于一个对子 ： F_{\rm pair}(x)=1+2x+2x^2+...=\dfrac{1+x}{1-x}

对于一个没有配对的数 ： F_{\rm single}(x)=1+x+x^2+...=\dfrac{1}{1-x}

将所有生成函数乘起来，答案为 ：

[x^n]\dfrac{(1+x)^{k-x+1+[x\bmod 2=0]}}{(1-x)^{k-x+1+\lfloor (x-1)/2\rfloor}}

考虑如何快速求 [x^n]\dfrac{(1+x)^a}{(1-x)^b}

分子分母的展开式都是容易表示的，暴力计算卷积即可。

\begin{aligned} [x^n]\dfrac{(1+x)^a}{(1-x)^b}&=\sum\limits_{i=0}^n[x^i](1+x)^a[x^{n-i}](1-x)^{-b}\\ &=\sum\limits_{i=0}^n\dbinom{a}{i}\dbinom{b+(n-i)-1}{n-i} \end{aligned}

复杂度 O(nk)。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 2050
using namespace std;
const int mod=998244353;
ll powM(ll a,int t=mod-2){
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
int fac[MaxN<<1],ifac[MaxN<<1];
int C(int n,int m){
  if (m>n)return 0;
  return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void Init(int n)
{
  fac[0]=1;
  for (int i=1;i<=n;i++)
    fac[i]=1ll*fac[i-1]*i%mod;
  ifac[n]=powM(fac[n]);
  for (int i=n;i;i--)
    ifac[i-1]=1ll*ifac[i]*i%mod;
}
int calc(int a,int b,int n)
{
  int ret=0;
  for (int i=0;i<=n;i++)
    ret=(ret+1ll*C(a,i)*C(b+(n-i)-1,n-i))%mod;
  return ret;
}
int n,k,ans[MaxN];
int main()
{
  scanf("%d%d",&k,&n);
  Init(n+k);
  for (int i=2;i<=k+1;i+=2){
    ans[i]=calc(i/2,k-i+1+(i-1)/2,n);
    ans[i+1]=ans[i];
  }
  for (int i=2;i<=k+1;i++)printf("%d\n",ans[i]);
  for (int i=k;i>=2;i--)printf("%d\n",ans[i]);
  return 0;
}