设 \(f_i\) 为以第 \(i\) 个人开始的 \(m\) 个人能够开始合唱的事件，那么要求的就是 \(E(\min\{f_i\})\)
设 \(S = \{ f_1, f_2 ... , f_{n - m + 1}\}\)，根据 \(min-max\) 容斥，就得到：
\[
ans = \sum_{T \subset S} (-1) ^ {|T| + 1} \max\{T\})
\]
当 \(n - m\) 比较小的时候，可以直接跑这个 \(min-max\) 容斥。
求一个集合的 \(max\)， 只需求出有多少要使这个集合中的歌都能唱，需要上几门课。不妨设需要上的课数目为 \(c\)， 总共有 \(W\) 门课，期望上课的次数就是:
\[
\sum_{i = 1} ^ {c} \frac{W}{i}
\]
当 \(m\) 比较小， $ n - m $ 比较大的时候，可以用一个状压 \(DP\) 来做 \(min-max\) 容斥。
注意到集合 \(T\) 的权值只和它的大小跟需要上的课数目有关。
设 \(dp_{i,j,k}\) 表示考虑前 \(i\) 个人，确定要上的课数目为 \(j\)， 前 \(m\) 个人选择的状态为 \(k\)，产生的贡献和是多少。
这里的贡献就是指，如果 \(|T|\) 为奇数，贡献为正，否则为负。
需要预处理一下 \(f_{i,j}\) 表示前 \(m\) 个人选择的状态为 \(j\) 时，要选第 \(i\) 个人，需要多上多少门课。这样转移就是 \(O(2^m n^3)\)
综合两部分复杂度，可以得到一个 \(O(2^{\frac{n}{2}} n^ 3)\) 的算法
#pragma GCC optimize("2,Ofast,inline")
#define fi first
#define se second
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#include<bits/stdc++.h>
using namespace std;
const int N = 31;
const int mod = 998244353;
template <typename T> void read(T &x) {
int f = 0;
register char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
for (x = 0; c >= '0' && c <= '9'; c = getchar())
x = (x << 3) + (x << 1) + (c ^ '0');
if (f) x = -x;
}
namespace Comb {
const int Maxn = 1e6 + 10;
int fac[Maxn], fav[Maxn], inv[Maxn];
void comb_init() {
fac[0] = fav[0] = 1;
inv[1] = fac[1] = fav[1] = 1;
for (int i = 2; i < Maxn; ++i) {
fac[i] = 1LL * fac[i - 1] * i % mod;
inv[i] = 1LL * -mod / i * inv[mod % i] % mod + mod;
fav[i] = 1LL * fav[i - 1] * inv[i] % mod;
}
}
inline int C(int x, int y) {
if (x < y || y < 0) return 0;
return 1LL * fac[x] * fav[y] % mod * fav[x - y] % mod;
}
inline int Qpow(int x, int p) {
int ans = 1;
for (; p; p >>= 1) {
if (p & 1) ans = 1LL * ans * x % mod;
x = 1LL * x * x % mod;
}
return ans;
}
inline int Inv(int x) {
return Qpow(x, mod - 2);
}
inline void upd(int &x, int y) {
(x += y) >= mod ? x -= mod : 0;
}
inline int add(int x, int y) {
return (x += y) >= mod ? x - mod : x;
}
inline int dec(int x, int y) {
return (x -= y) < 0 ? x + mod : x;
}
}
using namespace Comb;
int n, m, cla;
int a[50];
char s[50], t[50][50];
int H[10000], has[35][200];
int bitcnt[1 << 18];
namespace Subtask1 {
int need[N][26];
void main() {
int ans = 0, flag = 0;
for (int i = 0; i < (1 << n - m + 1); ++i) {
memset(need, 0, sizeof need);
int tag = 1, cnt = 0;
for (int j = 0; j < n - m + 1; ++j) {
if (~i >> j & 1) continue;
for (int k = 0; k < m; ++k) {
if (!has[j + k][s[k]]) tag = 0;
need[j + k][s[k] - 'a'] = 1;
}
}
if (i && tag) flag = 1;
else continue;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 26; ++j) {
cnt += need[i][j];
}
}
int tmp = 1LL * cla * H[cnt] % mod;
if (bitcnt[i] % 2 == 0) tmp = mod - tmp;
if (bitcnt[i] & 1) ans = add(ans, 1LL * cla * H[cnt] % mod);
else ans = dec(ans, 1LL * cla * H[cnt] % mod);
}
if (!flag) return (void) ( puts("-1") );
cout << ans << endl;
}
}
namespace Subtask2 {
int f[N][1 << 14 | 1];
int dp[2][N * 26 + 3][1 << 14 | 1];
void main() {
memset(f, 0, sizeof f);
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (1 << m); ++j) {
int cnt = 0, flag = 1;
for (int k = 0; k < m; ++k) {
if (!has[i + k][s[k]]) {
flag = 0;
break;
}
int tag = 1;
for (int l = 0; l < m; ++l) {
if (j >> l & 1) {
if (k + l < m && s[k + l + 1] == s[k]) {
tag = 0;
break;
}
}
}
if (tag) ++cnt;
}
if (!flag) f[i][j] = -1;
else f[i][j] = cnt;
}
}
int now = 1, flag = 0;
dp[0][0][0] = -1;
for (int i = 0; i + m <= n; ++i) {
memset(dp[now], 0, sizeof dp[now]);
for (int j = 0; j <= n * 26; ++j) {
for (int k = 0; k < (1 << m); ++k) {
if (!dp[now ^ 1][j][k]) continue;
int del = f[i][k], t;
int to = ((k & ((1 << m - 1) - 1)) << 1);
upd(dp[now][j][to], dp[now ^ 1][j][k]);
if (f[i][k] == -1) continue;
t = mod - dp[now ^ 1][j][k];
upd(dp[now][j + del][to ^ 1], t);
flag = 1;
}
}
now ^= 1;
}
if (!flag) return (void) (puts("-1"));
int ans = 0;
for (int j = 0; j <= n * 26; ++j) {
for (int k = 0; k < (1 << m); ++k) {
if (!dp[now ^ 1][j][k]) continue;
int del = 1LL * H[j] * dp[now ^ 1][j][k] % mod;
if (del < 0) del += mod;
upd(ans, del);
}
}
ans = 1LL * ans * cla % mod;
cout << ans << endl;
}
}
void solve() {
read(n); read(m);
cla = 0;
memset(has, 0, sizeof has);
for (int i = 0; i < n; ++i) {
scanf("%s", t[i]);
int len = strlen(t[i]);
cla += strlen(t[i]);
for (int j = 0; j < len; ++j) {
has[i][t[i][j]] = 1;
}
}
scanf("%s", s);
if (m <= 13) Subtask2::main();
else Subtask1::main();
}
int main() {
comb_init();
for (int i = 1; i < 10000; ++i) {
H[i] = add(H[i - 1], inv[i]);
}
for (int i = 0; i < (1 << 18); ++i) {
bitcnt[i] = bitcnt[i >> 1] + (i & 1);
}
int T; read(T);
while (T--) solve();
return 0;
}原文：https://www.cnblogs.com/Vexoben/p/11802974.html