ST表

另一种莫队算法的实现

$$O(n^2\log(u))$$

zkw真的快

出门左转58，双倍经验改一下比较....
话说难度一样的题一个一星，一个两星半，蜜汁尴尬.....

迷之数组大小

1A
随便玩玩基础(naive)的线段树..........

致 已被玩烂的PID1738

\begin{align*} \sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j}&=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\int_0^1x^{ik+j-1}dx \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=0}^{k-1}(-1)^jC_{k-1}^j\int_0^1x^{ik+j}dx \\ &=(k-1)!\sum_{i=1}^\infty\int_0^1(1-x)^{k-1}x^{ik}dx \\ &=(k-1)!\int_0^1\sum_{i-1}^\infty x^{ik}(1-x)^{k-1}dx \\ &=(k-1)!\int_0^1\frac{(1-x)^{k-1}}{1-x^k}dx \\ &【前方高能预警】 \\ &=k!\int_0^1\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{1-\varepsilon^j x}dx &(\varepsilon=e^{\frac{2i\pi}{k}}) \\ &=-k!\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{\varepsilon^j}\ln(1-\varepsilon^j) \\ &=-k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\ln(1-\varepsilon^j) \\ &【什么？你以为这就完了？图森破】 \\ &=k!\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\sum_{i=1}^\infty\frac{\varepsilon^{ij}}{i} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\varepsilon^{ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\varepsilon^{jl+ij} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\sum_{j=1}^{k-1}\varepsilon^{j(i+l)} \\ &=k!\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l(-1+[(i+l)\bmod{k}=0]k) \\ &=k!\sum_{i=1}^\infty\frac{1}{i}(\sum_{l=0}^{k-1}(-1)^{k-l}C_{k-1}^l+k(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}) \\ &=(k-1)!\sum_{i=1}^\infty\frac{(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}}{i} \\ &=(k-1)!\sum_{i=1}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=\sum_{i=1}^\infty\prod_{j=1}^k\frac{1}{ik+j} \\ &【登登登！成功推回来啦！】 \end{align*} 所以问题来了，这个式子还有更简洁的结果嘛？

$$[f(x)-e^x]^2=\sum_{i=0}^Na_i^2x^{2i}+2\sum_{i=0}^{N-1}\sum_{j=i+1}^Na_ia_jx^{i+j}-2\sum_{i=0}^Na_ix^ie^x$$
$$(x^i)'=ix^{i-1}\Rightarrow\int_0^1x^i\mathrm{d}x=\frac{1}{i+1}1^{i+1}-\frac{1}{i+1}0^{i+1}=\frac{1}{i+1}$$
然后并没有想清楚 $x^ie^x$ 定积分怎么求，就开始手算小数据：
$$(x^ie^x)'=(ix^{i-1}+x^i)e^x$$
$$\Rightarrow [(x-1)e^x]'=xe^x$$
$$\Rightarrow [(x^2-2x+2)e^x]'=x^2e^x$$
$$\Rightarrow [(x^3-3x^2+6x-6)e^x]'=x^3e^x$$
这样归纳一下好像就推出来了：
$$(e^x\sum_{i=0}^n(-1)^iA_n^ix^{n-i})'=x^ne^x\Rightarrow\int_0^1x^ne^x\mathrm{d}x=e\sum_{i=0}^n(-1)^iA_n^i-(-1)^nn!$$
这么看来原式应该就等于
$$\sum_{i=0}^N\frac{1}{2i+1}a_i^2+2\sum_{i=0}^{N-1}\sum_{j=i+1}^N\frac{1}{i+j+1}a_ia_j-2\sum_{i=0}^N[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]a_i$$
只有二次诶，那只要对每个 $a_i$ 令偏导为 $0$ 就行了，就能得到一个一次方程组，用高斯消元解方程组就做完了，可是 $a_i=\sum_{j=0}^\infty p_{ij}\cdot e^j$ 什么鬼？？难道要把多项式放进去消元，这个是要炸的呀。看了下方程组发现系数矩阵 $A$ 的数都是有理数，那么解方程 $Ax=b$（$x,b$ 为列向量）得到 $x=A^{-1}b$，而 $b$ 中的数都能表示成 $p_0+p_1e$ 的形式，所以答案 $x$ 也能表示成 $p_0+p_1e$ 的形式。
出题人真坑，明明答案是 $p_0+p_1$ 的形式，只有 $p_{i0},p_{i1}$ 是有用的，题面偏要写成 $\sum_{j=0}^\infty p_{ij}$ 误导别人存整个多项式。然后又只要输出有用的那两个数。坑爹！！
推导这里就开始写，写完之后测了下样例 $N=0$ 过了，$N=1$ 的WA了。开始怀疑算法有没错。或者是哪一步推导错了。好虚啊。

均衡队列的代码复制一下略加修改就能拿70分。。

这个题目到底是要问下标还是数值啊啊啊啊啊啊啊啊

第一种方法是强行化简这个式子。
首先S(i,j)当j>i时是0，所以原式可写成$\sum_{i=0}^n\sum_{j=0}^nS(i,j)*2^j*j!$
再考虑如何求$S(n,m)*m!$，它的意义是n个不同的球，放进m个不同的盒子里，盒子不允许空的方案数，求它的通项有很多方法，这里介绍比较简便的生成函数求法。
我们固定m，并定义多项式$A(x)=\sum_{i=0}^\infty A_i\frac{x^n}{n!}$的每一项系数$A_i$表示$S(i,m)*m!$
那$A(x)=(e^x-1)^m$（想一想，为什么）。
于是$S(n,m)*m!$即$\frac{x^n}{n!}$的系数就是$\sum_{j=0}^n(-1)^kC_j^k(j-k)^i$
原式即变为$\sum_{i=0}^n\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^kC_j^k(j-k)^i$
变形得$\sum_{j=0}^n2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}*\frac{\sum_{i=0}^n\;(j-k)^i}{(j-k)!}$
定义多项式$F(x)$的每一项$F_i=\frac{(-1)^i}{i!}$，定义多项式$G(x)$的每一项$G_i=\frac{\sum_{j=0}^ni^j}{i!}$，定义多项式$H(x)=F(x)*G(x)$
则$ans=\sum_{j=0}^n2^j*j!*H_j$
NTT一发就行了。
第二种方法是考虑原式的意义。
$F_i=\sum_{j=0}^iS(i,j)*2^j*j!$的意义是把n个不同的球，放进若干个不同的盒子了，盒子不允许空，每个盒子有两种状态的方案数。
枚举最后一个盒子的球数可得递推式$F_i=\sum_{j=1}^i2C_i^jF_{i-j}$
变形得$\frac{F_i}{i!}=\sum_{j=1}^i\frac 2{j!}*\frac{F_{i-j}}{(i-j)!}$
这是个卷积的形式，多项式求逆或者分治搞一搞就行了。

$$ \begin{align} f(n)&=\sum_{i=0}^n\sum_{j=0}^i S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n S(i,j)*2^j*(j!)\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*(j!)* \frac 1{j!}*\sum_{k=0}^j(-1)^kC_k^j(j-k)^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}C_k^jk^i\\ &=\sum_{i=0}^n\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*k^i\\ &=\sum_{j=0}^n 2^j*\sum_{k=0}^j(-1)^{j-k}*\frac{j!}{k!(j-k)!}*\sum_{i=0}^nk^i\\ &=\sum_{j=0}^n 2^j*j!*\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!} \end{align} $$
其中$\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}*\frac{\sum_{i=0}^nk^i}{k!}$交给我们伟大的NTT处理，令$a_i=\frac{(-1)^{j-i}}{(j-i)!}$，$b_i=\frac{\sum_{i=0}^nk^i}{k!}=\frac{i^{n+1}-1}{(i-1)*i!}$，$c_i=\sum_{k=0}^ia_k*b_{i-k}$，则$ans=\sum_{j=0}^n 2^j*j!*c_j$。

zkw

回复 @叶子の宿敌 :
是很水好不好

回复 @叶子の宿敌 :
是很水好不好

线段树数组要*4……

线段树有点慢呢……