ARC146E 题解

First Post:

Last Update:

因为之前做过水淹笛卡尔树的题（ARC117E），一眼看出了 DP 状态，后面就不会了，题解告诉我第二维有效状态不超过 个，人有点麻。也是没有仔细思考的缘故。

按值域从小到大 DP，每次考虑插入 个 。

假设已经插入的数形成了 个连续段，显然，除了最左和最右的连续段，剩下的段的两端都是 （不然就无法满足相邻位置差为 ）

这提示我们最左边和最右边有一些特殊性。

事实上，如果最左边是 ，那么当前的 还可以插到左边，否则不行。右边同理。

那么我们设 表示当前做到 ，一共形成了 个连续段，最左边是不是 ，最右边是不是 。

转移有两个方面，第一是 的变化，第二是转移系数。

如果我们想在最左和最右都填上 的话，我们首先会把 个 填在每个连续段的两侧，然后剩余的 个 会贡献 个连续段，总段数就是 。

如果想在某几侧不填上 的话，道理是一样的，将结果 或 即可。

考察转移系数，还是以 为例，这时一共会有 个空隙，每个空隙都必须有数，这就是个插板法，方案数为 。

直接这么做，看上去可以达到平方复杂度，但是，我们发现 的变化方法较为单一，它只有可能在每轮中由 变为 ，或在 或 变化时加上 或者 。

我们处理出 表示如果前 轮，每轮都在两边放数，会有几个连续段（显然有 ）。

那么 的取值只会在 附近，取 即可。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,a[N],cur[N];
int dp[N][7][2][2];
int fac[N],ifac[N];
inline void init(int n)
{
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[1] = 1;
	for(int i = 2;i <= n;i++) ifac[i] = 1ll * ifac[P % i] * (P - P / i) % P;
	ifac[0] = 1;
	for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	cur[1] = a[1];
	dp[1][2][1][1] = 1;
	init(2e5);

	for(int i = 2;i <= n;i++)
	{
		cur[i] = a[i] - cur[i - 1]; // 如果两边都不放 i,会有多少对相邻的 i
		for(int j = 0;j <= 6;j++)
			for(int u = 0;u <= 1;u++)
			for(int v = 0;v <= 1;v++)
			if(dp[i - 1][j][u][v])
			{
				for(int p = 0;p <= u;p++)
				for(int q = 0;q <= v;q++)
				{
					int val = dp[i - 1][j][u][v],c = cur[i - 1] + j - 2; // c 表示实际有多少对相邻的 i
					if(p == 0 && q == 0)
						Plus(dp[i][6 - j][p][q],1ll * val * C(a[i] - 1,c - 2) % P); // 4 - j : a - 原段数 + 2
					if(p == 1 && q == 1 && j <= 4)
						Plus(dp[i][4 - j][p][q],1ll * val * C(a[i] - 1,c) % P); // 2 - j: a - 原段数
					if(p + q == 1 && j <= 5)
						Plus(dp[i][5 - j][p][q],1ll * val * C(a[i] - 1,c - 1) % P);
				}
			}
		for(int j = 0;j <= 6;j++)
			for(int u = 0;u <= 1;u++)
				for(int v = 0;v <= 1;v++)
					printf("f[%d][%d][%d][%d]=%d\n",i,cur[i] + j - 2,u,v,dp[i][j][u][v]);
	}
	int ans = 0;
	for(int i = 0;i <= 6;i++)
		for(int u = 0;u <= 1;u++)
			for(int v = 0;v <= 1;v++)
				if(cur[n] + i - 2 == 1)
					Plus(ans,dp[n][i][u][v]);
	cout << ans << endl;
	return 0;
}
≡