11月
T0mle
·
·
个人记录
CF1553H
deepthink 一会。
好吧想明白了，挺唐的。
考虑两个数在 trie 上的 lca 算贡献。
那就枚举 lca，记 lca 的 dep 为 d，d 前的二进制位没用，暴力枚举后面的位，用一些技巧维护，在 trie 上走。
最后算一算。
复杂度是 O(k2^k)。
如何 *2900。
P6108
方差：s^2=\frac{\sum_{i=1}^na_i^2}n-\frac{\sum_{i=1}^n\sum_{j=1}^na_ia_j}{n^2}。
贡献分成三部分：\frac{a_i^2}n,\frac{a_i^2}{n^2},\frac{a_ia_j}{n^2}，算个系数即可。
第一部分：
$$
\begin{aligned}
\sum_{i=1}^L\frac{\binom{L-1}{i-1}}i
&=\frac1L\sum_{i=1}^L\binom Li
\\&=\frac{2^L-1}L
\end{aligned}
$$
第二部分：
$$
\begin{aligned}
\sum_{i=1}^L\frac{\binom{L-1}{i-1}}{i^2}
&=\frac1L\sum_{i=1}^L\frac{\binom Li}i
\\&=\frac1L\sum_{i=1}^L\sum_{j=1}^L\frac{\binom{j-1}{i-1}}i
\\&=\frac1L\sum_{i=1}^L\sum_{j=1}^L\frac{\binom ji}j
\\&=\frac1L\sum_{j=1}^L\frac{2^j-1}j
\end{aligned}
$$
简单算。
第三部分：
$$
\begin{aligned}
\sum_{i=2}^L\frac{\binom{L-2}{i-2}}{i^2}
&=\frac1{L(L-1)}\sum_{i=1}^L\frac{(i-1)\binom Li}i
\\&=\frac1{L(L-1)}\sum_{i=1}^L\sum_{j=1}^L\binom{j-1}{i-1}\frac{i-1}i
\\&=\frac1{L(L-1)}\sum_{i=1}^L\sum_{j=1}^L\binom ji\frac{i-1}j
\\&=\frac1{L(L-1)}\sum_{j=1}^L\frac1j\sum_{i=1}^L\binom ji(i-1)
\\&=\frac1{L(L-1)}\sum_{j=1}^L\frac{(\sum_{i=1}^L\binom jii)-(2^j-1)}j
\\&=\frac1{L(L-1)}\sum_{j=1}^L\frac{j2^{j-1}-2^j+1}j
\end{aligned}
$$
也简单算。
线段树维护一些东西就完了。
仔细一点做到 $O(n+m\log n)$，怎么直接最优解了。
```cpp
void solve() {
rd(n), rd(m);
pw[0] = 1;
rep(i, 1, n) (pw[i] = pw[i - 1] + pw[i - 1]) >= mod && (pw[i] -= mod);
inv[1] = 1;
rep(i, 2, n) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
rep(i, 1, n) a[i] = (pw[i] - 1ll) * inv[i] % mod, (b[i] = b[i - 1] + a[i]) >= mod && (b[i] -= mod);
rep(i, 1, n) b[i] = 1ll * b[i] * inv[i] % mod;
rep(i, 1, n) c[i] = (c[i - 1] + (1ll * i * pw[i - 1] - pw[i] + 1 + mod) % mod * inv[i]) % mod;
rep(i, 1, n) c[i] = 1ll * c[i] * inv[i] % mod * inv[i - 1] % mod;
build(1, 1, n);
while (m--) {
rd(op);
if (op == 1) {
rd(l), rd(r), rd(x);
maketag(1, l, r, x);
} else {
rd(l), rd(r);
Info dat = query(1, l, r);
int L = r - l + 1;
int ans1 = 1ll * dat.b * a[L] % mod;
int ans2 = 1ll * dat.b * b[L] % mod;
int ans3 = (1ll * dat.a * dat.a - dat.b + mod) % mod * c[L] % mod;
wrt((0ll + ans1 - ans2 - ans3 + mod + mod) % mod), putchar(10);
}
}
}
```
### [P10664](/problem/P10664)
单位根反演大学习。
$$
\begin{aligned}
&\sum_{i=0}^n\binom niF_i[k\mid i]
\\=&\sum_{i=0}^n\binom niF_i\frac1k\sum_{j=0}^{k-1}\omega_k^{ij}
\\=&\frac1k\sum_{j=0}^{k-1}\sum_{i=0}^n\binom niF_i\omega_k^{ij}
\end{aligned}
$$
记一个多项式 $G(x)=\sum_{i=0}^n\binom niF_ix^i$，原式就是 $\frac1k\sum_{j=0}^{k-1}G(\omega_k^j)$。
然后发现斐波那契很涩啊，直接拆成 $\phi$ 和 $\psi$ 就能二项式反演了。
$$
\boxed{
G(x)=\frac{\sqrt5}5[\phi(1+\phi x)^n-\psi(1+\psi x)^n]
}
$$
然后吃对 $5$ 的二次剩余性吃两坨史。
哎卧槽 $p=2$ 怎么这么坏。
被击杀了，老实玩矩阵去了。
$$
G(x)={\begin{pmatrix}
x+1 & x\\
x & 1
\end{pmatrix}}^n_{1,1}
$$