挑了一些简单点的题乱做。。。

题目链接：传送门

HNOI2019

「HNOI2019」多边形

这里

「HNOI2019」校园旅行

myy的题解

更详细的题解

稍微提一下，考虑优化暴力。暴力每次是往两边扩展一个点，那么我们就每次扩展一堆点。事实上，我们也并不需要知道每次往两边加多少个，只需要考虑奇偶性即可，于是就有了这个做法。

GXOI/GZOI2019

「GXOI / GZOI2019」与或和

[单调栈]

按位拆分，转化为求有多少个子矩阵全为11，以及总方案数减去有多少个子矩阵全为00

以全为11为例，预处理出len[i][j]len[i][j]表示从(i,j)(i, j)这个位置往右最长连续为11的长度。考虑每一列，我们即要求出这一列上所有区间lenlen的最小值之和

问题转化为，有一个数列，你需要求其中每个区间的最小值之和

显然考虑贡献，用单调栈维护左边第一个小于等于它的位置，右边第一个小于它的位置即可

「GXOI / GZOI2019」逼死强迫症

[矩阵快速幂]

设nn列的答案为fnf_n，斐波那契数列为gng_n，其前缀和为hnh_n，那么

fn=fn−1+fn−2+2∑i=1n−3gi=fn−1+fn−2+2∗hn−3=fn−1+fn−2+2∗(gn−1−1) \begin{aligned} \displaystyle f_n &= f_{n - 1} + f_{n - 2} + 2\sum_{i=1}^{n-3}g_i\\ &= f_{n - 1} + f_{n-2} + 2*h_{n - 3}\\ &= f_{n-1} + f_{n-2} + 2*(g_{n-1} - 1) \end{aligned}

考虑枚举两个1×11\times 1的砖块中更靠右的那个放在哪里.

若它放在第 n−1n-1 列，则答案是fn−1f_{n - 1}，若在前 n−2n-2 个中的某一列上，则答案是fn−2f_{n - 2}

若放在第nn列，设左边那个砖块放在第ii列，那么从第ii列到第nn列的方案其实是固定的，剩下的部分就是斐波那契数列

关于hn=gn+2−1h_{n} = g_{n + 2} - 1那里的证明：

hn=∑i=1ngi=∑i=1ngi+1−gi−1=(∑i=2n+1gi)−(∑i=0n−1gi)=gn+1+gn−1=gn+2−1 \begin{aligned} h_n &= \sum_{i=1}^{n}g_i\\ &= \sum_{i=1}^{n}g_{i + 1} - g_{i - 1}\\ &= \Big(\sum_{i=2}^{n + 1}g_{i}\Big) - \Big(\sum_{i=0}^{n - 1}g_{i}\Big)\\ &= g_{n + 1} + g_{n} - 1\\ &= g_{n + 2} - 1 \end{aligned}

然后矩阵快速幂优化即可

这里顺便记录一下矩阵快速幂优化线性齐次常系数递推的套路

假设dp转移方程是从f1,f2...fnf_{1}, f_{2} ... f_{n}转移成(a1,1f1+a2,1f2+...+an,1fn),...,(a1,nf1+a2,nf2+...+an,nfn)(a_{1, 1}f_1 + a_{2, 1}f_2 + ...+a_{n, 1}f_n), ... ,(a_{1, n}f_{1} + a_{2, n}f_2 + ... + a_{n, n}f_n)

那么矩阵就是

简单来说，ai,ja_{i, j}表示从fif_i转移到fj′f'_{j}需要乘的系数

这个东西我现在才会。。。

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Mod = 1e9 + 7;
const int Maxn = 5;

int N;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

struct Matrix
{
	int A[Maxn][Maxn];

	Matrix () { memset (A, 0, sizeof A); }
	
	inline Matrix operator * (const Matrix &rhs) const &
	{
		Matrix ans;
		for (int i = 0; i < Maxn; ++i)
			for (int k = 0; k < Maxn; ++k)
			{
				if (!A[i][k]) continue;
				for (int j = 0; j < Maxn; ++j)
					Add (ans.A[i][j], (LL) A[i][k] * rhs.A[k][j] % Mod);
			}
		return ans;
	}
	
