JZTXT

闲话 23.3.30

发布时间 2023-03-30 12:12:08作者: joke3579

模拟赛

摆！

T1 卷王

考虑差分异或 得到一个序列 a
第 \(t\) 秒按第 \(i\) 个开关会使得第 \(t + \text{dt}\) 秒 \(a[i + \text{dt}], a[i + \text{dt} + 1]\) 两个位置
异或带来的变化会保存

可以发现的是，除了 \(a[i]\) 外，所有 \(i + p (p > 0)\) 的位置都只有在第 \(t + p\) 的时刻翻转 而 \(a[i]\) 总已经被翻转了
所以如果确定了一个操作到现在的时间，我们可以轻易确定这个状态对现在 a 序列的影响
这样我们不妨设计一种状压 dp 来倒着枚举操作序列
设 \(f(t, S)\) 表示后 \(t\) 秒内（操作序列长度为 \(t\)） \(S\) 状态是/否可以翻转到全 0
初始 f(0, 00...0) = true;
每次枚举状态 f(t, S) = true，并枚举要加入到操作序列首的操作
可以是不操作，即 f(t + 1, S) = true
然后枚举当前操作位置为 p，我们知道这次操作肯定翻转 \(a[p]\)
并且由于这次操作到当前操作数/时间为 \(t + 1\) 可以知道 \(a[t + 1 + p]\) 也被翻转
这 dp 是 \(O(n^2 2^n)\) 的

我们没必要对每个长度都处理一遍答案
对于一个状态 S，在 S 前面加上任意多的 0 对答案没有影响
因为操作只会向后贡献
所以只需要处理长度为 \(\max n = 16\) 的即可
并且，打表可以发现最大操作次数不会超过 8，我们能把每两个答案压进一个可见字符
这样代码长度 \le 40k，总复杂度 O(2^n + Tn)（

T2 赢王

首先 \(a[l, r]\) 可行当且仅当 \(k \mid \sum_{i = l}^r a_i\)，原因显然
考虑对每个 \(r\) 统计合法的 \(l\)，这样的 \(l\) 可能有 \(O(n)\) 个，性质不太好
考虑对 \(a\) 作前缀和得到 \(s\)，则我们需要的就是 \(\equiv s_r \pmod k\) 的 \(s_{l - 1}\)

先不考虑整体咋算，考虑确定了区间 \(a[l, r]\) 如何计算贡献，记为 \(b[1, m]\)
从前往后考虑，对 \(b_1\) 只有动 \(b_2\) 可以修改 \(b_1\)，这个操作数是 \(\min(b_1 \text{ mod } k, k - b_1 \text{ mod } k)\) 的
然后从前往后扫，对 \(b\) 作前缀和得到 \(t\)，到第 i 个元素时其实 \(b_i = t_i\)
所以对 \(b\) 的答案就是 \(\sum_{i = 1}^m \min(t_i \text{ mod } k, k - t_i \text{ mod } k)\)

考虑 \(a[l, r]\) 是可行子序列，并存在 \(k\) 满足 \(a[l, k], a[k + 1, r]\) 是可行子序列
设 \(\sum_{i = l}^k a[i] = t\)，对 \(a[l, r]\) 作前缀和得到 s，我们还知道 \(k \mid t\)
则我们知道答案 \(f(l, r)\) 就是

\[\begin{aligned} &\sum_{i = l}^r \min(s_i \text{ mod } k, k - s_i \text{ mod } k) \\ = \ & \sum_{i = l}^k \min(s_i \text{ mod } k, k - s_i \text{ mod } k) + \sum_{i > k}^r \min(s_i \text{ mod } k, k - s_i \text{ mod } k) \\ = \ & f(l, k) + \sum_{i > k}^r \min((s_i - s_{k} + t) \text{ mod } k, k - (s_i - s_{k} + t) \text{ mod } k) \\ = \ & f(l, k) + \sum_{i > k}^r \min((s_i - s_{k}) \text{ mod } k, k - (s_i - s_{k}) \text{ mod } k) \\ = \ & f(l, k) + f(k + 1, r) \end{aligned}\]

这样我们就有了平凡的 \(O(nk)\) 做法
首先按 \(s_i \text{ mod } k\) 分组，组数是 \(O(k)\) 的
然后我们对每组直接 \(O(n)\) 处理出相邻点间的答案
一段的贡献就是包含他的区间个数，这个平凡算
然后加上没贡献的区间的 \(-1\) 即可
大概是 60pts

然后不会了 摆摆摆

T3 稳王

什么组合数？

期望回合
= 1 + \(\sum_{i\ge 0}\) 第 \(i\) 轮打不死 boss 的概率
= 1 + \(\sum_{S}\) 拿到的打不死 boss 的手牌是 \(S\) 的概率
所以考虑统计所有打不死 boss 的手牌和概率
顺序没有影响 所以考虑按 S 里有的手牌种类计数

先推个式子：

\[\sum_{i\ge 0} \frac{1}{x^i} = \sum_{i\ge 0} \left(\frac{1}{x}\right)^i = \frac{1}{1 - \frac{1}{x}} = \frac{x}{x - 1} \]

自然有

\[\sum_{i\ge 1} \frac{1}{x^i} = \frac{x}{x - 1} - 1 = \frac{1}{x - 1} \]

  1. 只有复读
    6
    答案就是 \(\sum_{i\ge 1} 3^{-i} = 1/2\)

  2. 只有火球
    每次打 2 点伤害，打 \((n + 1) / 2\) 次 boss 就没了
    设 m = \((n - 1) / 2\)
    答案就是 \(\sum_{i = 1}^n 3^{-i} = (1 - (1/3)^m) / 2\)

  3. 只有毒药
    每次打一张毒药 打 \(n + 1\) 次 boss 就没了
    答案就是 \(\sum_{i, 1, n} 3^{-i} = (1 - (1/3)^n) / 2\)

  4. 复读 + 火球
    只要有火球，那复读 = 火球
    全是复读和全是火球的已经统计完了
    那答案就是

\[\begin{aligned} & \sum_{i = 1}^m \sum_{j = 1}^{i - 1} \binom{i}{j} (1/3)^{j} (1/3)^{i - j} \\ = \ & \sum_{i = 1}^m \left(\frac{2}{3}\right)^i - 2\times \left(\frac{1}{3}\right) ^i \\ = \ & 1 + \frac{1 - 2^{m + 1}}{3^m} \end{aligned}\]

  1. 火球 + 毒药
    最优策略肯定是第一张打毒药，剩下的毒药伤害是 1，火球伤害是 3
    我们给 boss 血量 + 1，钦定第一张打出去的毒药有伤害
    设 \(f(dmg)\) 是给 boss 打了 \(dmg\) 伤害的概率 答案就是 \(\sum_{i\le n} f(i)\)
    dp 转移是 \(f(k) = f(k - 1) / 3 + f(k - 3) / 3\)
    这可以矩阵快速幂优化 就是

\[\begin{bmatrix} f(k) \\ f(k - 1) \\ f(k - 2) \\ ans(k - 1) \end{bmatrix} = \begin{bmatrix} 1/3 & 0 & 1/3 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} f(k - 1) \\ f(k - 2) \\ f(k - 3) \\ ans(k - 2) \end{bmatrix} \]

  1. 复读 + 毒药
    毒药伤害是 1，复读伤害是 2
    如上 dp 即可

  2. 三种都有
    仍然是直接维护矩阵快速幂

值得注意的是，最终需要做一些容斥，比方说 5. 需要删掉全是毒药的情况

总时间复杂度 \(O(T 4^3 \log n)\) ……吧？

没有代码！摆摆摆！