2024.6.22
T1
题面
给 \(n\) 个数，求他们的最小公倍数对 \(10^9+7\) 取模的结果。
\(1\le n\le 10^3\)
解法
用 \(\prod p^{\max}\) 计算
T2
题面
在 \(n\times n\) 的地图上有若干 \(1\times k\ (k>1)\) 的长条，竖着的只能竖向移动，横着的只能横向移动，一号一定横着，长条不能越过，求是的将一号点接触右边界的最小步数
\(1\le n\le 8，1\le 长条数\le 13，1\le 答案\le 10\)
解法
只需要记录每个长条起点的会变化的坐标，接着状压搜索。
方法
-
搜索
-
状压
T3
题面
有一个长度为 \(n\) 的序列 \(\{a\}\)，共 \(m\) 个操作
-
1 x y表示 \(a_x\leftarrow y\) -
2 l r求 \(l\) 到 \(r\) 的子区间里，有多少个区间的数拼起来为 \(p\) 的倍数
\(1\le n,m\le 10^5,2\le p\le 15,0\le a_i,y\le 9,1\le x\le n,1\le l\le r\le n\)
方法
每个节点维护这段区间内的答案，左右儿子合并的时候难算的是跨越左右儿子的部分。左儿
子维护后缀模 \(p\) 等于 \(x\) 的有多少个[]，右儿子维护前缀模等于，此时的长度满足
$10^l \mod p = \(的有多少个[][]。那考虑枚举, ，需要的可以算出来，答案增加
[] × [][( − ∗ )\)\bmod$]即可。
方法
-
线段树
线段树求啥维护啥
注意
- 指数要对 \(\varphi(p)\) 取模
T4
题面
\(a,b\) 为两个由 \(s\) 没有前导 \(0\) 的 \(n\) 为十进制正整数，求 \(a+b\) 为回文数的的方案书
多测
\(1\le T\le 10,1\le n\le 10^{18},s\subset\{0,1,2,3,4,5,6,7,8,9\},s\not=\empty\)
解法
[][0,1][0,1]表示已经填了位，高位有没有进位，低位需不需要进位使得已经填了的位回
文的方案数。转移两位两位转移，容易发现[ − 2]到[]的转移是与没关系的，矩阵快速
幂加速即可。唯一需要注意的是最后不能有前导零，所以矩阵快速幂到[ − 3], [ − 2]后
暴力把剩下的位填了就行，这样比在矩阵快速幂里面去处理前导零舒服很多。
方法
-
DP
-
矩阵快速幂
-
特判
单独特判前导0