Acwing1086

一次幂和 s1 和平方和 s2 的推导

假设当前我们在构造一个数，通过给它增加一个数字 i 来构成新的数，这个数在原有数的基础上增加了一位，并且这位的实际贡献是 k = i * 10^{pos-1} % MOD。这里 pos 表示当前位的位置，10^{pos-1} 是该位置上的位权（即这位数字对整体数值的影响），MOD 是取模操作来保证计算不溢出。

t.s1 的更新：一次幂和

首先考虑一次幂和的更新（即新的符合条件的数字的位数和）。

1. 假设 t.s0 表示符合条件的数字个数。
2. 每个符合条件的数字会增加 k 的贡献到位数和中。

因此：

$$t.s1=(t.s1+k\times t.s0)\mathrm{mod}MOD$$

• 这里 k * t.s0 表示当前位 k 对所有符合条件数字的位数和的贡献。
• 累加上原来的 t.s1，得到当前的位数和。

t.s2 的更新：平方和

平方和 t.s2 的更新更为复杂，因为我们需要考虑新加入的位对平方和的影响，这涉及到一次幂和 s1 和当前位的平方贡献。

平方和的更新公式可以通过以下步骤推导：

1. 设 t.s1 是已经累加的位数和（一次幂和）。
2. 新加入的位 k 对所有符合条件数字的平方和产生影响。

平方和的更新公式可以分解成两个部分：

1. 一次幂和对平方和的影响：根据二次展开公式 (a + b)^2 = a^2 + 2ab + b^2，当我们给数字增加一个位 k 时，平方和中会增加 2 * k * s1 的项。
2. 新位的平方贡献：即 k^2 * s0，因为当前位数 k 本身也会对平方和产生贡献。

因此，完整的平方和更新公式为：

$$t.s2=(t.s2+2\times k\times t.s1+k^2\times t.s0)\mathrm{mod}MOD$$

---

实际代码的推导与解释

代码中每一行的具体含义如下：

t.s2 = (t.s2 + 2ll * k % MOD * t.s1 % MOD) % MOD;

• 2ll * k % MOD * t.s1 % MOD：表示 2 * k * t.s1，即新位 k 对平方和的影响。这部分来源于 (a + b)^2 = a^2 + 2ab + b^2 的展开式中的 2ab 部分。

t.s2 = (t.s2 + k * k % MOD * t.s0 % MOD) % MOD;

• k * k % MOD * t.s0 % MOD：表示 k^2 * t.s0，即新位 k 自身的平方对平方和的贡献。这部分来源于 (a + b)^2 展开式中的 b^2 项。

t.s1 = (t.s1 + k * t.s0 % MOD) % MOD;

• k * t.s0 % MOD：表示新位 k 对一次幂和的贡献。