题目概述

求不存在 $|a_i-a_{i+1}|=1,i<n$ 的 $n$ 的排列 $\{a_n\}$ 的个数。

解题报告

定义 $f_{i,j,0/1}$ 表示前 $i$ 个数，有 $j$ 个数相邻，其中 $i$ 是否和 $i-1$ 相邻的方案数，讨论一下就可以转移了。

这种套路好像被称为加强条件……就是自行加一个有 $m$ 个数相邻这个条件，发现更容易想。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000,MOD=7777777;

int n,f[maxn+5][maxn+5][2];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);f[1][0][0]=1;
    for (int i=2;i<=n;i++)
        for (int j=0,F;j<i;j++){
            if (F=f[i-1][j][0]){
                f[i][j+1][1]=ADD(f[i][j+1][1],F<<1);
                if (i-2-j>0) f[i][j][0]=ADD(f[i][j][0],MUL(F,i-2-j));
                if (j) f[i][j-1][0]=ADD(f[i][j-1][0],MUL(F,j));
            }
            if (F=f[i-1][j][1]){
                f[i][j][1]=ADD(f[i][j][1],F);
                f[i][j+1][1]=ADD(f[i][j+1][1],F);
                if (i-1-j>0) f[i][j][0]=ADD(f[i][j][0],MUL(F,i-1-j));
                if (j) f[i][j-1][0]=ADD(f[i][j-1][0],MUL(F,j-1));
            }
        }
    printf("%d\n",f[n][0][0]);return 0;
}