P12917

· · 题解

做法

转化题意为，把 h_i 中出现的数放在合法位置的方案数。若有 m 个，结果再乘上 (n-m)!（表示其余的随便填），就是最终答案。

发现 h_i 放置的位置不能离 i 距离超过 1。但即使距离为 1，这也会导致常规的 DP 出现后效性。于是考虑增加状态。

对于一个 h_i，在不考虑特殊情况时。它可以放在 i-1,i,i+1 共计 3 个位置。当放在 i-1,i+1 时，就要关注 h_{i-1} 摆放情况。于是定义。

考虑转移。

如果 h_{i-2}=h_{i-1}=h_i。那么说明 h_i 只能放在 i-1 这个位置，那么 i 这个位置就不可能放 h_{i-1}。

f_{i,0}=f_{i-1,2}

如果 h_{i-2}=h_i 但 h_{i-1}\ne h_i。虽然 h_i 还是只能放在 i-1 这个位置。但是 h_{i-1} 的值就可以考虑放置位置。i-2 放 h_{i-1} 和 i 放 h_i 两种情况，分别对应。

f_{i,0}=f_{i-1,1}\\ f_{i,1}=f_{i-1,3}\\

如果 h_{i-1}=h_i 但 h_{i-2}\ne h_i。那么 h_i 就可以放在 i,i-1 两个位置。对于 i，就有 h_i 放在左边 i-1 和原位 i 两种情况。如果放在原位，那么 i-1 就有两种不放 i 这个位置的状态可以转移。

f_{i,0}=f_{i-1,2}\\ f_{i,2}=f_{i-1,3}+f_{i-1,4}\\

对于一般情况。

对于 f_{i,0}，它不 h_i 不放在 i，空出这个位置。那么空出 i-1 这个位置的状态只有 f_{i-1,0}。

f_{i,0}=f_{i-1,0}

对于 f_{i,1}，h_{i-1} 要提前放在 i 这个位置并且 i-1 这个位置要空出来，对应的状态就是 f_{i-1,4}。

f_{i,1}=f_{i-1,4}

对于 f_{i,2}，只要 h_{i-1} 没有提前放在 i 这个位置的状态就都可以转移。

f_{i,2}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}

对于 f_{i,3}，只要 i 这个位置被 h_{i-1} 提前放置的状态即可。因为这个状态 h_i 是放在 i+1 的。

f_{i,3}=f_{i-1,3}+f_{i-1,4}

对于 f_{i,4}，和 f_{i,2} 一样；只要 h_{i-1} 没有提前放在 i 这个位置的状态就都可以转移。

f_{i,4}=f_{i-1,0}+f_{i-1,1}+f_{i-1,2}

最后初始化 f_{1,2}=f_{1,4}=1，因为 0 这个位置不能讨论其放置情况。特别的，非法情况要单独特判掉。

代码

::::success[Accepted code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
const int mod=1e9+7;
int n,a[N],f[N][5],m;
vector<int>G[N];
/*
f[i][0] 放左，左非右，空出 i 
f[i][1] 放左，左放右
f[i][2] 放中，左非右 
f[i][3] 放右，左放右
f[i][4] 放右，左非右，空出 i 
*/
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(!G[a[i]].size())m++;
        G[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(G[i].size()>3)
        {
            cout<<"0\n";
            return 0;
        }
        if(G[i].size()==3 && (G[i][0]+1!=G[i][1]||G[i][1]+1!=G[i][2]))
        {
            cout<<"0\n";
            return 0;
        }
        if(G[i].size()==2 && G[i][1]-G[i][0]>2)
        {
            cout<<"0\n";
            return 0;
        }
    }

    f[1][2]=f[1][4]=1;
    for(int i=2;i<=n;i++)
    {
        if(i>2)
        {
            if(a[i-2]==a[i]&&a[i-1]==a[i])
            {
                f[i][0]=f[i-1][2];
                continue;
            }
            else if(a[i-2]==a[i])
            {
                f[i][0]=f[i-1][1];//i-2 这个位置放 a[i-1]
                f[i][1]=f[i-1][3];//i  这个位置放 a[i-1] 
                continue;
            }
        }
        if(a[i]==a[i-1])
        {
            f[i][0]=f[i-1][2];
            f[i][2]=(f[i-1][3]+f[i-1][4])%mod;
        }
        else 
        {
            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])%mod;
            f[i][3]=(f[i-1][3]+f[i-1][4])%mod;
            f[i][4]=(f[i-1][0]+f[i-1][1]+f[i-1][2])%mod;
        }
    }
    int ans=(f[n][0]+f[n][1]+f[n][2])%mod;
    for(int i=1;i<=n-m;i++)ans=(ans*i)%mod;
    cout<<ans;
    return 0;
}

::::