BZOJ4321: queue2

Description

n 个沙茶，被编号 1~n。排完队之后，每个沙茶希望，自己的相邻的两

人只要无一个人的编号和自己的编号相差为 1（+1 或-1）就行；

现在想知道，存在多少方案满足沙茶们如此不苛刻的条件。

Input

只有一行且为用空格隔开的一个正整数 N，其中 100%的数据满足 1≤N ≤ 1000;

Output

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

Sample Input

Sample Output

2
样例解释：有两种方案 2 4 1 3 和 3 1 4 2

考虑插入法：

设f[i][j][k]表示已经得到了[1,i]的排列，产生了j对相差为1的沙发，并且i的旁边是否有i-1

现在考虑将i+1插入i的旁边没有i-1的排列，分为三种转移：

1.将i+1放在i的两边，相差为1的沙发对数+1，有两种插法，f[i+1][j+1][1]+=2*f[i][j][0]

2.将i+1放在原有的一对相差为1的沙发之间，相差为1的沙发对数-1，有j种插法，f[i+1][j-1][1]+=j*f[i][j][0]

3.将i+1放在其他地方，相差为1的沙发对数不变，有i+1-2-(j)=i-j-1有插法，f[i+1][j][0]+=(i-j-1)*f[i][j][0]

将i+1插入i的旁边有i-1的排列对应有4种转移，类似就不写了。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int mod=7777777;
const int maxn=1010;
ll f[maxn][maxn][2];
int main() {
    int n=read();
    f[1][0][0]=1;
    rep(i,1,n) rep(j,0,i-1) {
        (f[i+1][j+1][1]+=2*f[i][j][0])%=mod;
        (f[i+1][j-1][0]+=j*f[i][j][0])%=mod;
        (f[i+1][j][0]+=(i-j-1)*f[i][j][0])%=mod;
        (f[i+1][j+1][1]+=f[i][j][1])%=mod;
        (f[i+1][j][1]+=f[i][j][1])%=mod;
        (f[i+1][j-1][0]+=(j-1)*f[i][j][1])%=mod;
        (f[i+1][j][0]+=(i-j)*f[i][j][1])%=mod;
    }
    printf("%lld
",f[n][0][0]%mod);
    return 0;
}

View Code