题解：P12917 [POI 2021/2022 R3] 小矮人派对 2 / Impreza krasnali 2

· · 题解

细节题，转移并不难，难点在于状态的设计。

设 h 中出现过不同的数的数量为 c，原问题等价于把这 c 个数放在 n 个位置上，有些位置空着不放，且 i 和放 a_i 的位置距离不超过 1 的方案数，最后再乘上 (n-c)! 就是答案了。

容易观察到有如下性质：

那么就可以考虑 dp，设只考虑前 i 个的方案数为 f_{i,0/1/2/3/4}，有如下几种情况：

那么就可以开始转移了，这个要根据 a_i 的位置和数量分类讨论来转移：

  1. $f_{i,0}=f_{i-1,2}$；
  2. $f_{i,0}=f_{i-1,1}$， $f_{i,1}=f_{i-1,3}$；
  3. $f_{i,0}=f_{i-1,2}$， $f_{i,2}=f_{i-1,3}+f_{i-1,4}$；
  4. $f_{i,0}=f_{i-1,0}$， $f_{i,1}=f_{i-1,4}$， $f_{i,2}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}$， $f_{i,3}=f_{i-1,3}+f_{i-1,4}$， $f_{i,4}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}$。

最终答案 (n-c)!(f_{n,0}+f_{n,1}+f_{n,2})，最开始的时候特判一下无解的情况，那么这题就做完了，时间复杂度 \mathcal O(n)。


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,a[N],cnt[N],lst[N],f[N][5],sum,ans;
vector<int>vec[N];
void add(int &x,int v){
    x+=v;
    if(x>=mod) x-=mod;
}
void gg(){
    cout<<"0\n";
    exit(0);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!cnt[a[i]]) sum++;
        cnt[a[i]]++;
        vec[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]>3) gg();
        if(cnt[i]==3&&(vec[i][2]-vec[i][1]>1||vec[i][1]-vec[i][0]>1)) gg();
        if(cnt[i]==2&&vec[i][1]-vec[i][0]>2) gg();
    }
    f[1][2]=f[1][4]=1;
    for(int i=2;i<=n;i++)
        if(i>=3&&a[i-2]==a[i-1]&&a[i-1]==a[i]) f[i][0]=f[i-1][2];
        else if(i>=3&&a[i-2]==a[i]){
            f[i][0]=f[i-1][1];
            f[i][1]=f[i-1][3];
        }
        else if(a[i-1]==a[i]){
            f[i][0]=f[i-1][2];
            f[i][2]=f[i-1][3];add(f[i][2],f[i-1][4]);
        }
        else{
            f[i][0]=f[i-1][0];
            f[i][1]=f[i-1][4];
            f[i][2]=f[i-1][1];add(f[i][2],f[i-1][0]);add(f[i][2],f[i-1][2]);
            f[i][3]=f[i-1][3];add(f[i][3],f[i-1][4]);
            f[i][4]=f[i-1][0];add(f[i][4],f[i-1][1]);add(f[i][4],f[i-1][2]);
        }
    ans=f[n][0];add(ans,f[n][1]);add(ans,f[n][2]);
    for(int i=1;i<=n-sum;i++) ans=1ll*ans*i%mod;
    cout<<ans<<'\n';
    return 0;
}