自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 22:48:11，当前版本为作者最后更新于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;
}