「TJOI2019」唱、跳、rap 和篮球 题解

思路

考虑容斥，设 $f(i)$ 为唱、跳、rap 和篮球（下文称为矛盾序列）数量 $\ge i$ 时队列的方案数，则答案即为 $\sum_{i=0}^{k} (-1)^if(i)$，其中 $k$ 为矛盾序列的最大数量。

问题来到了求 $f(i)$，首先考虑插板法，则有 $f(i)=\frac{(n-3i)!}{(i)!(n-4i)!}g(n-4i,a-i,b-i,c-i,d-i)$，$g$ 表示剩下的数的排列方案数（所有方案，无论合不合法）。

问题又到了如何求 $g(n,a,b,c,d)$，暴力的想法是枚举唱、跳、rap的数量，不过这样时间复杂度时 $O(n^4)$，考虑优化，在枚举唱、跳的数量后rap 和篮球的总数时一定的，所以可以枚举出rap 和篮球的和，求出方案数，再枚举唱、跳的数量（代码中写法稍有不同，类似记忆化的方法），这样总时间复杂度就是 $O(n^3)$ 了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,a,b,c,d;
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
ll f[1010],fv[1010];
ll calc(int n,int a,int b,int c,int d){
	ll ans=0;
	ll v[1010],aa[1010];
	for(int i=0;i<=1000;i++)v[i]=0;
	for(int i=0;i<=a;i++)if(i<=n&&i+b+c+d>=n){
		for(int j=0;j<=b;j++)if(i+j<=n&&i+j+c+d>=n){
			if(v[i+j])ans=(ans+f[n]*fv[i]%mod*fv[j]%mod*aa[i+j]%mod)%mod;
			else {
				v[i+j]=1;
				aa[i+j]=0;
				for(int k=0;k<=c;k++)if(i+j+k<=n&&n-i-j-k<=d){
					ans=(ans+f[n]*fv[i]%mod*fv[j]%mod*fv[k]%mod*fv[n-i-j-k]%mod)%mod;
					aa[i+j]=(aa[i+j]+fv[k]%mod*fv[n-i-j-k]%mod)%mod;
				}
			}
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>a>>b>>c>>d;
	f[0]=1;
	fv[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]*i%mod;
		fv[i]=qpow(f[i],mod-2);
	}
	ll ans=0;
    ans=calc(n,a,b,c,d);
    for(int i=1;i<=min({n/4,a,b,c,d});i++){
        if(i&1)ans=(ans-f[n-i*3]*fv[n-i*4]%mod*fv[i]%mod*calc(n-i*4,a-i,b-i,c-i,d-i)%mod+mod)%mod;
        else ans=(ans+f[n-i*3]*fv[n-i*4]%mod*fv[i]%mod*calc(n-i*4,a-i,b-i,c-i,d-i)%mod)%mod;
    }
    cout<<ans;
	return 0;
}

Perhaps someone needs a simple and brute-force DP with a different approach, N^3 style?

我不是小黑子。

注意到小黑子出现都是连续的，干脆枚举出现次数 i。

然后算出：

至少有 0 段小黑子出现的方案数

至少有 1 段小黑子出现的方案数

至少有 2 段小黑子出现的方案数

...

至少有 $mi$ 段小黑子出现的方案数

（mi 是可能出现最多段黑子数，即 $min(n/4,a,b,c,d)$）

通过容斥原理，至少有 i 段小黑子出现的容斥系数就为 $(-1)^i$。

考虑至少有 $i$ 段小黑子的情况，占 $4 * i$ 的位置，把他们当作 i 个大黑子排列组合。

方案数为 $C_{n-3*i}^i$，即从总共 $n - 3 * i$ 个位置选 $i$ 个位置来放大黑子。

接下来处理 $n - 4 * i$ 个正常人的位置方案数，用 $n^2$ dp。

分别枚举每种爱好，再枚举总人数，最后枚举总人数中是当前这种爱好的人数。

依旧组合数即可。注意边界。

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const LL P = 998244353;
const int N = 1010;
int n, a[5];
LL c[N][N];
int mi;
 
LL powc(int x) {
    if (x & 1) {
        return -1ll;
    }
    return 1ll;
}
 
LL f[N];
LL calc(int nn) {
    memset(f, 0, sizeof(f));
    f[0] = 1;
 
    int sum = 0;
    for (int i = 1; i <= 4; i ++) {
        sum = min(nn, sum + a[i]);
        for (int j = sum; j >= 1; j --) {
            for (int k = min(a[i], j); k >= 1; k --) {
                f[j] = (f[j] + f[j - k] * c[j][j - k] % P) % P;
            }
        }
        a[i] --;
    }
    return f[nn];
}
 
int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    memset(c, 0, sizeof(c));
    c[0][0] = 1;
    for (int i = 1; i <= 1000; i ++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j ++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
        }
    }
 
    cin >> n;
    mi = n / 4;
    for (int i = 1; i <= 4; i ++) {
        cin >> a[i];
        mi = min(mi, a[i]);
    }
 
    LL ans = 0;
    for (int i = 0; i <= mi; i ++) {
        LL t = powc(i) * c[n - 3 * i][i] % P * calc(n - 4 * i) % P;
        ans = (ans + t + P) % P;
    }
    cout << ans << "\n";
 
    return 0;
}