	inline Matrix operator ^ (const int b) const &
	{
		Matrix a = *this, ans;
		for (int i = 0; i < Maxn; ++i) for (int j = 0; j < Maxn; ++j) ans.A[i][j] = (i == j);
		for (int i = b; i; i >>= 1, a = a * a) if (i & 1) ans = ans * a;
		return ans;
	}
};

inline void Solve ()
{
	if (N == 1 || N == 2) { puts("0"); return ; }
	Matrix sum;
	sum.A[0][0] = sum.A[0][1] = 1;
	sum.A[1][0] = 1;
	sum.A[2][2] = sum.A[2][3] = 1, sum.A[2][0] = 2;
	sum.A[3][2] = 1;
	sum.A[4][0] = sum.A[4][4] = 1;

	Matrix ans;
	ans.A[0][2] = 2, ans.A[0][3] = 1, ans.A[0][4] = Mod - 2;
	
	ans = ans * (sum ^ (N - 2));
	
	printf("%d\n", ans.A[0][0]);
}

inline void Input ()
{
	N = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	int T = read<int>();
	while (T--)
	{
		Input ();
		Solve ();
	}
	
	return 0;
}

「GXOI / GZOI2019」旅行者

[最短路] [二进制分组]

考虑每条边的贡献。处理出fif_i表示到ii点最近的关键点，gig_i表示从ii出发能到达的最近的关键点。如果fi≠gif_i\ne g_i就能用这条边贡献答案

此外，还能直接二进制分组做。即枚举二进制下每一位，把关键点按这一位为0/10/1划分成两个集合，跑两个集合之间的最短路即可。因为原问题起点终点集合有交，于是不能直接跑最短路。而通过二进制分组分成两个不交的集合后就能直接跑了

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar(); 
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/sefl/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Maxm = 5e5 + 100;

int N, M, K;
int A[Maxn];

struct edge
{
	int x, y, z;
} E[Maxm];

struct Graph
{
	const LL inf = 1e18;
	int e, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], W[Maxm << 1];
	inline void init ()
	{
		e = 0;
		memset (Begin, 0, sizeof Begin);
	}

	inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }
	
	LL Dis[Maxn];
	int from[Maxn];
	
	inline void dijkstra ()
	{
		static priority_queue <pii, vector <pii>, greater <pii> > Q; 
		for (int i = 1; i <= N; ++i) Dis[i] = inf, from[i] = 0;
		for (int i = 1; i <= K; ++i) Dis[A[i]] = 0, from[A[i]] = A[i], Q.push (mp (0, A[i]));
	
		while (!Q.empty())
		{
			int x = Q.top ().y; Q.pop ();
			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				if (Chkmin (Dis[y], Dis[x] + W[i]))
				{
					from[y] = from[x];
					Q.push (mp (Dis[y], y));
				}
			}
		}
	}

} G[2];

inline void Solve ()
{
	G[0].dijkstra ();
	G[1].dijkstra ();
	
	LL ans = 1e18;
	
	for (int i = 1; i <= M; ++i)
	{
		int x = E[i].x, y = E[i].y, z = E[i].z;
		if (G[0].from[x] != G[1].from[y])
			Chkmin (ans, G[0].Dis[x] + G[1].Dis[y] + z);
	}
	
	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		E[i].x = read<int>(), E[i].y = read<int>(), E[i].z = read<int>();
		G[0].add_edge (E[i].x, E[i].y, E[i].z);
		G[1].add_edge (E[i].y, E[i].x, E[i].z);
	}
	for (int i = 1; i <= K; ++i) A[i] = read<int>();
}

inline void Init ()
{
	G[0].init ();
	G[1].init ();
}

int main ()
{
	
#ifndef ONLINE_JUDGE
	freopen ("A.in", "r", stdin);
	freopen ("A.out", "w", stdout);
#endif

	int Testcase = read<int>();
	
	while (Testcase--)
	{
		Init ();
		Input ();
		Solve ();
	}
	
	return 0;
}

「GXOI / GZOI2019」旧词

[数据结构]

一个很简单的套路。没有kk次方的话就是把可选点到根的路径全部+1+1，然后求所求点到根路径上的权值和

+1+1的本质其实是+depi−depfai\displaystyle +dep_i - dep_{fa_{i}}，那么这道题变成+(depik)−(depfaik)\displaystyle +(dep_i^k) -(dep_{fa_{i}}^k) 即可

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 5e4 + 100;
const int Mod = 998244353;

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
	return ans;
}

