Loading...
博主已经退役,评论可能会审核很久才能通过。
Codeforces Luogu 分析 考虑怎么用矩阵求出斐波那契数列的。有 为了方便,下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。 考虑使用线段树维护。每个叶子节点维护一个矩阵:若该位置的值为 $i$ ,则维护的矩阵为 $Q^{i-1}$ 。 注意到矩阵乘法是满足分配律的,那么我们只需要求 $[l,r]$ 内所有维护的矩阵的...
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...
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{...
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$ 。 括号内线性筛预处理,然后数论分...
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题,报警了... 首先要知道 $f$ 和 $g$ 都很好转移,同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况,所以要答案要乘 $2$ ;最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数,小 G 选的数的质因子集合为 $j$ ,小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子,因此我们可以只状压 $<\sqrt{500}$ 的质因子,然后再单...
Codeforces 分析 贪心地想可以知道,主席一定优先做 $b$ 最大的,如果 $b$ 相同会做 $a$ 最小的。 那么我们把所有任务排序,使得优先级越高的越靠后。 现在假设我们选了 $p$ 个任务出来,那么一定存在一条分界线,使得线前的主席都不做,线后的主席都做。 于是我们可以枚举分界线的位置,然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个,这就是这条线...
UVa Luogu 分析 首先把 $p_4=0$ 的情况判掉,答案显然为 $0$ 。 考虑 DP 。设 $dp_{i,j}$ 表示 $i$ 个人的队列,现在在第 $j$ 个,最后在前 $k$ 个位置的概率。 转移可以考虑后继状态,容易得到 于是可以得到 $dp_{1,1}=\frac{p_4}{1-p_1-p_2}$ 。 具体实现及细节见代码。 代码 // ================...
UVa Luogu Vjudge 分析 梅森素数:形如 $2^p-1$ 的素数,其中 $p$ 是素数。 关于梅森素数有一个定理: $N$ 的约数和能够写成 $2^k\;(k\in\mathbb{N})$ 的充要条件为 $N$ 能够写成一些 $\textbf{互不相同}$ 的梅森素数的积。 于是考虑让 $N$ 为一些不同的梅森素数的积。 对于 $p_i$ ,如果它能够表示为不同的梅森素数的...
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂,于是直接 FFT 就可以了。 (大概)可以理解成概率生成函数卷积? 然而 FFT 掉精度很严重,我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论: 设有 $n$ 个独立同分...