P9418 题解

船酱魔王 · 2024-08-30 18:32:22 · 题解

题意回顾

给定一个长度为 n 的序列 p ，你需要找出有多少个排列 a 满足 \forall 1 \le i \le n ，有 p_i = a_{i-1} 或 p_i=a_{i+1} 。

分析

当一个数字出现三次及以上或出现两次且两次位置差不为 2 时，无解。

在把出现两次的位置确定好后，我们考虑把每个仅出现一次的 p_i 分配给 a_{i-1} 或 a_{i+1} ，因为每个位置仅出现最多一次无重复且影响范围很小所以考虑设计动态规划。

定义 dp_{i,0/1,0/1} 表示对于位置 i 及之前所有出现一次的 p_i 都被分配完后， a_i 和 a_{i+1} 是否分配了值。我们分类讨论该位置是否属于出现两次的位置和该位置是否还可以被分配进行转移即可。

最后我们要把空位置填上所有未在 p_i 中出现过的值，乘上全排列即可。

时间复杂度 O(n) ，分类讨论详见代码。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
int a[N];
int buc[N];
int typ[N], dne[N];
int dp[N][2][2];
int main() {
    scanf("%d", &n);
    bool ok = true;
    int o = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(buc[a[i]] == 0) buc[a[i]] = i;
        else if(buc[a[i]] > 0) {
            if(buc[a[i]] != i - 2) ok = false;
            buc[a[i]] = -1;
            o++, dne[i - 1] = 1, typ[i - 2] = typ[i] = 1;
        } else ok = false;
    }
    if(!ok) {
        puts("0");
        return 0;
    }
    //for(int i = 1; i <= n; i++) cout << dne[i] << typ[i] << endl;
    dp[1][0][1] = 1;
    for(int i = 2; i <= n; i++) {
        if(typ[i]) {
            dp[i][1][dne[i + 1]] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % mod;
            if(!dne[i]) dp[i][0][dne[i + 1]] = (dp[i - 1][0][0] + dp[i - 1][1][0]) % mod;
        } else {
            if(!dne[i]) dp[i][0][0] = dp[i - 1][0][0], dp[i][0][1] = (dp[i - 1][1][0] + dp[i - 1][0][0]) % mod,
                dp[i][1][0] = dp[i - 1][0][1], dp[i][1][1] = (dp[i - 1][1][1] + dp[i - 1][0][1]) % mod;
            else dp[i][1][0] = dp[i - 1][0][1], dp[i][1][1] = (dp[i - 1][0][1] + dp[i - 1][1][1]) % mod;
        }
        //cout << i << " " << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << endl;
    }
    int ans = (dp[n][1][0] + dp[n][0][0]) % mod;
    for(int i = 1; i <= o; i++) ans = (long long)ans * i % mod;
    printf("%d\n", ans);
    return 0;
}