针对 Benny 题解中的式子：

考虑将所有的 $i$ 矛盾序列看为一个整体，在不考虑剩余数字之间的区别的情况下。总计有 $n-3i$ 个序列参与排序。其中，$i$ 个矛盾序列都是相同的，需要去重，同时不考虑剩余数字的区别，即总共有 $\frac{(n-3i)!}{(i)!(n-4i)!}$ 种排列方案。

接下来考虑剩余数字，显然对于每一种已经确定的序列，都有 $g(n-4i,a-i,b-i,c-i,d-i)$ 种不同剩余数的安排方法，所以将两者相乘即可。

关于函数部分：

考虑枚举 $i,j$ 分别为唱和跳的人数，发现在 $i+j$ 恒定时，我们知道有 $i$ 个唱，$j$ 个跳，$n-i-j$ 个 rap 和篮球，那么如果将后两个看成一个整体（也就是不区分 rap 和篮球），那么这三类所能组成的排列就非常好算了。

也就是，对于以下式子：

$$\sum_{k=max(n-i-j-d,0)}^{\min(n-i-j,c)}{\frac{(n)!}{(i)!(j)!(k)!(n-i-j-k)!}}$$

在模意义下，将其变成：

$$\sum_{k=max(n-i-j-d,0)}^{\min(n-i-j,c)}(n)!fv_{i}fv_{j}fv_{k}fv_{n-i-j-k}$$

其中 $fv_i$ 为 $(i)!$ 在模 $998244353$ 意义下的逆元。

对于上式，将 $(n)!fv_{i}fv_{j}$ 提出来，变为：

$$(n)!fv_{i}fv_{j}\times\sum_{k=max(n-i-j-d,0)}^{\min(n-i-j,c)}fv_{k}fv_{n-i-j-k}$$

显然在 $i+j$ 恒定时，后面的数不变，所以将后面的数储存起来，加速计算。

代码：

bool vis[1005];//vis标记是否计算过 
ll mem[1005];//mem表示已经计算完的数值 
ll calc(int n,int a,int b,int c,int d){
	for(int i=0;i<=1000;i++){
		vis[i]=mem[i]=0;
	}
	ll ans=0;
	for(int i=0;i<=a;i++){
		if(i<=n && i+b+c+d>=n){ //这几个if都是判断是否合法的 
			for(int j=0;j<=b;j++){
				if(i+j<=n && i+j+c+d>=n){
					if(vis[i+j]){//直接调用已经算过的值 
						ans=(ans+f[n]*fv[i]%mod*fv[j]%mod*mem[i+j]%mod)%mod;
					}
					else{
						vis[i+j]=1;
						for(int k=0;k<=c;k++){//进行计算并存储 
							if(i+j+k<=n && i+j+k+d>=n){
								ans=(ans+f[n]*fv[i]%mod*fv[j]%mod*fv[k]%mod*fv[n-i-j-k]%mod)%mod;
								mem[i+j]=(mem[i+j]+fv[k]*fv[n-i-j-k]%mod)%mod;
							}
						}
					}
				}
			}
		}
	}
	return ans;
}

cxk hopping

我们考虑先钦定 $i$ 个位置放上“鸡你太美”，其它随便填，设其方案数为 $f(i)$。

但这个 $f(i)$ 显然不是恰好有 $i$ 个“鸡你太美”的排列数——甚至不是至少 $i$ 个“鸡你太美”的排列数。

我们再设 $g(i)$ 为恰好 $i$ 个“鸡你太美”的排列数。