int N, M, K;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int fa[Maxn], dep[Maxn], dfn[Maxn], idfn[Maxn], son[Maxn], size[Maxn], top[Maxn], dfs_clock;
int Sum[Maxn];

struct info
{
	int x, y, id;
} Q[Maxn];

inline int cmp (info a, info b) { return a.x < b.x; }

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs (int x)
{
	dep[x] = dep[fa[x]] + 1, size[x] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		dfs (y);
		size[x] += size[y];
		if (size[y] > size[son[x]]) son[x] = y;
	}
}

inline void dfs (int x, int now)
{
	idfn[dfn[x] = ++dfs_clock] = x, top[x] = now;
	if (son[x]) dfs (son[x], now);
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == son[x]) continue;
		dfs (y, y);
	}
}

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls root << 1
#define rs root << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
	struct info
	{
		int sum, tag;
	} node[Maxn << 2];

	inline int get_val (int l, int r) { return (Sum[r] - Sum[l - 1] + Mod) % Mod; }
	
	inline void push_up (int root) { node[root].sum = (node[ls].sum + node[rs].sum) % Mod; }
	
	inline void push_down (int root, int l, int r)
	{
		if (!node[root].tag) return ;
		Add (node[ls].sum, (LL) node[root].tag * get_val (l, mid) % Mod);
		Add (node[ls].tag, node[root].tag);
		Add (node[rs].sum, (LL) node[root].tag * get_val (mid + 1, r) % Mod);
		Add (node[rs].tag, node[root].tag);
		node[root].tag = 0;
	}
	
	inline void update (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y)
		{
			Add (node[root].sum, get_val (l, r));
			Add (node[root].tag, 1);
			return ;
		}
		push_down (root, l, r);
		if (x <= mid) update (lson, x, y);
		if (y > mid)  update (rson, x, y);
		push_up (root);
	}
	
	inline int query (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return node[root].sum;
		else
		{
			push_down (root, l, r);
			int ans = 0;
			if (x <= mid) Add (ans, query (lson, x, y));
			if (y > mid) Add (ans, query (rson, x, y));
			return ans;
		}
	}

#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}

inline void Update (int x)
{
	while (x)
	{
		SEG :: update (1, 1, N, dfn[top[x]], dfn[x]);
		x = fa[top[x]];
	}
}

inline int Query (int x)
{
	int ans = 0;
	while (x)
	{
		Add (ans, SEG :: query (1, 1, N, dfn[top[x]], dfn[x]));
		x = fa[top[x]];
	}
	return ans;
}

int Ans[Maxn];

inline void Pre ()
{
	dfs (1);
	dfs (1, 1);
//	for (int i = 1; i <= N; ++i) cout << idfn[i] << ' ' << dep[idfn[i]] << endl;
	for (int i = 1; i <= N; ++i)
		Sum[i] = ((LL) Sum[i - 1] + Pow (dep[idfn[i]], K) - Pow (dep[idfn[i]] - 1, K) + Mod) % Mod;
}

inline void Solve ()
{
	Pre ();

	for (int i = 1; i <= M; ++i) Q[i].x = read<int>(), Q[i].y = read<int>(), Q[i].id = i;
	sort (Q + 1, Q + M + 1, cmp);
	
	int j = 1;
	for (int i = 1; i <= M; ++i)
	{
		while (j <= Q[i].x) Update (j++);
		Ans[Q[i].id] = Query (Q[i].y);
	}
	
	for (int i = 1; i <= M; ++i) printf("%d\n", Ans[i]);
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();
	for (int i = 2; i <= N; ++i) add_edge (fa[i] = read<int>(), i);
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();
	
	return 0;
}

TJOI2019

「TJOI2019」甲苯先生的字符串

[矩阵快速幂]

矩阵快速幂随便搞下

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 1e9 + 7;

LL N;
char S[Maxn];

inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
	return ans;
}

struct Matrix
{
	int A[30][30];
	inline Matrix () { memset (A, 0, sizeof A); }
	inline Matrix operator * (const Matrix &rhs) const &
	{
		Matrix ans;
		for (int i = 0; i < 26; ++i)
			for (int k = 0; k < 26; ++k)
			{
				if (!A[i][k]) continue;
				for (int j = 0; j < 26; ++j)
					Add (ans.A[i][j], (LL) A[i][k] * rhs.A[k][j] % Mod);
			}
		return ans;
	}

