queue2
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 sol:超有趣的dp,但自己就是想不出来,然后翻了题解考虑把n个数字按1~n一个个填过去,而不是按照位置1~n一个个填数字
把数字按照1~n排序,
dp[i][j][0]表示用到i,有j对数相差为1,i与i-1不相邻
dp[i][j][1]表示用到i,有j对数相差为1,i与i-1相邻
题解 https://blog.csdn.net/yjschaf/article/details/72453712
/*
把数字按照1~n排序,
dp[i][j][0]表示用到i,有j对数相差为1,i与i-1不相邻
dp[i][j][1]表示用到i,有j对数相差为1,i与i-1相邻
题解 https://blog.csdn.net/yjschaf/article/details/72453712
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const ll N=,Mod=;
ll n,dp[N][N][];
inline void Ad(ll &x,ll y)
{
x+=y; x-=(x>=Mod)?Mod:;
}
int main()
{
int i,j,k;
R(n);
dp[][][]=;
for(i=;i<=n;i++)
{
for(j=;j<=i-;j++)
{
Ad(dp[i][j][],dp[i-][j+][]*(j+)%Mod);
Ad(dp[i][j][],dp[i-][j+][]*j%Mod);
Ad(dp[i][j][],dp[i-][j][]*(i-j-)%Mod);
Ad(dp[i][j][],dp[i-][j][]*(i-j-)%Mod); Ad(dp[i][j][],dp[i-][j-][]*%Mod);
Ad(dp[i][j][],dp[i-][j-][]);
Ad(dp[i][j][],dp[i-][j][]);
}
}
Wl(dp[n][][]);
return ;
}
/*
input
4
output
2
*/