炼石计划 9 月 10 日 NOIP 模拟赛 #2【补题】 - 比赛 - 梦熊联盟 (mna.wang)
模拟赛恒等式：\(0+0+0+0=0\)。
复盘
T1 好像可做。有个显然的 \(n^2\) DP。推式子的时候猜到了 \(\gcd = 1\) 的做法。进一步尝试正解未果。
T2 一眼只会爆搜。想到了 \(b \times b!\) 的做法，应该能过 \(n \le 11\) 的点（实际上这也是出题人的意图）。但是测极限数据 3s，卡常未果。
T3, T4 一分不会。想的时间很少就放弃了。
剩下的时间基本都在 T2 优化（或者说卡常）。
总结
你说呢？
有个好的：T1 做完了正解的第一步。
题解
A. 数位（DP，前缀和，数论）
有 DP：\(f(i, 0/1)\) 表示考虑前 \(i\) 个数，最后一个段是否是倍数串。
转移枚举 \(j \in [0, i)\)。如果 \((j, i]\) 是倍数串那么 \(f(j,0)+f(j,1) \to f(i, 1)\)，否则 \(f(j, 1) \to f(i, 0)\)。
可以轻易 \(\mathcal O(n^2)\) 预处理 \(g(j, i) = \operatorname{val}(j, i] \bmod D = (g(j,i-1) \times 10 + a_j) \bmod D\)。转移也是 \(\mathcal O(n^2)\)。考虑优化。
考虑什么时候 \(\operatorname{val}(j, i] \bmod d = 0\)，即 \((j, i]\) 是一个倍数串。
类似字符串 Hash。令 \(p(i) = \operatorname{val}[i,n]\)。
首先考虑 \(\gcd(10, D) =1\) 的情况。不难发现 \((j, i]\) 是倍数串等价于 \(p(j + 1) \equiv p(i+1) \pmod D\)。读者自证不难。
然后怎么做？上面代码可以写成：
for (int i = 1; i <= n; ++ i ) {
f[i][p[1] == p[i + 1]] = 1;
for (int j = 1; j < i; ++ j ) {
if (p[j + 1] == p[i + 1]) f[i][1] = (f[i][1] + f[j][0] + f[j][1]) % P;
else f[i][0] = (f[i][0] + f[j][1]) % P;
}
}
前缀和优化即可。
考虑 \(\gcd(10, D) \ne 1\) 的情况。不妨设 \(D = 2^x5^yD'\)，其中 \(10 \not \mid D’\)。因为 \(D\) 是百万级别所以 \(x, y \le 20\)。
那么 \(p(j + 1) \equiv p(i+1) \pmod D\) 当且仅当下面的条件都满足：
\[\begin{align} p(j + 1) &\equiv p(i+1) \pmod {2^x}\\ p(j + 1) &\equiv p(i+1) \pmod {5^y}\\ p(j + 1) &\equiv p(i+1) \pmod {D'}\\ \end{align} \]注意到当一个串的长度超过 \(20\) 后，前两个条件是否满足已经可以通过其低 \(20\) 位确定了。这是因为当 \(x \le 20\) 时 \(a_i \times 10^{21} \bmod 2^x = 0\)，\(5\) 也同理。也就是说 \(20\) 位之后是多少，都对整个值模 \(2^x,5^y\) 后的结果没有影响。
所以当长度 \(\le 20\)（即 \(i - j \le 20\)）时暴力。当长度 \(> 20\) 时，先判断其第 \(20\) 位是否满足前两个条件。注意到 \(\gcd(D', 10) = 1\)。于是又转化了最开始的问题。分类讨论一下再前缀和即可。
标签：10,le,20,炼石,NOIP,pmod,bmod,爆零赛,equiv From： https://www.cnblogs.com/2huk/p/18456996