怎么做的？？
考虑至少有k组人在讨论cxk，给他们按位置的因数是C(n-3k,k)
剩下n-4k个位置，设第i类人物出现了di个，
满足d0+d1+d2+d3=n-4k，di+k<=pi，pi是第i类任务的总数
容易发现给这些人排位置的因数是(n-4k)!/(d0!d1!d2!d3!)
上边这玩意儿不就是卷积么。
把这两个因数相乘就得到k的答案了。
取k=1到n各做一遍，最后容斥得到?答案。
时间复杂度O(n2logn)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000+5;
const int mod=998244353;
int C[N][N],n,num[N];
int fac[N<<2],inv[N<<2],rev[N<<2],b[5][N<<2];
inline int qpow(int x,int y) {
int c=1;
for(; y; y>>=1,x=1LL*x*x%mod)
if(y&1) c=1LL*c*x%mod;
return c;
}
inline void ntt(int*a,int lmt,int flag) {
for(int i=0; i<lmt; ++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int m=1; m<lmt; m<<=1) {
int wm=qpow(3,(mod-1)/(m<<1));
if(flag==-1) wm=qpow(wm,mod-2);
for(int i=0; i<lmt; i+=(m<<1)) {
int w=1,tmp;
for(int j=0; j<m; ++j,w=1LL*w*wm%mod) {
tmp=1LL*a[i+j+m]*w%mod;
a[i+j+m]=(a[i+j]-tmp+mod)%mod;
a[i+j]=(a[i+j]+tmp)%mod;
}
}
}
if(flag!=-1) return;
int tmp=qpow(lmt,mod-2);
for(int i=0; i<lmt; ++i) a[i]=1LL*a[i]*tmp%mod;
}
inline int calc(int k) {
int lmt=1,l=0;
while(lmt<=max((num[4]-k)<<2,(n-4*k)<<1)) lmt<<=1,l++;
for(int i=0; i<lmt; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=1; i<=4; ++i) {
int ret=num[i]-k;
for(int j=0; j<=ret; ++j) b[i][j]=inv[j];
for(int j=ret+1; j<lmt; ++j) b[i][j]=0;
ntt(b[i],lmt,1);
}
for(int i=2; i<=4; ++i) for(int j=0; j<lmt; ++j)
b[1][j]=1LL*b[1][j]*b[i][j]%mod;
ntt(b[1],lmt,-1);
return 1LL*b[1][n-4*k]*fac[n-4*k]%mod;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=4; ++i) scanf("%d",&num[i]);
for(int i=0; i<=n; ++i) {
C[i][0]=1;
for(int j=1; j<=i; ++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
sort(num+1,num+5);
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2; i<N; ++i) {
fac[i]=1LL*fac[i-1]*i%mod;
inv[i]=qpow(fac[i],mod-2);
}
int ans=0,c=1;
for(int i=0; (i<<2)<=min(n,num[1]<<2); ++i) {
ans=((ans+1LL*c*C[n-3*i][i]%mod*calc(i)%mod)%mod+mod)%mod;
c*=-1;
}
printf("%dn",ans);
return 0;
}又去蒯人题解，怎么这副德行
律师函警告
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