我们考虑 $g(j)$ 会对 $f(i)$ 产生多少的贡献的贡献，显然对于这 $g(j)$ 个不同的排列，从 $j$ 个“鸡你太美”中任意钦定 $i$ 个都会对 $f(i)$ 产生 $1$ 的贡献，故 $f(i)=\sum\limits_{j=i}g(j)\times\dbinom{j}{i}$

又到了喜闻乐见的二项式反演的时间了

这个并不是常见的二项式反演的形式，但它也可以进行二项式反演，反演一下即可得到 $g(i)=\sum\limits_{j=i}(-1)^{j-i}\dbinom{j}{i}f(j)$

最后我们要求的答案为 $g(0)$，即 $\sum\limits_{j=0}(-1)^jf(j)$

接下来我们的任务就是求出 $f(i)$，考虑现在 $n$ 个位置上放好 $i$ 个“鸡你太美”的方案数，如果我们把每个”鸡你太美“看作一个人的话，那么相当于在 $n-3i$ 个位置上选择 $i$ 个位置留给”鸡你太美“，方案数为 $\dbinom{n-3i}{i}$。最后考虑填好其他人的方案数。那我们相当于是在 $n-4i$ 个位置上选择不超过 $a-i$ 个”唱“，不超过 $b-i$ 个“跳”，不超过 $c-i$ 个”rap“，不超过 $d-i$ 个”篮球“并排成一列的方案数。

