1 条题解

  • 0
    @ 2021-7-6 13:54:37

    题意

    维护一个集合 SS,表示后缀的数 mod k\text{mod } k 组成的集合。称集合 SS 为当前状态,初始为空集。

    每次打字等同于随机选择 t[0,B1]t \in [0, B - 1],令 SnxtS \leftarrow \text{nxt}。其中集合 nxt\text{nxt} 表示打字后的集合,并称 nxt\text{nxt} 为后继状态。

    可以得到 $\text{nxt} = \bigcup \limits_{i \in S \cup \{0\}} (i \cdot B + t) \bmod k$。

    目标是使得 0S0 \in S。求达成目标的期望次数。

    方程式

    f(S)f(S) 表示当前集合为 SS 时还需的期望次数。则当 0S0 \in S 时,f(S)=0f(S) = 0;否则

    $$f(S) = 1 + \dfrac{1}{B} \sum_{t \in [0, B - 1]} f(\text{nxt}) $$

    tmodkt \bmod k 相同时 nxt\text{nxt} 相同。所以合并这些状态得到

    $$f(S) = 1 + \dfrac{1}{B} \sum_{t \in [0, k - 1]} \left \lfloor \dfrac{B + k - 1 - t}{k} \right \rfloor \cdot f(\text{nxt}) $$

    算法 11Bmodk=0B \bmod k = 0

    Bmodk=0B \bmod k = 0 时,nxt\text{nxt}SS 无关。

    目标转化为 tmodk=0t \bmod k = 0,每次打字完成目标的概率为 1k\dfrac{1}{k}

    f()=xf(\varnothing) = x,则 x=1+(11k)xx = 1 + \left ( 1 - \dfrac{1}{k} \right ) x,解得 x=kx = k,即答案为 kk

    时间复杂度:O(1)O(1)

    算法 22gcd(B,k)=1\gcd(B, k) = 1

    结论:在达到目标前 S|S| 单调递增,其中 S|S| 表示集合 SS 的元素个数。
    证明:因为逆元存在,所以对于任意 iiiiiBmodki \cdot B \bmod k 一一对应。
    如果 0S0 \notin S,则 $\left | \bigcup \limits_{i \in S \cup \{0\}} (i \cdot B + t) \right | = |S \cup \{0\}| = |S| + 1$。
    即在达到目标前 S|S| 随每次打字增加 11

    所以可以按照 S|S| 降序进行 DP。

    优化:用位运算加速计算 nxt\text{nxt} 的过程。这可以使复杂度减少一个 kk 的因子。

    时间复杂度:O(2k×k)O(2k×k2)O(2^k \times k) \sim O(2^k \times k^2)

    算法 33gcd(B,k)2\gcd(B, k) \geq 2

    结论:最多只有 2kgcd(B,k)gcd(B,k)2^{\frac{k}{\gcd(B, k)}} \cdot \gcd(B, k) 种可能的 SS
    证明:对于任意 iiiBmodki \cdot B \bmod kgcd(B,k)\gcd(B, k) 的倍数。
    SS 的元素减去 tt 的集合一定是所有 gcd(B,k)\gcd(B, k) 的倍数组成集合的子集,有 2kgcd(B,k)2^{\frac{k}{\gcd(B, k)}} 种可能。
    加上 tt 后乘以 gcd(B,k)\gcd(B, k) 即得到答案。

    以上只是理论上界,实际(不包含 00 的)可能的 SS 的状态数是一个更小的值。

    所以可以直接列出转移方程,再用高斯消元解方程组。

    优化:只计算本质不相同的 SS。定义“本质不相同”为 nxt\text{nxt} 不相同(,且 nxt\text{nxt} 也“本质不相同”)。因为本质相同的 SS 的答案一定相同,故可以合并为同一状态。

    优化:在高斯消元时只计算非零项。因为矩阵较稀疏,可以跳过许多零,从而减少复杂度。

    优化(来自验题人):在解方程时将转移关系建图,在用 tarjan 缩点后每个强连通分量的点中高斯消元,点之间的 DAG 则直接 DP。

    时间复杂度:O(N3)O(N^3)NN 为状态数

    子任务

    结合算法 1,21, 2 及优化可以通过 kk11 或质数的测试点。

    结合算法 2,32, 3 及优化可以通过所有测试点。

    • 1

    信息

    ID
    151
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    28
    已通过
    2
    上传者