2024.6.23

lupengheyyds / 2024-11-13 / 原文

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]后
暴力把剩下的位填了就行，这样比在矩阵快速幂里面去处理前导零舒服很多。