看到”排成一列“当然想到 EGF 咯。设 $F1(x)=\sum\limits_{i=0}^{a-i}\dfrac{x^i}{i!},F2(x)=\sum\limits_{i=0}^{b-i}\dfrac{x^i}{i!},F3(x)=\sum\limits_{i=0}^{c-i}\dfrac{x^i}{i!},F4(x)=\sum\limits_{i=0}^{d-i}\dfrac{x^i}{i!}$，那么显然最终答案的 EGF 为 $F1\times F2\times F3\times F4$，多项式卷积合并即可，别忘了最终乘上 $(n-4i)!$，时间复杂度 $n^2\log n$，常熟较大，跑得比较慢。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
	x=0;char c=getchar();T neg=1;
	while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	x*=neg;
}
const int pr=3;
const int MOD=998244353;
const int MAXP=1<<11;
int qpow(int x,int e){
	int ret=1;
	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
	return ret;
}
int n,a,b,c,d,fac[MAXP+5],ifac[MAXP+5];
int A[MAXP+5],B[MAXP+5],C[MAXP+5],D[MAXP+5];
int LEN=1,LOG=0,rev[MAXP+5],prs[MAXP+5][2],inv[MAXP+5],ipr;
void NTT(int *a,int len,int type){
	int lg=log2(len);
	for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
	for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=2;i<=len;i<<=1){
		int W=prs[i][type<0];
		for(int j=0;j<len;j+=i){
			int w=1;
			for(int k=0;k<(i>>1);k++,w=1ll*w*W%MOD){
				int X=a[j+k],Y=1ll*a[(i>>1)+j+k]*w%MOD;
				a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;
			}
		}
	}
	if(type==-1) for(int i=0;i<len;i++) a[i]=1ll*a[i]*inv[len]%MOD;
}
int binom(int x,int y){return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
int solve(int n,int x1,int x2,int x3,int x4){
	for(int i=0;i<=x1;i++) A[i]=ifac[i];
	for(int i=0;i<=x2;i++) B[i]=ifac[i];
	for(int i=0;i<=x3;i++) C[i]=ifac[i];
	for(int i=0;i<=x4;i++) D[i]=ifac[i];
	NTT(A,LEN,1);NTT(B,LEN,1);NTT(C,LEN,1);NTT(D,LEN,1);
	for(int i=0;i<LEN;i++) A[i]=1ll*A[i]*B[i]%MOD*C[i]%MOD*D[i]%MOD;
	NTT(A,LEN,-1);int ans=1ll*A[n]*fac[n]%MOD;
	for(int i=0;i<LEN;i++) A[i]=B[i]=C[i]=D[i]=0;
	return ans;
}
int main(){
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);ipr=qpow(pr,MOD-2);
	while(LEN<=(a+b+c+d)) LEN<<=1,LOG++;
	for(int i=1;i<=LEN;i<<=1){
		inv[i]=qpow(i,MOD-2);
		prs[i][0]=qpow(pr,(MOD-1)/i);
		prs[i][1]=qpow(ipr,(MOD-1)/i);
	}
	fac[0]=1;for(int i=1;i<LEN;i++) fac[i]=1ll*fac[i-1]*i%MOD;
	ifac[LEN-1]=qpow(fac[LEN-1],MOD-2);for(int i=LEN-2;~i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%MOD;
	int ans=0;
	for(int i=0;i<=min(n/4,min(min(a,b),min(c,d)));i++){
		if(!(i&1)) ans=(ans+1ll*binom(n-3*i,i)*solve(n-4*i,a-i,b-i,c-i,d-i)%MOD)%MOD;
		else ans=(ans-1ll*binom(n-3*i,i)*solve(n-4*i,a-i,b-i,c-i,d-i)%MOD+MOD)%MOD;
	} printf("%d\n",ans);
	return 0;
}

注意到本题的卷积比较特殊。考虑从大到小倒着枚举 $j$，那么每次相当于是在 $F1(x),F2(x),F3(x),F4(x)$ 后面各添上一项。记 $G1(x)=F1(x)F2(x),G2(x)=F3(x)F4(x)$，那么我们每次都可以在 $\mathcal O(n)$ 的时间内更新 $G1(x),G2(x)$。并且最终我们要求的只是 $G1(x)G2(x)$ 中 $x^{n-3i}$ 项前面的系数，并不用把整个卷积都求出来，所以我们可以再次 $\mathcal O(n)$ 扫一遍求得。时间复杂度降到了 $\mathcal O(n^2)$。

似乎这么随随便便一写就抢到了除了 EI 之外的最优解？EI 给出了一个 $n^{1.5}$ 的神仙解法。storz EI yyds %%%%。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
	x=0;char c=getchar();T neg=1;
	while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	x*=neg;
}
const int MOD=998244353;
const int MAXP=1e3;
int qpow(int x,int e){
	int ret=1;
	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
	return ret;
}
int n,a,b,c,d,t1[MAXP+5],t2[MAXP+5];
int fac[MAXP+5],ifac[MAXP+5],ans=0;
int binom(int x,int y){return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
int main(){
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);int mn=min(n/4,min(min(a,b),min(c,d)));
	fac[0]=1;for(int i=1;i<=MAXP;i++) fac[i]=1ll*fac[i-1]*i%MOD;
	ifac[MAXP]=qpow(fac[MAXP],MOD-2);for(int i=MAXP-1;~i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%MOD;
	a-=mn;b-=mn;c-=mn;d-=mn;
	for(int i=0;i<=a;i++) for(int j=0;j<=b;j++) t1[i+j]=(t1[i+j]+1ll*ifac[i]*ifac[j]%MOD)%MOD;
	for(int i=0;i<=c;i++) for(int j=0;j<=d;j++) t2[i+j]=(t2[i+j]+1ll*ifac[i]*ifac[j]%MOD)%MOD;
	int sum=0;for(int i=0;i<=n-4*mn;i++) sum=(sum+1ll*t1[i]*t2[n-4*mn-i]%MOD)%MOD;
	sum=1ll*sum*fac[n-4*mn]%MOD;sum=1ll*sum*binom(n-3*mn,mn)%MOD;//printf("%d\n",sum);
	if(!(mn&1)) ans=sum;else ans=(MOD-sum)%MOD;
	for(int t=mn-1;~t;t--){
		a++;b++;c++;d++;
		for(int i=0;i<b;i++) t1[i+a]=(t1[i+a]+1ll*ifac[i]*ifac[a]%MOD)%MOD;
		for(int i=0;i<a;i++) t1[i+b]=(t1[i+b]+1ll*ifac[i]*ifac[b]%MOD)%MOD;
		t1[a+b]=(t1[a+b]+1ll*ifac[a]*ifac[b]%MOD)%MOD;
		for(int i=0;i<d;i++) t2[i+c]=(t2[i+c]+1ll*ifac[i]*ifac[c]%MOD)%MOD;
		for(int i=0;i<c;i++) t2[i+d]=(t2[i+d]+1ll*ifac[i]*ifac[d]%MOD)%MOD;
		t2[c+d]=(t2[c+d]+1ll*ifac[c]*ifac[d]%MOD)%MOD;
		sum=0;for(int i=0;i<=n-4*t;i++) sum=(sum+1ll*t1[i]*t2[n-4*t-i]%MOD)%MOD;
		sum=1ll*sum*fac[n-4*t]%MOD;sum=1ll*sum*binom(n-3*t,t)%MOD;//printf("%d\n",sum);
		if(!(t&1)) ans=(ans+sum)%MOD;else ans=(ans-sum+MOD)%MOD;
	} printf("%d\n",ans);
	return 0;
}