251113 模拟赛
T1
给定一个数字串，求它有多少个子串从左往右写成的十进制数是给定常数 \(d\) 的倍数。
\(n\le 1000,~d\le 10^6\)
如果 \(\gcd(d,10)=1\) 那么是非常好做的。否则，我们将 \(d\) 分解为 \(2^x5^yd'\)，其中 \(\gcd(d',10)=1\)。子串 \((l,r]\) 合法当且仅当：
\[
s_r\equiv s_l\times 10^{r-l}\pmod {2^x}\\
s_r\equiv s_l\times 10^{r-l}\pmod {5^y}\\
s_r\equiv s_l\times 10^{r-l}\pmod {d'}
\]
发现 \(r-l\) 充分大的时候，前两行式子的右边等于 \(0\)，因此贡献是非常容易统计的，最后一行直接仿照 \(d\) 和 \(10\) 互质时做即可。\(r-l\) 较小时暴力转移即可。
T2
同底矩阵快速幂可以优化到 \(O(\omega^{3}\log V+T\omega^2\log V)\)。
T3
发现链是简单的，考虑钦定 \(1\to n\) 的边连起来的情况下如何计算代价。枚举序列前缀极长连续段长度，可以计算出极长连续后缀长度的下界，用小根堆维护。然后线段树直接做即可。