搞出一道2700的数学题使我的心中又一次充满了虚假的信心。。。QAQ
You have \(c_1\) letters ‘a‘, \(c_2\) letters ‘b‘, ..., \(c_{26}\) letters ‘z‘. You want to build a beautiful string of length \(n\) from them (obviously, you cannot use the \(i\)-th letter more than \(c_i\) times). Each \(c_i\) is greater than \(\frac{n}{3}\).
A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than 1 in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than 1 (for example, "aca"). Another example: the string "abcaa" is beautiful.
Calculate the number of different strings you can build, and print the answer modulo 998244353.
简单来说，有一些字母，它们被用于构造长度为n的、不包含奇数长度回文子串的字符串，你需要计算可以被构造出来的字符串一共有多少种。
我们注意到，如果所有字母的数量都很充足，字符串的数量很好计算：一共有\(26^2\cdot 25^{n-2}\)种合法字符串。解释一下它的组合意义：每个奇数长度回文串都有一个中心字母，该串关于中心对称。要使得没有字串是奇回文串，就要使所有可能的中心（除了首末以外的所有位置）两侧的字母不同。考虑从头构建字符串，前两个字母可以随意选择，之后向末尾添加字母时要注意不与倒数第二个字母相同。
然后考虑字母数量不足的情况。这种情况下直接计算合法字符串的数量有些困难。注意那个标成粗体的条件“Each \(c_i\) is greater than \(\frac{n}{3}\)”：这说明一个不含回文子串的非法字符串最多有两类字母的数量超过限制。于是我们可以尝试计算不含回文子串的非法字符串的数量，再从所有不含回文子串的字符串的数量中去除它。
任意选择两个字母\(a_1,a_2\)，定义DP状态\(s(l,n_1,n_2,t_2,t_1)\)，表示：长度为\(l\)，包含\(n_1\)个\(a_1\)和\(n_2\)个\(a_2\)，且倒数第二个字母为\(t_2\)，最后一个字母为\(t_1\)，且不包含回文子串的字符串的数量。其中\(l,n_1,n_2\le n\)，而\(t_2,t_1\)分别有\(a_1\)、\(a_2\)、既非\(a_1\)也非\(a_2\)三种状态，所以总状态数是\(O(n^3)\)的。这个DP不难以\(O(n^3)\)的时间复杂度计算出来。
因为DP中假设的两个字母是任意选择的，所以可以把任意两个需要的字母代入进去而不改变结果。最后就是一点细节了：用容斥原理，先减去存在一类字母数量超限的非法字符串，再加上刚好有两类字母数量超限的非法字符串。
代码：https://codeforces.com/contest/1487/submission/112370125
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>
#include <time.h>
#include <complex>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_map>
#include <set>
#include <bitset>
#pragma warning(disable:4996)
#define PII std::pair<int, int>//<long long, long long>
#define PTT std::pair<tree *, tree *>
template<typename T> T min(T x, T y)
{
return x < y ? x : y;
}
template<typename T> T max(T x, T y)
{
return x > y ? x : y;
};
const long long INF = 2000000005;//00000;// autojs.org
const long long mod = 998244353;//1000000007;//
const int MAXN = 405;
int N, U, c[30];
long long f[2][MAXN][MAXN][3][3];//第一种数量，第二种数量，倒数第二个，最后一个
long long sum[MAXN][MAXN];
void DP()
{
f[0][0][0][0][0] = 24 * 24;
f[0][1][0][1][0] = f[0][0][1][2][0] = 24;
f[0][1][0][0][1] = f[0][0][1][0][2] = 24;
f[0][2][0][1][1] = f[0][0][2][2][2] = f[0][1][1][1][2] = f[0][1][1][2][1] = 1;
for (int i = 3; i <= N; i++)
{
int cur = i & 1, last = 1 - cur;
for (int j = 0; j <= U; j++)
for (int k = 0; k <= U; k++)
memset(f[cur][j][k], 0, sizeof(f[cur][j][k]));
for (int j = 0; j <= U; j++)
for (int k = 0; k <= U; k++)
for (int s = 0; s < 3; s++)
for (int t = 0; t < 3; t++)
{
f[cur][j][k][t][0] += f[last][j][k][s][t] * (24 - !s);
f[cur][j][k][t][0] %= mod;
if (s != 1)
f[cur][j + 1][k][t][1] += f[last][j][k][s][t],
f[cur][j + 1][k][t][1] %= mod;
if (s != 2)
f[cur][j][k + 1][t][2] += f[last][j][k][s][t],
f[cur][j][k + 1][t][2] %= mod;
}
}
for (int i = U; i >= 0; i--)
{
for (int j = U; j >= 0; j--)
{
sum[i][j] = sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1];
for (int s = 0; s < 3; s++)
for (int t = 0; t < 3; t++)
sum[i][j] += f[N & 1][i][j][s][t];
sum[i][j] = (sum[i][j] % mod + mod) % mod;
}
}
}
void cal()
{
DP();
long long ans = 26 * 26;
for (int i = 3; i <= N; i++)
ans = (ans * 25) % mod;
for (int i = 0; i < 26; i++)
{
ans = (ans - sum[c[i] + 1][0]) % mod;
for (int j = 0; j < i; j++)
ans = (ans + sum[c[i] + 1][c[j] + 1]) % mod;
}
ans = (ans % mod + mod) % mod;
printf("%lld\n", ans);
}
int main()
{
scanf("%d", &N);
U = N / 2 + 3;
for (int i = 0; i < 26; i++)
scanf("%d", c + i);
cal();
return 0;
}
codeforces 1487G - String Counting
原文：https://www.cnblogs.com/blogofddw/p/14638588.html