bzoj4321 queue2

http://www.elijahqi.win/archives/3716

Description

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

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

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

Input

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

Output

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

Sample Input

4

Sample Output

2

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

设dp[i][j][0/1]分别表示 已经插入1~i的排列 有j个数相邻 0,1分别表示最后i,i-1是否相邻

那么考虑dp[i][j][1]的情况 我们可以把插入i-1,i-2相邻i-1与i-2之间 不会增加j 反之会增加1

i-1 i-2不相邻 那么随便插在i-1两边都会+1

考虑dp[i][j][0]的情况

i-1,i-2相邻 那么随便插入除了他们的任意一对都会-1

反之 要减去他们这一对

如果不插在i-1,i-2这中间 （当i-1,i-2恰好相邻也可以插在中间）也不去破坏其他相邻的 那么则有i-j-1种插入的方法

反之如果i-1 i-2不相邻 那么只有i-j-2个地方可以插入

#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
inline char gc(){
    static char now[<<],*S,*T;
    if (T==S){T=(S=now)+fread(now,,<<,stdin);if(T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=,f=;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-;ch=gc();}
    while(isdigit(ch)) x=x*+ch-'0',ch=gc();
    return x*f;
}
const int mod=;
const int N=+;
inline void inc(int &x,int v){x=x+v>=mod?x+v-mod:x+v;}
int dp[N][N][],n;
int main(){
    freopen("bzoj4321.in","r",stdin);
    n=read();dp[][][]=;
    for (int i=;i<=n;++i){
        for (int j=;j<i;++j){
            inc(dp[i][j][],dp[i-][j-][]);inc(dp[i][j][],(dp[i-][j-][]<<)%mod);
            inc(dp[i][j][],dp[i-][j][]);inc(dp[i][j][],(ll)dp[i-][j+][]*j%mod);
            inc(dp[i][j][],(ll)dp[i-][j+][]*(j+)%mod);
            inc(dp[i][j][],(ll)dp[i-][j][]*(i-j-)%mod);
            inc(dp[i][j][],(ll)dp[i-][j][]*(i-j-)%mod);
        }
    }printf("%d\n",dp[n][][]);
    return ;
}