[BZOJ4321] queue2
题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=4321
Solution
这种题一般套路就是从小到大插入然后( m dp)。
设(f_{i,j,0/1})表示现在插入了前(i)个数，有(j)组相邻的数，并且(i)和(i-1)有没有相邻的方案数，(0/1)是方便转移。
那么转移需要分类讨论下：
我们先转移较简单的(f_{i,j,1})：
[f_{i,j,1}=f_{i-1,j-1,1}+f_{i-1,j,1}+2f_{i-1,j-1,0}
]
这就是枚举填在(i-1)的两侧。
(f_{i,j,0})的转移有点复杂：
[f_{i,j,0}=f_{i-1,j+1,1}cdot j+f_{i-1,j+1,0}cdot (j+1)
]
这一部分是让(i)插在两个相邻的之间，那么相邻的数量减少(1)。
[f_{i,j,0}=f_{i-1,j,0}cdot (i-j-2)+f_{i-1,j,1}cdot (i-j-1)
]
这部分是枚举插在其他地方，那么相邻的数量不变，注意不能插在(i-1)的两侧。
复杂度(O(n^2))。
顺便说一下这个数列在( m OEIS)上有：http://oeis.org/A002464
并且给出了一个(O(n))的递推式：
[a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).
]
但是我并没有搞明白是为什么...
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 7777777;
int n,f[1002][1002][2];
int main() {
read(n);f[0][0][0]=1,f[1][0][0]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<i;j++) {
f[i][j][1]=(f[i-1][j][1]+f[i-1][j-1][1]+f[i-1][j-1][0]*2)%mod;
f[i][j][0]=(1ll*f[i-1][j+1][1]*j+1ll*f[i-1][j+1][0]*(j+1))%mod;
f[i][j][0]=(1ll*f[i-1][j][0]*(i-j-2)+1ll*f[i-1][j][1]*(i-j-1)+f[i][j][0])%mod;
}
write(f[n][0][0]);
return 0;
}