从 2022-08-25 开始更新。
\(\mathbb{ARC \ 146 \ C}\)
观察
一眼递推，问题在于 \(\Theta(2^n)\) 的复杂度显然不对。
考虑怎么从上一层转移，可以从现在新增的元素里选出一些往上一层合法的集合中加，如果在添加后不合法则情况是上一层的集合存在一个大小为奇数的子集异或值和当前选出的元素相等，继续想，这个子集只可能有一个，因为如果存在两个，则上一层的该集合不合法，即会存在一个大小为偶数且异或和为 \(0\) 的子集。
其实还可以发现一个性质，即是说因为上一层的集合每一个大小为奇数的集合都对应着一个唯一一个不能加进去的元素，那么每一新元素都有 \(2^i - 2^{i - 1}\) 种选法。
具体推一下，定义 \(dp_i\) 为第 \(i\) 层的答案，那么可以拿到 \(dp_{i - 1}\) 。
得到的转移方程为
边界是 \(dp_1 = 1\) 。
回到最开始的问题，复杂度不对，其实打表可以看到在 \(i \ge n + 2\) 时，答案不会再次变化。
\(\mathbb{ABC \ 256 \ F}\)
/kk 因为这道题没看到弱智题 G
可以考虑一个最蠢的 \(dp_{t,i,j}\) 表示，前确定了 \(t\) 个维度后，距离 \(p\) 为 \(i\) ，距离 \(q\) 为 \(j\) 的多维体的总数，可以写出一个 \(\Theta(nD^3)\) 的转移方程。
然后比赛时就卡在这里了，，，
如果把代码写出来，估计优化就容易了。
for (int t = 1; t <= n; t++) {
memset(dp[t & 1], 0, sizeof(dp));
for (int pos = -2 * 1000; pos <= 2 * 1000; pos++) {
int dis1 = Abs(pos - p[t]);
int dis2 = Abs(pos - q[t]);
if (Max(dis1, dis2) > d) continue;
for (int i = 0; i <= d - dis1; i++) {
for (int j = 0; j <= d - dis2; j++) {
dp[t & 1][i + dis1][j + dis2] += dp[t & 1 ^ 1][i][j];
}
}
}
}
然后要搞一个奇妙的转化，定义 \(s_i = \mid p_i - q_i \mid\) ，把合法的 \((dis1,dis2)\) 分成三类。如下
\((s, 0), (s - 1, 1), (s - 2, 2), (s - 3, 3) \dots (0, s)\)
\((s + 1, 1), (s + 2, 2), (s + 3, 3) \dots\)
\((1, s + 1), (2, s + 2), (3, s + 3) \dots\)
那么这个就可以做了，因为这些合法的点均在一条直线上，最终可以优化到 \(\Theta(nd^2)\)。
\(\mathbb{ABC \ 264 \ G}\)
居然不会写了
标签：mathbb,ABC,记录,板刷,sum,mid,times,dp From： https://www.cnblogs.com/Iridescent41/p/17546996.html