文以载道（潍坊一中78级互测赛）ABEF题解

· · 题解

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 个元素是坏位置。

同理，前缀和优化可以做到 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;
}