题解：P9418 [POI 2021/2022 R1] Impreza krasnali

· · 题解

前言

模拟赛T1，正解是DP但是很显然本蒟蒻不会，所以搞了个神秘做法。

题意

有一个 1 \sim n 的排列 P。现在给定一个长度为 n，值域为 [1,n] 的序列 A，其中 A_i 表示 P_{i-1} 或 P_{i+1} 为 A_i。

特别的，P_2 总是等于 A_i，P_{n-1} 总是等于 A_n。

问你有多少个 P 满足 A 对其的限制，对 10^9+7 取模。

1 \le n \le 10^5

题解

先判断掉一些不合法的情况：

现在来依次看看这些不合法的情况。

第一种情况很显然，直接讨论第二种。

如果有两个相同的数 P_{i-1} 和 P_{i+1}，我们就可以确定 A_i=P_{i-1}。

反之不合法。

对于第三种，因为我们可以结合已经确定的 A_2 和 A_{n-1} 来进一步确定中间的 A_i，如果 n 是奇数的话，拓展到中间时就会矛盾。

举个例子

P: 1 2 3 4 5
A: ? 1 ? 5 ?

我们发现对于 P_3=3 来说，既没有 A_2=3，也没有 A_4=3。所以矛盾了。

在这个手摸的过程中我们还发现如果 P_i=i 且 n 为偶数时有且仅有一种排列满足。

我们先将可以确定的数确定下来。因为每一次确定的数都可能对前/后的数有影响，所以我们没有办法通过顺序扫一遍完成这个操作。

我这里是使用了两个指针 l,r ，不断往前推来进行互相更新。

现在我们再来思考怎么样计算答案。

这里给出一组样例：

10
3 1 3 4 9 8 10 6 2 6

在这个样例中，能确定的数如下

? 3 ? ? ? ? ? ? 6 ?

把这两个序列结合起来看，如图。

一个数箭头指向的两个位置指的是这两个位置中一定要有一个位置的值和它相等。

观察发现，红色箭头与蓝色箭头是相互独立的，所以我们可以分开考虑。

单独拎出来的话长这样。

假设另外加入的数为 x，情况如下

加入的 x，指在 A 中没有出现过的数，即没有限制。

x 1 4 8
1 x 4 8
1 4 x 8
1 4 8 x

实际上就是把 x 插入每两个数之间。假设这段 0 有 tot 个，就会有 tot 种方案。

分别单/偶数下标遍历一遍找到每一个 tot 即可。

根据乘法原理，每一段 0 之间不互相影响，需要乘起来。

又因为我们要给每一段 0 分配一个 x，假设有 cnt 个数没有出现过，分配的方案即为 cnt!。

答案为

cnt! \prod tot

时间复杂度 \mathcal{O}(n)。

talk is cheap,show me the code!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x)    cerr<<"in "<<x<<"!!!\n";
const int N=1e5+5,mod=1e9+7;
int n;
int h[N],a[N];
bool used[N];
int bk[N]; 
int ans=1;
bool deal(int x){//推导能确定的 A_i。
    if(a[x-1]&&a[x+1]&&a[x-1]!=h[x]&&a[x+1]!=h[x])  return 1;
    if(a[x-1]||a[x+1]){
        if(a[x-1]&&a[x-1]!=h[x])    a[x+1]=h[x];
        else a[x-1]=h[x];
    }
    return 0;
}
signed main(){
    scanf("%d",&n);
    bool fl=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        bk[h[i]]++;
        if(bk[h[i]]>2){
            printf("0\n");
            return 0;
        }
        if(h[i]!=i) fl=0;
    }
    if(fl){//判断 P_i=i 的情况。
        printf("%d\n",!(n&1));
        return 0;
    }
    for(int i=3;i<=n-2;i++){
        if(bk[h[i]]==2){
            if(h[i]!=h[i-2]&&h[i]!=h[i+2]){//判断距离。
                printf("0\n");
                return 0;
            }
        }
    }
    for(int i=2;i<=n-1;i++){
        if(h[i-1]==h[i+1]){//确定那种 P_{i-1} 和 P_{i+1} 都确定的。
            a[i]=h[i-1];
            if(used[a[i]]){
                printf("0\n");
                return 0;
            }
            used[a[i]]=1;
        }
    }
    if((a[2]&&a[2]!=h[1])||(a[n-1]&&a[n-1]!=h[n])){
        printf("0\n");
        return 0;
    }
    a[2]=h[1],a[n-1]=h[n];
    used[a[2]]=used[a[n-1]]=1;
    int l=3,r=n-2;
    while(l<n||r>1){//确定能确定的 A_i。
        while(l<n&&used[h[l]])  l++;
        while(r>1&&used[h[r]])  r--;
        if(l<n&&deal(l)){
            printf("0\n");
            return 0;
        }
        if(r>1&&deal(r)){
            printf("0\n");
            return 0;
        }
        if(l<n) l++;
        if(r>1) r--;
    }
    int qwq=0;
    for(int i=1;i<=n;i++){
        if(!bk[i])  qwq++;//找出没有出现过的数的个数。
    }
    int tot=0;
    for(int i=1;i<=n;i+=2){//单数下标
        if(!a[i])   tot++;
        else{
            if(tot) ans=1ll*ans*tot%mod;
            tot=0;
        }
    }
    if(tot) ans=1ll*ans*tot%mod;
    tot=0;
    for(int i=2;i<=n;i+=2){//偶数下标
        if(!a[i])   tot++;
        else{
            if(tot) ans=1ll*ans*tot%mod;
            tot=0;
        }
    }
    if(tot) ans=1ll*ans*tot%mod;
    if(qwq){
        for(int i=1;i<=qwq;i++) ans=1ll*ans*i%mod;//阶乘
    }
    printf("%d\n",ans);
    return 0;
}
/*//一些样例
10 
3 1 3 4 9 8 10 6 2 6 
*/
/*
5
3 2 3 2 4
*/