洛谷2150 [NOI2015]寿司晚宴
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数,小 G 选的数的质因子集合为 $j$ ,小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子,因此我们可以只状压 $<\sqrt{500}$ 的质因子,然后再单...
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数,小 G 选的数的质因子集合为 $j$ ,小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子,因此我们可以只状压 $<\sqrt{500}$ 的质因子,然后再单...
UVa Luogu Vjudge 分析 梅森素数:形如 $2^p-1$ 的素数,其中 $p$ 是素数。 关于梅森素数有一个定理: $N$ 的约数和能够写成 $2^k\;(k\in\mathbb{N})$ 的充要条件为 $N$ 能够写成一些 $\textbf{互不相同}$ 的梅森素数的积。 于是考虑让 $N$ 为一些不同的梅森素数的积。 对于 $p_i$ ,如果它能够表示为不同的梅森素数的...
Luogu 分析 完全图的生成树个数为 $n^{n-2}$ ,每条边会出现 $2n^{n-3}$ 次。 容易得到答案为 考虑怎么计算 $\sum_{i=n+1}^{2n-1}i^k$ 。可以发现 $i^k$ 是完全积性函数,直接线性筛后求前缀和即可。 整理一下思路: 首先线性筛求出 $i^k$ ,然后求出它的前缀和。此部分时间复杂度为 $O(k)$。 然后利用算出的前缀和,递推计算出 ...
Luogu LOJ 分析 因为 $e_1\perp e_2$ ,所以会存在一对数 $s,t$ ,满足 $e_1s+e_2t=1$ 。 我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形: 于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ,所以可以直接 exgcd 求出 $s$ 和 $t$ 。 然而这里求出的 $s$ 和 $t$ 一正一负,为了方便我...
Luogu LOJ 分析 先来考虑 $n=1$ 的情况,可以发现所有能取到的体积为 $k\cdot\gcd(v,P)$ 。于是我们可以直接把体积设成 $\gcd(v,P)$ 。 这样子所有体积都是 $P$ 的约数了。考虑预处理出 $P$ 的所有约数,然后求出每种约数在体积中的出现次数。 注意到一条性质:重复选取相同的体积对答案没有影响。于是假设第 $i$ 个约数有 $s_i$ 个,那么这个约...
Luogu 分析 首先要知道一个性质 即可。可以发现就是 这个题 $k=2$ 时的版本,直接复制过来即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #incl...
Codeforces 分析 我们直接令 $n = 2000$,并在前面放 $1998$ 个 $0$,然后设 $1999$ 项为 $-d$ ,$2000$ 项为 $x+d$ 。 那么正确答案是 $2000x$ ,Alice 算出来的答案是 $x+d$ ,两者的差为 $1999x-d$ 。 那么 $1999x-d=k\Rightarrow x=\frac{k+d}{1999}$ 。随便找一组满足...
Luogu BZOJ 分析 已知 $X_{i+1}\equiv aX_i+b\pmod p$ 。 两边加上 $\frac{b}{a}$ 后再乘上 $a$ ,变为 $a$、$b$、$X_1$、$X_i$(就是题目中的 $t$) 全部已知,BSGS 解出 $i$ 即可。 然后还有一些特判: $X_1=t$,答案为 $1$ 。 $a=0$,此时对于任意的 $i$ ,都有 $X_i=b$ 。所以...
Luogu 分析 同余类最短路。 设 $a$ 中的最小值为 $k$ 。容易发现,如果能表示出 $xk+t\;(0\leq t<k)$ ,那么也能表示出 $(x+1)k+t$ 。 把 $t$ 看做余数,然后对于每个 $a_i$ ,从 $t$ 向 $(t+a_i) \bmod k$ 连一条边权为 $a_i$ 的边。 然后跑 SPFA 求出最短路,再对每个余数统计答案即可。 代码 //It ...
Luogu 分析 设 $\mathbf{f}(i)=i^k$,$\mathbf{g}(i)=\mathbf{f}*\mu$ 。 线性筛 $\mathbf{g}$ 的前缀和,然后数论分块计算即可。 代码 //It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib...