4321: queue2

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 475  Solved: 287

[][][]

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

 

 

设f[i][j][k]为排完1-i之后，有j对相邻位置差一，并且i是否和i-1相邻的方案数。

然后随便推一推转移就好了，这里稍微提一下怎么推转移，至于最后的式子看代码就好了。

首先，我们看一下f[i][j][0]可以转移到哪些状态：

1.我们在i的两边放i+1，都会让差一的相邻位置+1。

所以f[i+1][j+1][1]+=2*f[i][j][0]。

2.我们在j对差一的相邻位置中间放i+1，都会让差一的相邻位置-1。

并且因为i于i-1不相邻，所以j对里不用减去，并且放完之后i+1和i不相邻，所以就是：

f[i+1][j-1][0]+=j*f[i][j][0]。

3.在剩下的i-j-1个空挡里放，不仅i和i+1不相邻，并且相邻差一的不会增多，

所以f[i+1][j][0]+=(i-j-1)*f[i][j][0]。

 

f[i][j][1]的情况类似，推一下就好了。

 

/**************************************************************	Problem: 4321	User: JYYHH	Language: C++	Result: Accepted	Time:484 ms	Memory:9180 kb****************************************************************/#include
      
       #define ll long long#define maxn 1005using namespace std;const int ha=7777777;int f[maxn][maxn][2];int n;inline int add(int x,int y){	x+=y;	return x>=ha?x-ha:x;}inline void dp(){	f[1][0][0]=1;	for(int i=1;i
       
        >n;	dp();	cout<
        
         <