题目描述

求$1~n$的序列,满足一个数与其相邻树的差的绝对值不等与1的方案数。

输入格式

一个数$n$。

输出格式

一个非负整数,表示方案数对$7777777$取模。

样例输入

4

样例输出

2

数据范围

对于$100\%$的数据,满足$1≤N ≤ 1000$。

菜鸡的咆哮

看第一眼感觉和$windy$数有点像....但是数据....

好的我还是太菜了(手动狗头。

其实正解也是$DP$。

由于从前向后一个一个加入情况太过复杂,

所以我们可以考虑从小到大一个个加入。

我们定义$f[i][j][0/1]$表示$1-i$组成的序列中,有$j$对不合法的方案数。

其中第三维$0$表示$i-1$与$i$不相邻,$1$表示$i-1$与$i$相邻。

定义了状态,我们开始分析状态转移方程:

$f[i][j][1]$

​ 因为$i$与$i-1$相邻,所以$i$只有两个地方可插。

​ ①若$i-2$与$i-1$相邻:

​ 当$i$插在$i-2$与$i-1$之间时,非法数不变,即$f[i-1][j][1]\times 1$。

​ 当$i$插在$i-1$不与$i-2$相邻的一边时,非法数加$1$,即$f[i-1][j-1][1]\times 1$。

​ ②若$i-2$与$i-1$不相邻:

​ 当$i$插在$i-1$两边时,非法数都加$1$,即$f[i-1][j-1][0]\times 2$

$f[i][j][0]$

​ ①若$i-2$与$i-1$相邻:

​ 当$i$插在不合法对之间时,非法数减$1$,即$f[i-1][j+1][1]\times j$(不能插在$i-2$与$i-1$中)。

​ 当$i$插在合法对之间时,非法数不变,即$f[i-1][j][1]\times (i-1+1-j-1)$(不能插在$i-1$合法的一旁)。

​ ②若$i-2$与$i-1$不相邻:

​ 当$i$插在不合法对之间时,非法数减$1$,即$f[i-1][j+1][0]\times (j+1)$。

​ 当$i$插在合法对之间时,非法数不变,即$f[i-1][j][0]\times (i-1+1-j-2)$(不能插在$i-1$旁)。

考场上我是想不出来怎么诡异的状态.....太菜了太菜了$QAQ$

代码

#include<bits/stdc++.h>
#define ll long long
#define mod 7777777
#define maxn 105
using namespace std;
int n;
ll f[maxn][maxn][2];
int main(){
    scanf("%d",&n);
    f[1][0][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=n;j++){
            f[i][j][1]=(f[i-1][j][1]+f[i-1][j-1][1]+f[i-1][j-1][0]*2)%mod;
            f[i][j][0]=(f[i-1][j+1][1]*j+f[i-1][j][1]*(i-j-1))%mod;
            f[i][j][0]+=(f[i-1][j+1][0]*(j+1)+f[i-1][j][0]*(i-j-2))%mod;
        }
    }
    printf("%lld\n",f[n][0][0]);
    return 0;
}