负担集训-Test11(多校联合训练-4)

--------------------------------------------------
结束前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
题意就是给你一个点阵画,读出其中的数字
 
暴力即可
 
--------------------------------------------------