LuoguLOJ分析显然二合一,先考虑 $m=2$ 的情况。可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便,我们把 $l,r$ 都加上 $1$,那么相当于要求用同样的方法扩域计算即可。代码// ==================================== // author: M_sea // website: https://m-sea...
LuoguGym分析一个做法是直接 meet in the middle,复杂度 $\mathcal{O}(2^{n/2})$,并不能过 $n\leq 64$。但是题目中还有一个奇妙的性质 $a_i > \sum_{j=1}^{i-1} a_j$,套用得到 $a_1<2^{65-n}$。发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小,这启发我们在 $n$ 大时去枚举 $a...
CodeforcesLuogu分析首先有一个定理:${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。于是可以把 $A$ 转成 $p$ 进制,然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位,进位 $j$ 次,第 $i-1$ 位是否向第 $i$ 位进位,$a+b$ 是否顶着 $A$ 的上界的方案数。转移比...
Div1Div2从一月份一直咕到现在的一场比赛 /kelConneR and the A.R.C. Markland-N暴力往两边找即可。代码JOE is on TV!显然每次淘汰掉刚好一个人是最好的。答案即为 $\sum_{i=1}^n\frac{1}{i}$。代码NEKO's Maze Game维护每个格子是否是岩浆,当一个格子改变时维护一下上下两格都是岩浆的列数即可。代码Aroma's...
比赛地址4-adjacent我们把所有数分成 $3$ 类:$4$ 的倍数、不是 $4$ 的倍数但是是 $2$ 的倍数、奇数。那么肯定是第三种和第一种交错排,在最后放第二种最好。直接判一下第一种的数量是否 $\geq$ 最后一种的数量即可。当没有第二种数时最后还可以放一个第三种数,此时应该是第一种的数量 $+1\geq$ 最后一种的数量。代码Grid Coloring蛇形填上每种颜色即可。代码...
比赛地址Factors of Factorial直接把 $1\sim n$ 分解质因数即可。代码Walk and Teleport显然从左往右走是最优的,相邻两个选更小的方式即可。代码Grouping设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。转移时枚举人数 $=j$ 的组数 $k$,那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个,然...
CodeforcesLuogu分析根据一些小学奥数知识可以知道第一个数应该是 $2^x3^y$ 的形式,而且 $y\in\{0,1\}$ ,因为 $>3$ 的质因子我们换成 $2^k$ 更优,$3^2$ 换成 $2^3$ 更优。为了方便设 $m=\lfloor\log_2 n\rfloor$。考虑 DP。设 $dp_{i,x,y}$ 表示前 $i$ 个数,当前的 $\gcd$ 是 $2...
Luogu分析先莫比乌斯反演一下后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$,显然是积性函数,所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$,所以只要算两项即可。至于 $f_i$,可以求拉格朗日插值公式中每项系数求出,也可以直接高斯消元。代码// ========...
LuoguLOJ分析先简单介绍一下阶。设 $\gcd(a,p)=1$,则满足 $a^x\equiv 1\pmod p$ 的最小正整数 $x$ 被称为 $a$ 在模 $p$ 意义下的阶,记做 $\operatorname{ord}_pa=x$阶有这样一些性质(这里没有证明,可以自行查找相关资料):$\operatorname{ord}_p a|\varphi(p)$。于是我们可以枚举 $\va...
LuoguLOJ分析先筛出 $10^6$ 以内的质数,然后把 $a_i$ 除掉这些质数,这样子每个 $a_i$ 至多剩下两个质因子。可以直接 Pollard-Rho 求出剩下的质因子。这样子第一问的答案即为最多的质因子出现次数,第二问的答案即为 $2$ 的出现次数等于第一问答案的质因子个数次方减 $1$,写个高精度即可。不想写 Pollard-Rho 怎么办?只剩下一个质因子和剩下两个相同质...