D
根据题目给出的构造方式，\(S_n'\) 的长度会达到 \(2^n\) 数量级，没法求出 \(S_n'\)，所以考虑递推。
设 \(dp_{i,l,r}\) 为 \(S_i'\) 里 \(T\) 的 \([l,r]\) 区间以子序列的方式出现了多少次，可以写出转移方程：\(dp_{i,l,r} = \sum dp_{i-1,l,k}\cdot dp_{i-1,k+1,r} + [a_i=T_k]\cdot \sum dp_{i-1,l,k-1}\cdot dp_{i-1,k+1,r}\)，其中 \(k\in [l,r]\)。
第一个大 \(\sum\) 计算不考虑中间的 \(a_i\) 时，前一个 \(S_{i-1}'\) 里左半段 \([l,k]\) 出现的次数乘上后一个 \(S_{i-1}'\) 里右半段 \([k+1,r]\) 出现的次数——当然，需要注意加上左半段或右半段为空的边界情况；第二个大 \(\sum\) 计算如果中间 \(a_i=T_k\) 时，左半段和右半段出现次数之积，同样要注意左右半段为空的情况。具体实现上，可以直接 dp[i][l][l-1] = dp[i][r+1][r] = 1 处理。
rep(i, 1, n) rep(l, 1, m) // n,m分别为a,t长度
rep(r, l, m) { // t的[l,r]在s_i出现多少次
dp[i - 1][l][l - 1] = 1; // 将不合法区间设为1，便于计算
dp[i - 1][r + 1][r] = 1;
int64_t& res = dp[i][l][r] = dp[i - 1][l][r]; // 循环取不到“左半段为空”情况，这里补上
rep(k, l, r) {
res += dp[i - 1][l][k] * dp[i - 1][k + 1][r]; //略去取模操作
if (s[i] == t[k]) res += dp[i - 1][l][k - 1] * dp[i - 1][k + 1][r]; }}
cout << dp[n][1][m];
I
题解给了一个非常神奇的 dp。设 \(g_d\) 为答案大于等于 \(d\) 的情况数，则 \(\sum g_d\) 就是最终答案——对于单个答案 \(d\)，会在 \(g_1,g_2\cdots g_d\) 中被统计恰好 \(d\) 次。考虑如何计算 \(g_d\)：每个人只能选择离自己距离大于等于 \(d\) 的行李，所以第 \(i\) 个人能选择的行李一定是第 \(i+1\) 个人能拿的行李的子集（你肯定把 \(a_i,b_i\) 从小到大排序了吧），于是有 \(dp_{i,j}\) 表示前 \(i\) 个人选择了 \(j\) 件行李的情况数，转移方程：\(dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times (c_i-j+1)\)，其中 \(c_i\) 为距离第 \(i\) 个人大于等于 \(d\) 的行李数。枚举 \(d\)，对每个 \(d\) 预处理 \(c_i\)，然后 \(O(nm)\) 计算 \(dp_{i,j}\)，\(g_d=\sum\limits _{j=1}^m dp_{n,j}\)，最后统计 \(ans=\sum g_d\)。
这个子集性质保证了转移方程的成立，比较巧妙。
// 略去输入、取模
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int ans = 0;
for (int d = 1; d <= 500; d++) {
for (int i = 1; i <= m; i++) {
c[i] = 0;
for (int j = 1; j <= n; j++) {
if (b[i] - a[j] < d) break;
c[i] += 1;
}
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= m; i++) {
dp[i][0] = 1;
for (int j = 1; j <= c[i]; j++)
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (c[i] - j + 1);
}
for (int i = 1; i <= n; i++) g[d] = g[d] + dp[m][i];
ans += g[d];
}
printf("%d\n", ans);
J
J 题是一个比较板子的线性基，但是我当时并不会。线性基是用于处理异或问题的常用工具，考虑求一列数 \(a_i\) 中子集的最大异或和。把 \(a_i\) 做二进制拆分得到一个 01 矩阵，如果直接从上到下扫，没法判断当前数该不该选，因为后面的可能会影响前面的。但如果把这个矩阵转化为行阶梯型，就能判断了！因为 1）转化为行阶梯型实际上是求一组基，所以在原来矩阵里选若干行（即若干 \(a_i\)）能得到的异或和，在新矩阵里选若干行一样能凑出；2）每行主元下面一定不会再有 1，每选一个就确定了一位。所以，我们可以直接从上到下 \(O(bit)\) 地求出答案。
// 图示二进制拆分为矩阵 // 变换为行阶梯型（线性基）
a[1] = 44 00101100 p[6] = 01101101
a[2] = 28 00011100 p[5] = 00101100
a[3] = 109 01101101 p[4] = 00011100
a[4] = 3 00000011 p[2] = 00000011
求线性基模版（贪心）：
uint64_t p[52];
void insert(uint64_t x) {
for (int i = 51; ~i; i--) {
if (!(x >> i)) continue;
if (!p[i]) {
p[i] = x;
break;
}
x ^= p[i];
}
}
还可以用高斯消元求，直接就是行阶梯型，没有中间的空行。
线性基能做的事有：
- 求异或和最大值；
- 求异或和最小值——直接输出 \(\min p_i\)；
- 求异或和第 \(k\) 大值——把 \(p_i\) 改为行最简形，把 \(k\) 的置位全部加进去；
- 求一个数在给定集合的子集异或和中的排名（判断是否能被异或和表出）。
对于此题，我们令 \(a\) 的异或和为 \(A\)，\(b\) 的异或和为 \(B\)，对 \(c_i=a_i\oplus b_i\) 建线性基，就把转化出了选择 \(c_i\) 的子集的问题。从高位到低位枚举 \(A,B\) ，如果都是 0 则不变；都是 1 的话，如果当前位线性基非 0 则异或上；直到出现一个 1 一个 0，如果线性非 0，枚举一下“异或”“不异或”两种情况（线性基为 0 什么也做不了）——此时最大值就确定了。用后面位的线性基最小化这个最大值，输出即可。
void insert(ull x) {
for (int i = 31; ~i; i--) {
if (!(x >> i)) continue;
if (!p[i]) { p[i] = x; break; }
x ^= p[i];
}
}
int main() {
int T;
cin >> T;
while (T--) {
fill(p, p + 32, 0);
int n; cin >> n;
ull A = 0, B = 0;
for (int i = 1; i <= n; i++) cin >> a[i], A ^= a[i];
for (int i = 1; i <= n; i++) cin >> b[i], B ^= b[i], insert(a[i] ^ b[i]);
bool ok = 0;
for (int i = 31; ~i; i--) {
int a = (A >> i) & 1, b = (B >> i) & 1;
if (a == 0 && b == 0) continue;
if (a == 1 && b == 1) { A ^= p[i], B ^= p[i]; continue; }
ok = 1;
if (a == 1) {
for (int j = i - 1; ~j; j--) A = min(A, A ^ p[j]); // 不改变，A为最大值
if (!p[i]) cout << A << endl;
else {
B ^= p[i];
for (int j = i - 1; ~j; j--) B = min(B, B ^ p[j]); // 改变，B为最大值
cout << min(A, B) << endl;
}
} else {
for (int j = i - 1; ~j; j--) B = min(B, B ^ p[j]); // 不改变，B为最大值
if (!p[i]) cout << B << endl;
else {
A ^= p[i];
for (int j = i - 1; ~j; j--) A = min(A, A ^ p[j]); // 改变，A为最大值
cout << min(A, B) << endl;
}
}
break;
}
if (!ok) cout << max(A, B) << endl;
}
}