SPOJ FIBONOMIAL Fibonacci Polynomial
SPOJ Luogu 分析 为了方便，设 两个求和号中的部分利用等比数列求和公式计算即可。 但是 $5$ 在模 $10^9+7$ 意义下没有二次剩余，所以需要扩域。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ============...
分类 题解 下的文章
- 首页
- 题解
ARC083E Bichrome Tree
AtCoder Luogu 分析 首先注意到黑色还是白色并不重要，因为黑白可以互换。因此我们染一棵子树的根节点时可以强制让它为黑色。 那么，当染一棵子树的根节点 $u$ 时，子树中黑点的权值和应为 $X_u$ ，白点的权值和应该尽量小。 这里白点权值和尽量小是贪心的思想，因为权值尽量小是一定能通过一些更改满足条件。 于是可以考虑 DP。设 $f_u$ 表示以 $u$ 为根的子树中白点权值和最...
CF718C Sasha and Array
Codeforces Luogu 分析 考虑怎么用矩阵求出斐波那契数列的。有 为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。 考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。 注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的...
CF1215F Radio Stations
Codeforces Luogu 分析 很神仙的 2-SAT 。 设表示第 $i$ 个电台启用的点为 $yes(i)$ ，表示第 $i$ 个电台不启用的点为 $no_i$ 。 先考虑一下 $u$ 和 $v$ 至少启用一个怎么连边。连 $no(u)\to yes(v)$ 和 $no(v)\to yes(u)$ 即可。 再考虑一下 $u$ 和 $v$ 不能同时启用怎么连边。连 $yes(u)\t...
洛谷4619 [SDOI2018]旧试题
Luogu LOJ 分析 首先要知道 显然我们可以 $O(C\log C)$ 预处理出 $f_a,f_b,f_c$ ，然而计算还是 $O(n^3)$ 的。 但是注意到 $O(n^3)$ 的枚举中会出现很多贡献为 $0$ 的情况： $\mu(x),\mu(y),\mu(z)$ 中有 $0$ 。 $\operatorname{lcm}(x,y)>A$ 或 $\operatorname{...
洛谷1829 [国家集训队]Crash的数字表格 / JZPTAB
Luogu 分析 下文中，设 $n\leq m$ ，$n/m=\left\lfloor\frac{n}{m}\right\rfloor$ 。 为了方便，设 $S(n)=\sum_{i=1}^ni=\frac{n(n+1)}{2}$ 。 令 $\mathbf{f}(i)=\frac{1}{i}$，$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 括号内线性筛预处理，然后数论分...
CF809E Surprise me!
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了... 首先要知道 $f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...
洛谷2150 [NOI2015]寿司晚宴
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子，因此我们可以只状压 $<\sqrt{500}$ 的质因子，然后再单...
CF332C Students' Revenge
Codeforces 分析 贪心地想可以知道，主席一定优先做 $b$ 最大的，如果 $b$ 相同会做 $a$ 最小的。 那么我们把所有任务排序，使得优先级越高的越靠后。 现在假设我们选了 $p$ 个任务出来，那么一定存在一条分界线，使得线前的主席都不做，线后的主席都做。 于是我们可以枚举分界线的位置，然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个，这就是这条线...
UVA1498 Activation
UVa Luogu 分析 首先把 $p_4=0$ 的情况判掉，答案显然为 $0$ 。 考虑 DP 。设 $dp_{i,j}$ 表示 $i$ 个人的队列，现在在第 $j$ 个，最后在前 $k$ 个位置的概率。 转移可以考虑后继状态，容易得到 于是可以得到 $dp_{1,1}=\frac{p_4}{1-p_1-p_2}$ 。 具体实现及细节见代码。 代码 // ================...