【luogu SP7685】FLWRS - Flowers（DP）（容斥）

FLWRS - Flowers

题目链接：luogu SP7685

题目大意

给你模数 m，问你有多少个长度为 n 的排列满足相邻两个差不为 1。

思路

首先一个简单的想法是容斥。
那有 $n$ 对相邻的不满足，就乘上 $(-1{)}^n$。

考虑如何统计，首先考虑不看数，就看每个位置是否会不满足。
于是能设计出一个 DP 为 $f_{i,j,0/1}$ 是前 $i$ 个数，已经有 $j$ 对地方不满足，当前位置跟前面满足 / 不满足。

然后第一次不满足你要安排顺序，顺着还是逆着，那一开始固定了不满足的一段后面都固定了。

然后你考虑对于 $f_{n,i,0/1}$，它怎么给答案进行贡献。
首先容斥系数 $-1$（当然你可以放在 DP 里面）。
另外就是你要安排一下给的数，考虑怎么安排：
发现我们可以把每段连续的不合法捆成一个，那因为你 DP 里面固定了顺序，所以你可以直接可以用左端点或者右端点代表它。
那我们只需要找到它们之间的相对大小，所以我们只需要乘上 $(n-i)!$ 即可。

代码

#include
#define ll long long

using namespace std;

const int N = 2005;
int n;
ll mo, f[N][N][2], jc[N];

int main() {
	scanf("%d %lld", &n, &mo);
	
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo;
	
	f[1][0][0] = 1;
	for (int i = 2; i <= n; i++) {
		f[i][0][0] = f[i - 1][0][0];
		for (int j = 1; j <= i; j++) {
			f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mo;
			f[i][j][1] = (mo - (f[i - 1][j - 1][0] * 2 + f[i - 1][j - 1][1]) % mo) % mo;
		}
	}
	
	ll ans = 0;
	for (int i = 0; i < n; i++)
		(ans += jc[n - i] * (f[n][i][0] + f[n][i][1]) % mo) %= mo;
	printf("%lld", ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30