[数学记录]AT4362 [ARC102C] Stop. Otherwise...
command_block
2021-05-04 08:10:45
**题意** ：有 $n$ 个骰子，每个骰子有 $k$ 个面，上面有 $1\sim k$。
现在对于 $[2,2k]$ 中的每一个数 $x$，求出任意投这个 $n$ 个骰子使得不存在任意两个骰子的点数和为 $x$ 的方案数。
骰子之间本质相同（无标号）。
答案对 $998244353$ 取模。
$n,k\leq 2000$ ，时限$\texttt{2s}$。
------------
只考虑 $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)$。
```cpp
#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;
}
```