12.5 ~ 12.11 总结
UOJ450【集训队作业2018】复读机
\(k\) 个对象，\(n\) 个操作，每次操作选一个对象出来，需要满足每个对象最后出现了 \(d\) 的倍数次。问方案数。\(d \le 3, n \le 10^9, k \le 5\times 10^5\)。
指数型生成函数。
- \(d = 1\)， \(F(x) = e^{kx}\)，答案就是 \(k^n\)。
- \(d = 2\)，构造 $ F(x) = (\dfrac{e^{x} + e^{-x}}{2} ) ^ k$ 表示
\((\{1,1,1,1,\dots \}\) + \(\{1,-1,1,-1,\dots\} ) / 2\)。
二项式定理展开可以得到 \(\sum_{i+j=k} e^{2i-k} \dbinom{k}{i}\) 取 \(n\) 次项系数是容易的。 - \(d = 3\)，使用单位根 \(\omega\)，满足 \(\omega ^ 2 + \omega + 1 = 0\)。
构造 \(F(x) = (\dfrac{e^x + e^{wx} + e^{w^2 x}}{3} ) ^ k\)
注意到可以暴力算卷积，\(\sum\limits_{i+j+l=k} ...\)。
11 B
每个位置有一个颜色，求区间内颜色相同两个数的最小距离。 \(n\le 5\times 10^5\)
使用 \(i-p_i\) 更新答案，这样需要满足 \(p_i \ge l\), 扫描线随便搞搞。
11 C
每个点可以向左边或者右边相聚 \(k\) 人传递能量，要求最后每个人到达平均值，保证可以，问最小传递次数。 \(n\le 10^5\)。
把每个环拉出来就是 平衡负载问题。
考虑每个点 \(i\) 最终向右边给 \(x_i\) 个。
有这样 \(n-1\) 个方程
以 \(x_1\) 为主元。
\[x_1 = x_1 \]\[x_2 = a_2 + x_1 - aver \]\[x_3 = a_3 + a_2 + x_1 - aver \]\[x_4 = a_4 + a_3 + a_2 + x_1 - aver \]不妨设 \(c_i = \sum\limits_{j=2}^{i}a_j - aver\)
就是要找到一个 \(x_1\) 让 \(\sum_{|c_i - x_1|}\) 最小，取中位数就好了。
群论
HDU1883
给一些点，问一个 \(r\) 的圆最多能覆盖多少点。 \(n\le 2000\)
答案最后可以使得一个点在圆上，那么圆心就是一个圆，每个合法的可以被这个圆覆盖到的是一段弧，离散下来然后差分前缀和一下。
标签：总结,10,le,12.11,sum,12.5,aver,每个 From： https://www.cnblogs.com/Lates/p/16974103.html