专栏文章

11月

TT0mle
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbwksr
此快照首次捕获于
2025/12/01 23:53
3 个月前
此快照最后确认于
2025/12/01 23:53
3 个月前
查看原文

CF1553H

deepthink 一会。
好吧想明白了，挺唐的。
考虑两个数在 trie 上的 lca 算贡献。
那就枚举 lca，记 lca 的 dep 为 dd，dd 前的二进制位没用，暴力枚举后面的位，用一些技巧维护，在 trie 上走。
最后算一算。
复杂度是 O(k2k)O(k2^k)。
如何 *2900。

P6108

方差：s2=∑i=1nai2n−∑i=1n∑j=1naiajn2s^2=\frac{\sum_{i=1}^na_i^2}n-\frac{\sum_{i=1}^n\sum_{j=1}^na_ia_j}{n^2}。
贡献分成三部分：ai2n,ai2n2,aiajn2\frac{a_i^2}n,\frac{a_i^2}{n^2},\frac{a_ia_j}{n^2}，算个系数即可。
L=r−l+1L=r-l+1。
第一部分：
∑i=1L(L−1i−1)i=1L∑i=1L(Li)=2L−1L\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}
第二部分：
∑i=1L(L−1i−1)i2=1L∑i=1L(Li)i=1L∑i=1L∑j=1L(j−1i−1)i=1L∑i=1L∑j=1L(ji)j=1L∑j=1L2j−1j\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}
简单算。
第三部分：
∑i=2L(L−2i−2)i2=1L(L−1)∑i=1L(i−1)(Li)i=1L(L−1)∑i=1L∑j=1L(j−1i−1)i−1i=1L(L−1)∑i=1L∑j=1L(ji)i−1j=1L(L−1)∑j=1L1j∑i=1L(ji)(i−1)=1L(L−1)∑j=1L(∑i=1L(ji)i)−(2j−1)j=1L(L−1)∑j=1Lj2j−1−2j+1j\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+mlog⁡n)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

单位根反演大学习。
∑i=0n(ni)Fi[k∣i]=∑i=0n(ni)Fi1k∑j=0k−1ωkij=1k∑j=0k−1∑i=0n(ni)Fiωkij\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)=∑i=0n(ni)FixiG(x)=\sum_{i=0}^n\binom niF_ix^i，原式就是 1k∑j=0k−1G(ωkj)\frac1k\sum_{j=0}^{k-1}G(\omega_k^j)。
然后发现斐波那契很涩啊，直接拆成 ϕ\phi 和 ψ\psi 就能二项式反演了。
G(x)=55[ϕ(1+ϕx)n−ψ(1+ψx)n]\boxed{ G(x)=\frac{\sqrt5}5[\phi(1+\phi x)^n-\psi(1+\psi x)^n] }
然后吃对 55 的二次剩余性吃两坨史。
哎卧槽 p=2p=2 怎么这么坏。
被击杀了，老实玩矩阵去了。
G(x)=(x+1xx1)1,1nG(x)={\begin{pmatrix} x+1 & x\\ x & 1 \end{pmatrix}}^n_{1,1}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...