CF1474F 题解

First Post:

Last Update:

做的时候没有觉得这是一道找性质题，以至于连突破口都没找到。

其实原序列更一般的序列最大的区别在于，其相邻两项的差只有 或 。说明如果存在 ，那么对于任意 ，都存在一个 使得 。这就是连续函数性质的离散版本。

所以，任何一个 LIS 都是公差为 的等差数列，否则一定可以调整使其变大。

类似地可以证明，所有 LIS 的起点或终点一定在原序列的波峰或波谷上 （即 或 的位置）。如果不在的话，假设终点 满足 ，那么可以将终点调整到 。如果是 ，那可以将其调整到其所属下降区间的最左端，这样一定可以在前面多选一些数，故原方案也是劣的。

那么第一问就好解决了，显然波峰或波谷只可能在给出的每一段的端点。设 表示第 段结尾的数，答案就是 。

设 ，将所有 的二元组提出来按 排序，那么 一定是单调不增的（如果出现了 使得 ，那么 显然比 更大）。另一方面，如果把所有 相同的连续段都一起考虑，设其中最大的 为 ，这些 对应的最小的 为 ，那么区间 显然是互不相交的。所以可以分开处理，最后将每个区间的答案加起来。

现在对于每个区间，我们已经知道了 LIS 的构成就是 。那直接从小往大填。设 表示当前填到了数 ，这个数在第 段的方案数。每次从 转移到 。但是 的规模很大，所以将值域按照 中每一段的端点的值划分为 段，每一段内的转移方程是相同的，用矩阵快速幂优化即可。

时间复杂度 。

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
const int N = 55,P = 998244353;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
typedef long long ll;
struct Mat {
	int a[N][N];
	Mat() { memset(a,0,sizeof a);}
	int * operator [](const int p) { return a[p];}
	Mat operator * (const Mat &rhs) const {
		Mat res;
		for(int i = 0;i < N;i++)
			for(int k = 0;k < N;k++)
				for(int j = 0;j < N;j++)
					Plus(res.a[i][j],1ll * this->a[i][k] * rhs.a[k][j] % P);
		return res;
	}
	void init() {
		for(int i = 0;i < N;i++)
			for(int j = 0;j < N;j++)
				a[i][j] = (i == j);
	}
};
int n,a[N];
ll sum[N];
ll vals[N << 1];
inline int Solve(int l,int r) {
	int len = 0;
	for(int i = l + 1;i <= r;i++) {
		ll L = sum[i - 1] + (a[i] > 0 ? 1 : -1),R = sum[i];
		if(L > R) swap(L,R);
		if(L - 1 >= sum[l]) vals[++len] = L - 1;
		vals[++len] = R;
	}
	sort(vals + 1,vals + len + 1);
	len = unique(vals + 1,vals + len + 1) - vals - 1;
	vals[0] = -0x3f3f3f3f;
	Mat T;
	for(int i = l;i <= r;i++)
		if(sum[i] == sum[l]) T[0][i] = 1;
	for(int i = 2;i <= len;i++) { // (vals[i - 1],vals[i]]
		Mat trs;
		vector<int> V;
		for(int j = l + 1;j <= r;j++) {
			ll L = sum[j - 1] + (a[j] > 0 ? 1 : -1),R = sum[j];
			if(L > R) swap(L,R);
			if(L <= vals[i - 1] + 1 && vals[i] <= R)
				V.push_back(j);
		}	
		for(auto id : V)
			for(int j = l;j < id;j++)
				trs[j][id] = 1;
		for(auto id : V)
			if(a[id] > 0) trs[id][id] = 1;
		int tim = vals[i] - vals[i - 1];
		while(tim) { if(tim & 1) T = T * trs;trs = trs * trs;tim >>= 1;}
	}
	int res = 0;
	for(int i = l;i <= r;i++) Plus(res,T[0][i]);
	return res;
}
int main() {
	scanf("%d%*d",&n);
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	static int b[N];int tn = 0;
	for(int i = 1;i <= n;i++) if(a[i]) b[++tn] = a[i];
	n = tn;swap(a,b);
	if(!n) return puts("1 1"),0;
	for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + a[i];
	ll mx = 0;
	for(int i = 0;i <= n;i++)
		for(int j = i + 1;j <= n;j++)
			mx = max(mx,sum[j] - sum[i]);
	if(mx == 0) return printf("%d %lld\n",1,(-sum[n] + 1) % P),0;
	int ans = 0;
	for(int i = 0;i <= n;i++) {
		int p = -1;
		for(int j = i + 1;j <= n;j++)
			if(sum[j] - sum[i] == mx) p = j;
		if(~p) Plus(ans,Solve(i,p)),i = p;
	}
	printf("%lld %d\n",mx + 1,ans);
	return 0;
}
≡