题解：P14534 [RMI 2018] W

这种排列计数题，一般从左到右不好 dp，转而考虑按值从大到小 dp（类似套路有 P9197 等）。把 W 拆成五个极值点，一共有

2^5

种状态，用

0

和

1

表示极值点的确定与否。只需要会怎么转移，就做完了，本质是自动机，但是因为有效状态较少，所以采用手动机。

下面引用官方题解里的一张图片：（个人认为比较抽象，仅供理解）

举点例子，假设状态是

10100

，那么：

状态 $00000$ 贡献 ${x-1\choose 1}$ ，意义即为将 $x$ 个数分为两段且不能为空。
状态 $10000$ 贡献 ${x\choose 1}$ ，意义即为将 $x$ 分为两段，一段不能为空。
状态 $00100$ 贡献 $x+1\choose 2$ ，意义即为将 $x$ 分为三段，一段不能为空。因为中间的极值点能往左右两边扩展。
状态 $10100$ 贡献 $x+2\choose 2$ ，意义即为将 $x$ 分为三段。

假设状态是

11101

，那么：

状态 $10100$ 贡献 ${x\choose 2}$ ，意义即为将 $x$ 个数分为三段，两段不能为空。注意，此时中间的极值点不能扩展左边。
状态 $11100$ 贡献 ${x\choose 1}$ ，意义即为将 $x$ 分为两段，一段不能为空。
状态 $10101$ 贡献 $x+1\choose 2$ ，意义即为将 $x$ 分为三段，一段不能为空。
状态 $11101$ 贡献 $x+1\choose 1$ ，意义即为将 $x$ 分为两段。

其余情况类似，可参考代码。最终时间复杂度为

O(n)

，带一点常数。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e9+7;
int a[N],f[1<<5],g[1<<5],fac[N],fv[N],inv[N];
int C(int x,int y){
	if(x<y) return 0;
	return fac[x]*fv[x-y]%mod*fv[y]%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	f[0]=fac[0]=fac[1]=fv[0]=fv[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=N-5;i++){
		fac[i]=fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		fv[i]=fv[i-1]*inv[i]%mod;
	}
	for(int i=1,x;i<=n;i++){
		cin>>x;
		a[x]++;
	}
	for(int i=N-5;i;i--){
		if(!a[i]) continue;
		g[0b10000]=f[0b00000]+f[0b10000];
		g[0b00100]=f[0b00000]+f[0b00100]*C(a[i]+1,1);
		g[0b00001]=f[0b00000]+f[0b00001];
		g[0b10100]=f[0b00000]*C(a[i]-1,1)+f[0b10000]*C(a[i],1)+f[0b00100]*C(a[i]+1,2)+f[0b10100]*C(a[i]+2,2);
		g[0b10001]=f[0b00000]*C(a[i]-1,1)+f[0b10000]*C(a[i],1)+f[0b00001]*C(a[i],1)+f[0b10001]*C(a[i]+1,1);
		g[0b00101]=f[0b00000]*C(a[i]-1,1)+f[0b00100]*C(a[i]+1,2)+f[0b00001]*C(a[i],1)+f[0b00101]*C(a[i]+2,2);
		g[0b10101]=f[0b00000]*C(a[i]-1,2)+f[0b10000]*C(a[i],2)+f[0b00100]*C(a[i]+1,3)+f[0b00001]*C(a[i],2);
		g[0b10101]+=f[0b10100]*C(a[i]+2,3)+f[0b10001]*C(a[i]+1,2)+f[0b00101]*C(a[i]+2,3)+f[0b10101]*C(a[i]+3,3);
		g[0b11100]=f[0b10100]*C(a[i],1)+f[0b11100];
		g[0b11101]=f[0b10100]*C(a[i],2)+f[0b11100]*C(a[i],1)+f[0b10101]*C(a[i]+1,2)+f[0b11101]*C(a[i]+1,1);
		g[0b11111]=f[0b10101]*C(a[i]-1,1)+f[0b11101]+f[0b10111];
		g[0b00111]=f[0b00101]*C(a[i],1)+f[0b00111];
		g[0b10111]=f[0b00101]*C(a[i],2)+f[0b00111]*C(a[i],1)+f[0b10101]*C(a[i]+1,2)+f[0b10111]*C(a[i]+1,1);
		for(int j=0;j<(1<<5);j++) f[j]=g[j]%mod;
	}
	cout<<f[(1<<5)-1];
    return 0;
}

题解：P14534 [RMI 2018] W

文章操作

相关推荐

评论

题解：P14534 [RMI 2018] W