	inline Matrix operator ^ (const LL &n) const &
	{
		Matrix a = *this, ans;
		for (int i = 0; i < 26; ++i) ans.A[i][i] = 1;
		for (LL i = n; i; i >>= 1, a = a * a) if (i & 1) ans = ans * a;
		return ans;
	}
} trans;

inline void Solve ()
{
	Matrix Ans;
	for (int i = 0; i < 26; ++i) Ans.A[0][i] = 1;
	Ans = Ans * (trans ^ (N - 1));

	int ans = 0;
	for (int i = 0; i < 26; ++i) Add (ans, Ans.A[0][i]);
	cout << ans << endl;
}

inline void Input ()
{
	N = read<LL>();
	scanf("%s", S);
	for (int i = 0; i < 26; ++i) for (int j = 0; j < 26; ++j) trans.A[i][j] = 1;
	for (int i = 1, len = strlen (S); i < len; ++i)
		trans.A[S[i - 1] - 'a'][S[i] - 'a'] = 0;
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();
	
	return 0;
}

「TJOI2019」甲苯先生的滚榜

[数据结构]

无脑上pb_ds，当然也可以权值线段树维护

「TJOI2019」唱、跳、rap 和篮球

[容斥] [生成函数] [多项式] [NTT]

考虑容斥。设m=min{a,b,c,d,n4}m = \min\{a, b, c, d, \frac{n}{4}\}，枚举至少有ii个cxk，则

ans=∑i=0m(−1)i(n−3ii)fn−4i ans = \sum_{i=0}^{m} (-1)^{i}\binom{n - 3i}{i}f_{n-4i}

其中fn−4if_{n-4i}表示剩下的n−4in-4i个人的排列方案

前面那个(n−3ii)\binom{n-3i}{i}是因为cxk不能拆开，于是把每个cxk看成一个整体，所以总共有n−3in-3i个元素，要从中选出ii个元素

后面的部分，设四种同学分别有aja_j个，那么就是(n−4i)!∏j=14aj!\displaystyle \frac{(n-4i)!}{\prod_{j=1}^{4} a_j!}

分母部分就直接把四个指数型生成函数的多项式卷起来即可

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1000 + 100;
const int Mod = 998244353;

int N, Num[4], M;

namespace MATH
{
	int fac[Maxn], ifac[Maxn];
	inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }
	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
		return ans;
	}
	inline int C (int n, int m)
	{
		if (n < m) return 0;
		return (LL) fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
	}
}

using namespace MATH;

namespace Poly
{
	const int Maxn = 1e4 + 10;
	const int g = 3;
	int n, rev[Maxn];
	int F[4][Maxn];

	inline void init (int k)
	{
		int sum = 0;
		for (int i = 0; i < 4; ++i) sum += Num[i] - k;
	
		n = 1; while (n <= sum) n <<= 1;
		for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? (n >> 1) : 0);
	
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < n; ++j)
				F[i][j] = (j <= Num[i] - k) ? ifac[j] : 0;
	}
	
	inline void dft (int *A, int fl)
	{
		for (int i = 0; i < n; ++i) if (rev[i] < i) swap (A[rev[i]], A[i]);
		for (int mid = 1; mid < n; mid <<= 1)
		{
			int Wn = Pow (g, (Mod - 1) / mid / 2);
			if (fl) Wn = Pow (Wn, Mod - 2);
			for (int i = 0; i < n; i += (mid << 1))
			{
				int W = 1;
				for (int j = i; j < i + mid; ++j, W = (LL)W * Wn % Mod)
				{
					int x = A[j], y = (LL) W * A[j + mid] % Mod;
					A[j] = (x + y) % Mod, A[j + mid] = (x - y + Mod) % Mod;
				}
			}
		}
	
		int inv = Pow (n, Mod - 2);
		if (fl) for (int i = 0; i < n; ++i) A[i] = (LL) A[i] * inv % Mod;
	}
	
	inline int calc (int k)
	{
		init (k);
		for (int i = 0; i < 4; ++i) dft (F[i], 0);
		for (int i = 1; i < 4; ++i)
			for (int j = 0; j < n; ++j)
				F[0][j] = (LL) F[0][j] * F[i][j] % Mod;
		dft (F[0], 1);
		return F[0][N - 4 * k];
	}
}

