题解：P14534 [RMI 2018] W

· · 题解

这种排列计数题，一般从左到右不好 dp，转而考虑按值从大到小 dp（类似套路有 P9197 等）。把 W 拆成五个极值点，一共有 2^5 种状态，用 0 和 1 表示极值点的确定与否。只需要会怎么转移，就做完了，本质是自动机，但是因为有效状态较少，所以采用手动机。

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

举点例子，假设状态是 10100，那么：

  1. 状态 00000 贡献 {x-1\choose 1}，意义即为将 x 个数分为两段且不能为空。

  2. 状态 10000 贡献 {x\choose 1}，意义即为将 x 分为两段，一段不能为空。

  3. 状态 00100 贡献 x+1\choose 2，意义即为将 x 分为三段，一段不能为空。因为中间的极值点能往左右两边扩展。

  4. 状态 10100 贡献 x+2\choose 2，意义即为将 x 分为三段。

假设状态是 11101，那么：

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

  2. 状态 11100 贡献 {x\choose 1}，意义即为将 x 分为两段，一段不能为空。

  3. 状态 10101 贡献 x+1\choose 2，意义即为将 x 分为三段，一段不能为空。

  4. 状态 11101 贡献 x+1\choose 1，意义即为将 x 分为两段。

其余情况类似，可参考代码。最终时间复杂度为 O(n)，带一点常数。

#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;
}