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 ;
}