inline void Solve ()
{
	int ans = 0;
	for (int i = 0; i <= M; ++i)
	{
		int now = (LL) C (N - 3 * i, i) * Poly :: calc (i) % Mod * fac[N - 4 * i] % Mod;
		if (i & 1) Add (ans, Mod - now);
		else Add (ans, now);
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = N / 4;
	for (int i = 0; i < 4; ++i) Chkmin (M, Num[i] = read<int>());
}

inline void Init (int maxn = 1000)
{
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i) fac[i] = (LL) fac[i - 1] * i % Mod;
	ifac[maxn] = Pow (fac[maxn], Mod - 2);
	for (int i= maxn - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % Mod;
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Init ();
	Input ();
	Solve ();
	
	return 0;
}

「TJOI2019」大中锋的游乐场

因为kk很小，直接把所有状态拿出来跑最短路

「TJOI2019」甲苯先生和大中锋的字符串

[后缀自动机] [字符串]

建SAM随便搞

Code 
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 1e5 + 100;

int N, K;
char S[Maxn];

namespace BIT
{
#define lowbit(x) (x & (-x))
	LL sum[Maxn];
	inline void init () { memset (sum, 0, sizeof sum); }
	inline void add (int x, int val) { for (; x < Maxn - 5; x += lowbit(x)) sum[x] += val; }
	inline void add (int x, int y, int val) { add (x, val), add (y + 1,-val); }
	inline LL query (int x) { LL ans = 0; for (; x; x -= lowbit(x)) ans += sum[x]; return ans; }
}

namespace SAM
{
	int node_cnt = 1, last = 1;
	struct info
	{
		int ch[30], fa, maxlen, cnt;
	} node[Maxn << 2];
	
	inline int new_node (int pre)
	{
		++node_cnt;
		node[node_cnt].maxlen = node[pre].maxlen + 1;
		node[node_cnt].cnt = 1;
		return node_cnt;
	}
	
	inline void extend (int c)
	{
		int now = new_node (last), pre = last; last = now;
		for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;
		if (!pre) node[now].fa = 1;
		else
		{
			int x = node[pre].ch[c];
			if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
			else
			{
				int y = ++node_cnt; node[y] = node[x];
				node[y].cnt = 0, node[y].maxlen = node[pre].maxlen + 1;
				node[now].fa = node[x].fa = y;
				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;  
			}
		}
	}
	
	inline void build (char *s, int n)
	{
		for (int i = 1; i <= n; ++i) extend (s[i] - 'a');
	}
	
	vector <int> G[Maxn << 2];
	
	inline void dfs (int x)
	{
		for (int y : G[x])
		{
			dfs (y);
			node[x].cnt += node[y].cnt;
		}
	}
	
	inline void solve ()
	{
		for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i);
		dfs (1);
	
		for (int i = 1; i <= node_cnt; ++i)
		{
			if (node[i].cnt == K)
				BIT :: add (node[node[i].fa].maxlen + 1, node[i].maxlen, 1);
		}
	
		int ans = -1;
		LL times = 0;
		for (int i = N; i >= 1; --i)
		{
//			cout << i << ' ' << BIT :: query (i) << endl;
			if (Chkmax (times, BIT :: query (i))) ans = i;
		}
		
		cout << ans << endl;
	}
	
	inline void init ()
	{
		for (int i = 1; i <= node_cnt; ++i) G[i].clear (), memset (node[i].ch, 0, sizeof node[i].ch), node[i].fa = node[i].cnt = node[i].maxlen = 0;
		node_cnt = last = 1;
	}
}

inline void Solve ()
{
	BIT :: init ();
	SAM :: init ();
	SAM :: build (S, N);
	SAM :: solve ();
}

inline void Input ()
{
	scanf("%s", S + 1);
	N = strlen (S + 1);
	K = read<int>();
}

int main ()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);	
	freopen("A.out", "w", stdout);
#endif

	int Testcase = read<int>();
	
	while (Testcase--)
	{
		Input ();
		Solve ();
	}
	return 0;
}