每日归档： 2018年10月18日

这一题的题面很复杂，但形式化地概括则很简单：

对于一个长度为n的全排列，求出其中有多少排列A满足，对于任意i属于n，$$(A_{i}-A{i-1})*(A_{i}-A_{i+1})>=0;$$

然后我们观察排列的特点，我们可以发现，对于排列A中的一个元素\(A_{i}\)，我们可以发现，如果\(A_{i}\)是山峰，那么将\(A_{i}\)的值无论添加多少，都不改变这个序列的可居住性；对于山谷，则反之。
于是，我们可以发现，一个合法的排列，如果我们要在它末尾添上一个数让它形成一个新的合法排列，对于除了最后一个数以及这个数是属于山峰以及山谷以外，我们不关心其他的属性。
因此我们可以用\(f[i][j][k]\)表达当前长度为i，最后一个数为j，最后一个数的状态为k的时候的状态数。其中k==0表示山谷，而k==1表示山峰。
则很容易可以得到状态转移方程：
$$f[i][j][k]+=f[i-1][l][k\ xor\ 1](k?(0<l<=j-1):(j-1<l<=i))$$
但是这样子的复杂度是N^3的，对于4200的数据显然是不能通过的。这时候考虑优化。
我们发现求和的东西是一段区间，因此我们可以考虑前缀优化。
这样子就将复杂度从\(n^3\)降低到了\(n^2\)，于是可以通过。
但是这样子需要的空间是3E7的，对于128MB的空间是非常危险的，这时候考虑滚动数组优化，这样是可以通过的。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,p,f[4205][2],pre[4205][2];
void init(){
    scanf("%lld%lld",&n,&p);
    int l,r;
    f[1][1]=f[1][0]=pre[1][0]=pre[1][1]=1;
    for(int i=2;i<=n;++i){
        pre[i][0]=pre[i-1][0],pre[i][1]=pre[i-1][1];
        for(int j=1;j<=i;++j){
            for(int k=0;k<=1;++k){
                l=k?0:j-1;
                r=k?j-1:i;
                f[j][k]=(pre[r][k^1]-pre[l][k^1]+p)%p;
//                printf("(%d,%d)[%d,%d]%lld|",l,r,pre[l][k^1],pre[r][k^1],f[j][k]);
            }
//            printf(" ");
        }
        pre[0][0]=pre[0][1]=0;
        for(int j=1;j<=i;++j){
            pre[j][0]=(pre[j-1][0]+f[j][0])%p;
            pre[j][1]=(pre[j-1][1]+f[j][1])%p;
        }
//        puts("");
    }
    long long ans=(pre[n][0]+pre[n][1])%p;
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
}

 

Q：为什么这个方程不会重复统计呢？
如果只关心上一个元素的大小，排列中的元素可能重复出现了。

A：不会重复统计，感性证明如下：

首先我们假定对于上一个A，使得：

$$ |A|==i-1 $$

并没有重复统计。
那么我们插入一个新的元素\(i\)时，产生的新序列必然是 本质不同 的。
我们对于\(A_{i-1}\)是山峰和山谷分别讨论。
如果\(A_{i-1}\)是山峰，那么新插入的元素，必然比\(A_{i-1}\)小，并且一定是由将序列中大等于【某个小于等于\(A_{i-1}\)的一个数\(l\)】的所有数提升一，然后将新插入的元素定义为\(l\)。
这时候，\(i-1\)位上的数是\(A_{i-1}+1\)，而\(i\)位上的数则是\(l\)。
在这种情况下，最后两位是\(A_{i-1}+1\)与\(l\)。显然对于每一个本来已有的\(A_{i-1}\)，它们在新的序列中都会加且仅加1。
这样，所有新增的组合的最后两位都是 本质不同 的，因此序列本质不同。
对于山谷，情况类同于山峰，同样可以证明不会产生重复的后两位，进而不会产生本质相同的数列。

而对于 $$|A|==1$$ ，结果显然是1，没有重复统计。
从而归纳得出全部都没有重复统计。