这几天做了几道codechef上的题

白天听冬令营，晚上练2道题

0801

A是 Codechef April Challenge 2018 Chef at the Food Fair

发现是\(p_i*=x\) 但是却要求\((1-p_i)\)的积不太好做

于是看到乘积形式果断取\(ln\)转成维护区间和最后\(exp\)回去

发现\(ln(1-x)=-\sum_{i=1}^{\infty}\frac{x^i}{i}\)

再发现\(p<=0.9\)

于是只需要维护前\(100\)项即可

时间复杂度是\(O(100nlogn)\)

B是 Codechef July Challenge 2020 Weird Product

发现这个\(x\)的幂次是随下标逐渐\(+1\)果断考虑前缀和

记\(sum_i=\sum_{j=1}^{i}a_j*x^j\)

于是\(w(l,r)=x^{-2*l}*(sum_r-sum_{l-1})\)

于是只需要求\(\prod_{i=1}^n \prod_{j=i}^n -(sum_j-sum_{i-1})*(sum_{i-1}-sum_j)\)

即只需要求\(\prod_{i=0}^n \prod_{j!=i}(sum_i-sum_j)\)

记\(f(x)=\prod_{i=0}^n(x-sum_i)\)

于是对于每一个\(i\)我们就是求\(\frac{f(x)}{x-sum_i}\)在\(x=sum_i\)处的点值

用一下洛必达法则我们发现其实就是求

\(f'(x)\)在\(sum_0\)到\(sum_n\)处的点值

写一个多项式多点求值即可

时间复杂度是\(O(nlog^2n)\)

0802

A是Codechef July Challenge 2020 Expected Repetitions

p是整个串的贡献最后加上去

发现两个前缀\(i\)和\(j(i<j)\)的贡献为\((j-i)*lcs(i,j)\)

于是直接后缀树上线段树合并维护一下答案就好了

类似的有一个SA+CDQ+单调栈的做法

但由于前几天写过类似的题就写的SAM的做法

时间复杂度是\(O(nlogn)\)

B是Codechef July Challenge 2020 Expected Spanning Trees

不难发现可以对每棵生成树分开计算

看到操作序列考虑EGF

不难发现一条在原图中出现的边最后在原图中依然出现的EGF是

\(\sum_{i=0}^{\infty}\frac {x^{2i}} {i!}=\frac{e^x+e^{-x}}{2}\)

同样的一条不在原图中出现的边最后在原图中出现的EGF是

\(\sum_{i=0}^{\infty}\frac {x^{2i+1}} {i!}=\frac{e^x-e^{-x}}{2}\)

于是只需要对于\(i\)从\(0\)到\(n-1\)统计一下有\(i\)条边在原图中出现的生成树个数

这个是常见套路变元矩阵树+高斯消元\(O(n^4)\)解决

于是对于所有有\(i\)条边在原图中出现过的生成树他们的贡献是相同的

生成函数是\([\frac{e^x+e^{-x}}{2}]^{i} [\frac{e^x-e^{-x}}{2}]^{n-1-i}\)

类似「ZJOI2019」开关 的做法

我们把它写成\(\sum_{i}a_i*e^{ix}\)的形式

把\(n\)个式子乘上生成树个数合并起来

每次询问对每个\(e^{ix}\)次方快速幂一下算贡献

我们得到了\(O(n^4+nqlogmod)\)的做法

但这样太慢了好像过不了怎么办（其实能过）

光速幂！

时间复杂度降为\(O(n^4+n(\sqrt{mod}+q))\)

0803