本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-14 20:31:52

A

显然有一个结论：假设 $a_0 = a_{n+1} = 0$，那么如果 $\exist i \in [1,n]$ 满足 $a_i \gt a_{i-1} + a_{i+1}$，那么无解。

那么能不能推广一下呢？

事实上，只要不存在 $i \in [1,n]$ 满足 $a_i \gt a_{i-1}+a_{i+1}$，那么一定有解。

以下是我的（并不严谨的）证明：

假设 $1$ 到 $n$ 位置顺序是从左到右。考虑反复执行这个操作：
选择最靠左的不为 $0$ 的位置，记该位置的值为 $a_{lef}$，从该位置开始向右选择最长的最小值大于等于 $a_{lef}$ 的连续子段，对这个子段执行 $a_{lef}$ 次操作。
由于 $a_i \le a_{i-1} + a_{i+1}$，显然可得，除非序列变为全 $0$，否则不会出现不可操作的情况。

设计 $dp_{i,lst,now}$ 代表只考虑前 $i$ 位，第 $i-1$ 个数是 $lst$，第 $i$ 个数是 $now$ 的（判定合法时只考虑前 $i-1$ 个的）合法序列方案数。
假设第 $i-2$ 个数是 $lst_2$，那么：

$lst_2 + now \ge lst$
$lst_2 \ge lst-now$
$dp_{i,lst,now} = \sum\limits_{k \ge lst_2 \ge lst-now} dp_{i-1,lst_2,lst}$
最后答案是 $\sum\limits_{0 \le x \le k}dp_{n+1,x,0}$

用前缀和优化后复杂度是 $O(n^3)$ 的。
CF 提交记录

B

此时 $n \le 3000$，原来算法不再可行。
现在，我们应该请出数数题的一个很好用的算法：容斥！

如果一个位置 $1 \le i \le n$ 满足 $a_i \gt a_{i-1}+a_{i+1}$，我们就称之为坏位置。

设 $f(i)$ 代表钦定有 $i$ 个坏位置的方案数。

那么根据容斥公式，答案是 $\sum\limits_{i=0}^{n} (-1)^if(i)$。

我们需要对于 $\forall i \in [0,n]$ 计算出 $f(i)$。

设计状态 $dp_{i,lst,x}$ 代表只考虑前 $i$ 个，第 $i$ 个数是 $lst$，前 $i-1$ 个已经钦定了 $x$ 个坏位置的方案数。

看上去状态数是 $O(n^3)$，但注意，事实上根据容斥公式，我们关心的只有坏位置的奇偶性，所以实际有效的状态数可以压缩到 $O(n^2)$，即 $dp_{i,lst,x}$ 代表只考虑前 $i$ 个，第 $i$ 个数是 $lst$，前 $i-1$ 个已经钦定了的坏位置的数量模 $2$ 为 $x$ 的方案数。

转移的话，假设当前状态是 $dp_{i,lst,x}$，考虑是否钦定第 $i-1$ 个元素是坏位置。

• 钦定第 $i-1$ 个位置是坏位置
  $dp_{i,lst,x} = \sum\limits_{lst_2}dp_{i-2,lst_2,x \oplus 1} \times (k-lst-lst_2)$
• 不钦定第 $i-1$ 个位置是坏位置（注意语序，不要理解成 “钦定第 $i-1$ 个位置不是坏位置”）
  $dp_{i,lst,x} = \sum\limits_{lst_2} dp_{i-1,lst_2,x}$

同理，前缀和优化可以做到 $O(n^2)$。
CF 提交记录

E

这些操作看上去很麻烦，而且似乎没有特定数据结构可以直接完成如此复杂的操作。

那么我们请出递推重器——矩阵！

对于一个元素有多个属性需要互相递推的操作，使用矩阵将会大大简化，所以考虑使用矩阵完成这些操作。

剩下部分

F

考虑枚举中点，计算每一个点作为回文串中点能给答案带来多少贡献。

具体地， $1,2,3,4,5,\cdots,n$ 以及相邻两个整点的中点均可以作为回文串中点。

假设枚举 $mid$ 作为回文串中点，接下来，枚举回文串长度，并计算出这个回文串被加入答案的概率，然后累加到答案里即可。整个过程可以用前缀和/后缀和优化。

复杂度 $O(n^2)$。

Code(By @CountingGroup)

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
inline int ksm (int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
const int N = 4005;
const int mod = 998244353;
int n, mp[N], ans, tot, pre[N], suf[N], siz[N];
signed main () {
	n = read ();
	tot = 1;
	pre[0] = suf[n + 1] = 1;
	for (int i = 1;i <= n; ++ i) {
		char s[40];
		scanf ("%s", s + 1);
		int m = strlen (s + 1);
		for (int j = 1;j <= m; ++ j) {
			int offset = s[j] - 'a';
			mp[i] |= (1 << offset);
		}
		tot = tot * m % mod;
		siz[i] = m;
	}
	for (int i = 1;i <= n; ++ i) pre[i] = pre[i - 1] * siz[i] % mod;
	for (int i = n;i >= 1; -- i) suf[i] = suf[i + 1] * siz[i] % mod;
	for (int mid = 1;mid <= n; ++ mid) {
		int L = mid, R = mid, cur = __builtin_popcountll (mp[mid]);
		while (true) {
			ans = (ans + cur * pre[L - 1] % mod * suf[R + 1] % mod) % mod;
			L --, R ++;
			if (L < 1 || R > n) break;
			int state = (mp[L] & mp[R]);
			cur = cur * (__builtin_popcountll (state)) % mod;
		}
	}
	for (int mid = 1;mid <= n; ++ mid) {
		int S = (mp[mid] & mp[mid + 1]);
		int L = mid, R = mid + 1, cur = __builtin_popcount (S);
		while (true) {
			ans = (ans + cur * pre[L - 1] % mod * suf[R + 1] % mod) % mod;
			L --, R ++;
			if (L < 1 || R > n) break;
			int state = (mp[L] & mp[R]);
			cur = cur * (__builtin_popcountll (state)) % mod;
		}
	}
	printf ("%lld\n", ans * ksm (tot, mod - 2, mod) % mod);
	return 0;
}