[数学记录]Loj#6503. 「雅礼集训 2018 Day4」Magic
command_block
2020-11-03 07:15:29
**题意** ：有 $m$ 种小球,每种小球有 $a[i]$ 个,一共有 $\sum a[i] = n$ 个小球.
把它们排成一排
，求恰有 $k$ 对相邻的小球种类相同的方案数。
答案对 $998244353$ 取模。
$m\leq 2\times 10^4.n\leq 2\times 10^5$ ，时限$\texttt{1s}$。
------------
考虑钦定 $k$ 个相邻相同关系，最后反演。
那么，若 $a$ 个同类小球最终在序列里产生 $t$ 次相邻相同，则相当于分成了 $a-t$ 个连续段，不妨直接视作 $a-t$ 个球。
对于一类大小为 $a$ 的球 ，将其分成 $i$ 段的方案书可用夹板法计算，为 $\dbinom{a-1}{i-1}$
枚举其缩成多少段，可得其 $\rm EGF$ 为 $\sum\limits_{i=1}^{a}\dfrac{\binom{a-1}{i-1}x^i}{i!}$
用分治 $\rm FFT$ 将各个球的 $\rm EGF$ 卷积起来。
钦定 $k$ 个相邻相同关系时，会缩成 $n-k$ 段，即 $[x^{n-k}]$ 项系数。
设 $f(k)$ 为钦定 $k$ 个相邻相同的方案数，$g(k)$ 为恰有 $k$ 个相邻相同的方案数。
则有 $f(k)=\sum\limits_{i=k}^{n-1}\dbinom{i}{k}g(i)\Rightarrow g(k)=\sum\limits_{i=k}^{n-1}\dbinom{i}{k}(-1)^{i-k}f(k)$。
复杂度 $O(n\log^2n)$。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define ull unsigned long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int _G=3,mod=998244353,Maxn=135000;
ll powM(ll a,ll t=mod-2){
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;t>>=1;
}return ans;
}
ll fac[Maxn],ifac[Maxn];
ll C(int n,int m)
{return 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]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
const int invG=powM(_G);
int tr[Maxn],tf;
void tpre(int n){
if (tf==n)return ;tf=n;
for(int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *g,bool op,int n)
{
tpre(n);
static ull f[Maxn],w[Maxn]={1};
for (int i=0;i<n;i++)f[i]=(((ll)mod<<5)+g[tr[i]])%mod;
for(int l=1;l<n;l<<=1){
ull tG=powM(op?_G:invG,(mod-1)/(l+l));
for (int i=1;i<l;i++)w[i]=w[i-1]*tG%mod;
for(int k=0;k<n;k+=l+l)
for(int p=0;p<l;p++){
int tt=w[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
}if (!op){
ull invn=powM(n);
for(int i=0;i<n;++i)
g[i]=f[i]%mod*invn%mod;
}else for(int i=0;i<n;++i)g[i]=f[i]%mod;
}
void px(int *f,int *g,int n)
{for(int i=0;i<n;++i)f[i]=1ll*f[i]*g[i]%mod;}
int _o[Maxn],*tbuf=_o;
struct Poly{int len,*f;}a[Maxn];
Poly times(Poly A,Poly B)
{
static int t1[Maxn],t2[Maxn],t3[Maxn];
int len=A.len+B.len-1;
if (1ll*A.len*B.len<=(A.len+B.len)*30ll){
for (int i=0;i<A.len;i++)
for (int j=0;j<B.len;j++)
t3[i+j]=(t3[i+j]+1ll*A.f[i]*B.f[j])%mod;
cpy(A.f,t3,len);clr(t3,len);
}else {
cpy(t1,A.f,A.len);
cpy(t2,B.f,B.len);
int n=1;
while(n<len)n<<=1;
NTT(t1,1,n);NTT(t2,1,n);
px(t1,t2,n);NTT(t1,0,n);
cpy(A.f,t1,len);
clr(t1,n);clr(t2,n);
}return (Poly){len,A.f};
}
int n,m,k;
int main()
{
scanf("%d%d%d",&m,&n,&k);
Init(n);
for (int i=1;i<=m;i++){
scanf("%d",&a[i].len);
a[i].f=tbuf;
for (int j=1;j<=a[i].len;j++)
a[i].f[j]=C(a[i].len-1,j-1)*ifac[j]%mod;
tbuf+=++a[i].len;
}
while(m>1){
for (int i=2;i<=m;i+=2)
a[i/2]=times(a[i-1],a[i]);
if (m&1)a[m/2+1]=a[m];
m=(m+1)/2;
}
ll ans=0;
for (int i=k;i<n;i++){
if ((i-k)&1)ans=(ans-C(i,k)*a[1].f[n-i]%mod*fac[n-i])%mod;
else ans=(ans+C(i,k)*a[1].f[n-i]%mod*fac[n-i])%mod;
}printf("%lld",(ans+mod)%mod);
return 0;
}
```