负担集训-Test11（多校联合训练-4）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------
结束前20s听到前面的队一阵尖叫...
然后我们就被挤出了前40_(:з」∠)_
话说我居然在03这种sb题上卡了一个多小时...真的是不会数学了...
--------------------------------------------------
02:
题意是说给你一个长度为$n$的串$s$和一个长度为$m$的串$t$，有$k$个询问，每个询问是给出$[L,R]$,询问任选一对$(i,j)$满足$i\leq L,j\geq R$，删去$s$的$[i+1,j-1]$这个区间的子串，剩下两块拼在一起，$t$在其中的匹配数的期望$e$。
输出$e\times L\times (n-R+1)$
$n,k\leq 5\times 10^4,m\leq 100$
删去一段之后的匹配分两种，一种是本来就匹配的，删除没有影响他，另一种是本来不匹配，删除之后因为两端连接产生的新匹配。
首先考虑第一种：设$t$的某个匹配为$(l,r)$,推一下公式发现若$r\leq L$，那么这个匹配的贡献为$(L-r+1)\times (n-R+1) = (L+1)(n-R+1)-r(n-R+1)4$，那么我们可以预处理一下匹配的r的前缀和匹配数的前缀和,就可以$O(1)$询问出来了。而若$l\geq R$，那么贡献是$(l-R+1)\times L$，也类似的弄两个前缀和出来就好。
现在考虑因为删除中间一坨而产生的新匹配，我们考虑把$t$拆开成两个非空部分$t_1$,$t_2$，显然这一种的总贡献等同于$t_1$在$[1,L]$内的匹配数乘以$t_2$在$[R,n]$内的匹配数，这个也可以预处理一下前缀和，询问的时候枚举拆开的位置就行了。
--------------------------------------------------
03：
题意就是说给你$l$,$r$,$k$，问你$\sum_{i=l}^rd(i^k)$的值是多少。
其中$d(n)$表示$n$的约数个数。
$l,r\leq 10^{12},r-l\leq 10^6,k\leq 10^7$
假设一个数是$a=p_1^{b_1}p_2^{b_2}...p_m^{b_m}$，那么$d(a^k)$就等于$(b_1k+1)(b_2k+1)...(b_mk+1)$。
然后对于一个数$n$，大于$n^{0.5}$的$n$的素约数最多只有一个
所以我们只需要枚举$10^6$以内的素数，再枚举他们的$[l,r]$内的倍数，去分解每个数，这样算出他们的$d(i^k)$
对于那些用$10^6$以内的素数分解$0$之后不为$1$的数，就说明他们有一个大于$10^6$的素约数
最后把每个数的$d$加起来就好
--------------------------------------------------
11
题意就是给你一个点阵画，读出其中的数字
暴力即可
--------------------------------------------------
评论 (0)
