题解 P5339 【[TJOI2019]唱、跳、rap和篮球】
command_block
2019-12-13 12:46:52
CXK题怎么都这么毒瘤啊/kk
设$f(k)$为钦定$k$个鸡你太美,其余放任自流的方案数。
$g(k)$为队伍中恰好有$k$个鸡你太美的方案数,我们要求的就是$g(0)$。
可以得到$f(k)=\sum\limits_{i=k}\dbinom{i}{k}g(k)$
那么二项式反演可得$g(k)=\sum\limits_{i=k}(-1)^{i-k}\dbinom{i}{k}f(k)$
设$S(a,b,c,d,n)$为随便排列的方案数,不符合题意即为$0$。
又可以得到$f(k)=\dbinom{n-3k}{k}S(a-k,b-k,c-k,d-k,n-4k)$
得$g(0)=\sum\limits_{k=0}(-1)^kf(k)$
$=\sum\limits_{k=0}(-1)^k\dbinom{n-3k}{k}S(a-k,b-k,c-k,d-k,n-4k)$
剩下的问题就是求$S$了。
$S(a,b,c,d,n)$的组合意义就是在四种颜色里面(有个数限制)取一些来涂色。
(为了方便令$X_i=\dfrac{x^i}{i!}$)
这个是EGF经典问题,考虑构造$R_k(x)=\sum\limits_{i=0}^kX_i$,就是$k$个同种颜色的EGF。
EGF卷积的意义就是随意插入混合,那么我们把四个$R$卷起来之后取第$n$项就可以得到答案了。
这样子的话要对每一个$S$都做一次NTT,复杂度$O(n^2logn)$,比较慢。
我们需要的$S$的参数比较特殊,可以针对来优化。
我们从小到大枚举$k$,那么相当于每次都会在四个$R$的后面添加一项。
我们考虑一个一个来添加,分别维护前两个EGF的卷积和后两个EGF的卷积。
最后因为只需要查询一项,$O(n)$暴力即可。
考虑前两个,后两个类似 :
$R_aR_b=(R_{a-1}+X_a)(R_{b-1}+X_b)=R_{a-1}R_{b-1}+X_aR_b+X_bR_a-X_aX_b$
$R_{a-1}R_{b-1}$上一次知道了,后面的几项$O(n)$计算即可。
综上,时间复杂度$O(n^2)$,空间$O(n)$,代码写起来比较流畅。
随手交了一发居然rk1了,不过应该很快就会被超过去。
~~这个题范围扩大3倍不过分吧~~
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 998244353
#define Maxn 1050
using namespace std;
int r[Maxn];
ll invn,invG;
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 ifac[Maxn],fac[Maxn];
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void Init(int lim)
{
ifac[0]=fac[0]=1;
for (int i=1;i<=lim;i++)
fac[i]=fac[i-1]*i%mod;
ifac[lim]=powM(fac[lim]);
for (int i=lim-1;i;i--)
ifac[i]=ifac[i+1]*(i+1)%mod;
}
ll R1[Maxn],R2[Maxn];
int a,b,c,d,n;
int main()
{
scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
Init(n);
int k=min(min(min(a,b),min(c,d)),n/4);
a-=k;b-=k;c-=k;d-=k;
for (int i=0;i<=a;i++)
for (int j=0;j<=b;j++)
R1[i+j]=(R1[i+j]+ifac[i]*ifac[j])%mod;
for (int i=0;i<=c;i++)
for (int j=0;j<=d;j++)
R2[i+j]=(R2[i+j]+ifac[i]*ifac[j])%mod;
ll ans=0;
for (;k>=0;k--){
ll buf=0;
int tp=n-4*k;
for (int i=0;i<=tp;i++)
buf=(buf+R1[i]*R2[tp-i])%mod;
buf=buf*fac[tp]%mod*C(n-3*k,k)%mod;
ans=(ans+ ((k&1) ? mod-buf : buf) )%mod;
a++;b++;c++;d++;
for (int i=0;i<=a;i++)
R1[i+b]=(R1[i+b]+ifac[i]*ifac[b])%mod;
for (int i=0;i<=b;i++)
R1[i+a]=(R1[i+a]+ifac[i]*ifac[a])%mod;
R1[a+b]=(-ifac[a]*ifac[b]%mod+R1[a+b]+mod)%mod;
for (int i=0;i<=c;i++)
R2[i+d]=(R2[i+d]+ifac[i]*ifac[d])%mod;
for (int i=0;i<=d;i++)
R2[i+c]=(R2[i+c]+ifac[i]*ifac[c])%mod;
R2[c+d]=(-ifac[c]*ifac[d]%mod+R2[c+d]+mod)%mod;
}printf("%lld",ans);
return 0;
}
```