数学题选做

由于之后文章长度越来越长然后特别卡，所以代码都放在云剪贴板里了（ --- ### [P1290 欧几里德的游戏](https://www.luogu.com.cn/problem/P1290) 考虑到当某一个数是另一个数的两倍时先手必胜。于是只要考虑不超过两倍的情况即可。递归处理。 [代码。](https://www.luogu.com.cn/paste/u3hvlrd3) --- ### [P1247 取火柴游戏](https://www.luogu.com.cn/problem/P1247) Nim 游戏简单结论：异或和不为 $0$ 即可。证明直接用二进制拆分证。 构造方案直接跟每个数异或比大小就行。 [代码。](https://www.luogu.com.cn/paste/3zyq7adm) --- ### [P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈](https://www.luogu.com.cn/problem/P2252) 记结论： $$\left\lfloor\dfrac{\sqrt{5} + 1}{2}\left(b - a \right)\right\rfloor = a$$ 此时先手必败。 [代码。](https://www.luogu.com.cn/paste/d3ll3pkx) --- ### [P3338 [ZJOI2014]力](https://www.luogu.com.cn/problem/P3338) 带入化简式子会变为： $$E_i=\sum_{j=1}^i\dfrac{q_j}{(i-j)^2}-\sum_{j=i}^n\dfrac{q_j}{(j-i)^2}$$ 记 $g_{i} = \dfrac{1}{i^2}$，那么： $$E_i=\sum_{j=1}^iq_jg_{i-j}-\sum_{j=i}^nq_jg_{j-i}$$ 记 $g_0 = q_0 = 0$。 $$E_i=\sum_{j=0}^iq_jg_{i-j}-\sum_{j=0}^{n-i}q_{j+i}g_j$$ 记 $f_i = q_{n - i}$，就是将 $q$ 翻转一下。 $$E_i=\sum_{j=0}^iq_jg_{i-j}-\sum_{j=0}^{n-i}g_jq_{n-i-j}$$ 记 $n-i=m$。 $$E_i=\sum_{j=0}^iq_jg_{i-j}-\sum_{j=0}^{m}g_jq_{m-j}$$ 是个卷积式，直接 FFT 即可。 [代码。](https://www.luogu.com.cn/paste/uv5z5rk4) ---- ### [P3723 [AH2017/HNOI2017]礼物](https://www.luogu.com.cn/problem/P3723) 即求：~~下面那个东西拼成了我的名字qwq~~ $$(\sum_{i=1}^n(x_i + c - y_i))_{\min}$$ 其中 $y_i$ 可以旋转。 展开： $$\sum_{i=1}^n{x_i}^2+\sum_{i=1}^n{y_i}^2+nc^2+2c\sum_{i=1}^nx_i-2c\sum_{i=1}^ny_i - 2\sum_{i=1}^nx_iy_i$$ 发现只有最后的一项是不确定的，于是求那个最大值即可。 模仿上一题，令 $z_i = y_{n - i + 1}$，那么即为： $$\sum_{i=1}^nx_iz_{n-i+1}$$ 可以卷积了。将反数组倍长，卷积后找一下末 $n$ 项最大值即可。 [代码。](https://www.luogu.com.cn/paste/0tlwu8lu) --- ### [P5432 A/B Problem (高精度除法)](https://www.luogu.com.cn/problem/P5432) 不会，咕。 --- ### [P5577 [CmdOI2019]算力训练](https://www.luogu.com.cn/problem/P5577) 不会，咕 --- ### [P5245 【模板】多项式快速幂](https://www.luogu.com.cn/problem/P5245) 简单题，一句话题解： $$F^k(x) = e^{k\ln F(x)}$$ [代码。](https://www.luogu.com.cn/paste/jwzx3wo8) --- ### [P5343 【XR-1】分块](https://www.luogu.com.cn/problem/P5343) 普通 DP 之后发现转移都相同，矩阵快速幂即可。 [代码。](https://www.luogu.com.cn/paste/6a7nxe6g) --- ### [P5337 [TJOI2019]甲苯先生的字符串](https://www.luogu.com.cn/problem/P5337) 记 $f_{i, j}$ 为前 $i$ 个字符末尾为 $j$ 的方案数，$g_{i, j}$ 为 $i, j$ 是否可以相邻。 显然有: $$f_{i, j} = \sum_{k=1}^{26}f_{i - 1, k}g_{k, j}$$ 发现状态转移均相同，矩阵快速幂优化即可。 [代码。](https://www.luogu.com.cn/paste/cj2qwk4k) --- ### [P4967 黑暗打击](https://www.luogu.com.cn/problem/P4967) ~~众所周知，看到这种输入量少的题，我们应当找规律。~~ 直接列出前四项：1 6 26 100 然后放到 [OEIS](http://oeis.org/) 上找到了[这个东西](http://oeis.org/A094811)，发现第 $12$ 项也一样，所以可以大胆猜测这是对的。 然后找到其递推公式： $$a_n = 6a_{n-1}-10a_{n-2}+4a_{n-3}$$ 矩阵快速幂即可。 [代码。](https://www.luogu.com.cn/paste/pj626c26) --- ### [P4781 【模板】拉格朗日插值](https://www.luogu.com.cn/problem/P4781) 考虑构造以下多项式： $$f(x)=\sum_{i=1}^ny_i\prod_{j=1}^n[j \neq i]\dfrac{x - x_j}{x_i - x_j}$$ 显然这 $n$ 个点带进去均成立。 直接计算 $f(k)$ 即可。 [代码。](https://www.luogu.com.cn/paste/6w8diqjk) --- ### [P5158 【模板】多项式快速插值](https://www.luogu.com.cn/problem/P5158) 不会，咕。 --- ### [P7141 [THUPC2021 初赛] 棋盘](https://www.luogu.com.cn/problem/P7141) 不会，咕。 --- ### [P5372 [SNOI2019]积木](https://www.luogu.com.cn/problem/P5372) 不会，咕。 --- ### [P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768) 一顿操作猛如虎： $$\begin{aligned}\text{原式}&=\sum_{d=1}^nd^3\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor}ij[\gcd(i, j)=1]\\&=\sum_{d=1}^nd^3\sum_{k=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\mu(k)\cdot k^2\cdot S(\left\lfloor \frac{n}{kd} \right\rfloor, \left\lfloor \frac{n}{kd} \right\rfloor)\end{aligned}$$ 其中 $S(n, m)=\sum_{i=1}^n\sum_{j=1}^mij=\dfrac{n(n+1)}{2}\cdot\dfrac{m(m+1)}{2}$ 套路地令 $T=kd$，调换求和顺序可得： $$\begin{aligned}\text{原式}&=\sum_{T=1}^nT^2\sum_{d\mid T}\mu(d)\cdot\dfrac{T}{d}\cdot S(\left\lfloor \frac{n}{T} \right\rfloor\left\lfloor \frac{n}{T} \right\rfloor)\\&=\sum_{T=1}^nT^2\cdot\varphi(T)\cdot S(\left\lfloor \frac{n}{T} \right\rfloor, \left\lfloor \frac{n}{T} \right\rfloor)\end{aligned}$$ 用杜教筛求 $\varphi$ 的前缀和，然后数论分块就行，时间复杂度为 $O(n^{\frac{2}{3}})$。 [代码。](https://www.luogu.com.cn/paste/gsmu3w7a) --- ### [P1587 [NOI2016] 循环之美](https://www.luogu.com.cn/problem/P1587) 首先，经过一系列推导可得： $$ans = \sum_{i=1}^n\sum_{j=1}^m[i \perp j][j \perp k]$$ 记 $N=\min\{n, m\}$。 化简： $$\begin{aligned}ans&=\sum_{i=1}^n\sum_{j=1}^m[j\perp k]\sum_{d\mid \gcd(i, j)}\mu(d)\\&=\sum_{d=1}^N\mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor[d \perp k]\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[j \perp k]\end{aligned}$$ 记 $$s(i) = \sum_{j=1}^i[j \perp k]$$ 由于 $\gcd(j, k) = \gcd(j + k, k)$，于是有 $$s(i) = \left\lfloor\dfrac{n}{k}\right\rfloor\varphi(k)+s(i \bmod k)$$ 这里也可以感性理解一下，就是 $k$ 个一循环。 代入： $$ans = \sum_{d=1}^N\left\lfloor\dfrac{n}{d}\right\rfloor s(\left\lfloor\dfrac{m}{d}\right\rfloor)\mu(d)[d\perp k]$$ 记 $$\begin{aligned}f(i)&= \sum_{j=1}^i\mu(j)[j\perp k]\\&=\sum_{j=1}^i[j\perp k]f(\left\lfloor\dfrac{i}{j}\right\rfloor)-\sum_{j=2}^i[j\perp k]f(\left\lfloor\dfrac{i}{j}\right\rfloor)\end{aligned}$$ 然后有 $$\begin{aligned}\sum_{i=1}^n[i\perp k]f(\left\lfloor\dfrac{n}{i}\right\rfloor)&=\sum_{i=1}^n[i\perp k]\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\mu(j)[j\perp k]\\&=\sum_{i=1}^n\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\mu(j)[ij\perp k]\\&=\sum_{T=1}^n[T\perp k]\sum_{d\mid T}\mu(d)\\&=\sum_{T=1}^n[T\perp k][T = 1]\\&=1\end{aligned}$$ 所以 $$f(i) = 1 - \sum_{j=2}^i[j\perp k]f(\left\lfloor\dfrac{i}{j}\right\rfloor)$$ 可以杜教筛了。over。 [代码。](https://www.luogu.com.cn/paste/7zlvjspc) --- ### [P1516 青蛙的约会](https://www.luogu.com.cn/problem/P1516) 记总次数为 $k$，那么有： $$x + km \equiv y + kn\quad (mod \;\;l)$$ 之后一通乱搞： $$x+km - y+kn = lz$$ $$(x-y)+k(m-n)=lz$$ $$k(m-n)-lz=-(x-y)$$ $$\text{令}\;A = n - m,\; B = x - y$$ $$\therefore Ak + lz = B$$ 扩欧即可。 [代码。](https://www.luogu.com.cn/paste/g394hk6d) --- ### [P2480 [SDOI2010]古代猪文](https://www.luogu.com.cn/problem/P2480) 先翻译一下题意，求： $$g^{\sum_{d\mid n}\binom{n}{d}} \mod 999911659$$ 首先运用费马小定理，即求： $$\sum_{d\mid n}\binom{n}{d} \mod 999911658$$ 考虑到 $99911658 = 2×3×4679×35617$，那么只需要求出： $$\sum_{d\mid n}\binom{n}{d} \mod 2$$ $$\sum_{d\mid n}\binom{n}{d} \mod 3$$ $$\sum_{d\mid n}\binom{n}{d} \mod 4679$$ $$\sum_{d\mid n}\binom{n}{d} \mod 35617$$ 最后用中国剩余定理合并即可。 [代码。](https://www.luogu.com.cn/paste/8t3sshgz) --- ### [P3868 [TJOI2009]猜数字](https://www.luogu.com.cn/problem/P3868) $b_i \mid (n - a_i)$ 等价于 $n \equiv a_i(\bmod\ b_i)$。 中国剩余定理板子题。 [代码。](https://www.luogu.com.cn/paste/23z1z11w) --- ### [P5345 【XR-1】快乐肥宅](https://www.luogu.com.cn/problem/P5345) 不会，咕。 --- ### [P3306 [SDOI2013] 随机数生成器](https://www.luogu.com.cn/problem/P3306) 以下 $=$ 默认为 $\equiv$。 根据我们小学就学过的等比数列求和公式，构造等比数列： ~~开个玩笑，是必修5数列的内容（~~ $$x_{i+1}+\dfrac{b}{a-1}=a(x_i + \dfrac{b}{a-1})$$ $$\therefore x_n +\dfrac{b}{a-1}=a^{n-1}(x_1 + \dfrac{b}{a-1})$$ $$a^{n-1} = \dfrac{x_n + \dfrac{b}{a-1}}{x_1 + \dfrac{b}{a-1}}$$ 然后直接 BSGS 即可。注意 $a=0$ 或 $1$ 时的特判。 [代码。](https://www.luogu.com.cn/paste/21xxtog9) --- ### [P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485) 直接分析每一问： $1.$ 直接快速幂即可。 $2.$ 转化为 $x\equiv\dfrac{z}{y}(\bmod\ p)$，费马小定理+快速幂即可。 $3.$ BSGS 模板题。 [代码。](https://www.luogu.com.cn/paste/qk9v6xjm) --- ### [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139) 首先，有扩展欧拉定理： $$\forall b \ge \varphi(p), a^b \equiv a^{b \bmod \varphi(p)+\varphi(p)}(\bmod\ p)$$ 于是，原式即可化为： $$2^{2^{2^{...}}}\equiv 2^{2^{2^{...}}\bmod \varphi(p)+\varphi(p)}(\bmod\ p)$$ 然后递归处理即可，边界条件是 $p=1$，此时值为 $0$。 [代码。](https://www.luogu.com.cn/paste/smqb76mr) --- ### [P3200 [HNOI2009]有趣的数列](https://www.luogu.com.cn/problem/P3200) 不会，咕。 --- ### [P4091 [HEOI2016/TJOI2016]求和](https://www.luogu.com.cn/problem/P4091) 先去度娘那里嫖一个 $S(i, j)$ 的通项公式： $$S(i, j) = \dfrac{1}{j!}\sum_{k=0}^j (-1)^{j-k}\binom{j}{k}k^i$$ 代回原式，并注意到 $S(i, j) = 0(i < j)$： $$\begin{aligned}f(n)&=\sum_{i=0}^n\sum_{j=0}^n 2^j\times j!\times \dfrac{1}{j!}\sum_{k=0}^{j}(-1)^{j-k}\binom{j}{k}k^i\\&=\sum_{i=0}^n\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^{j-k}\dfrac{j!}{k!(j-k)!}k^i\\&=\sum_{j=0}^n2^j\times j!\sum_{k=0}^j(-1)^{j-k}\dfrac{1}{k!(j-k)!}\sum_{i=0}^nk^i\end{aligned}$$ 最后那个等比数列求和即可，不妨记为 $x_k$。记 $y_k = \dfrac{(-1)^k}{k!}$，$z_k = \dfrac{x_k}{k!}$ $$f(n)=\sum_{j=0}^n2^j\times j!\sum_{k=0}^jz_ky_{j-k}$$ 发现最后那个东西是个卷积，可以 NTT 求出，不妨记为 $w_j$。 $$f(n)=\sum_{j=0}^n2^j\times j!\times w_j$$ 搞定。 [代码。](https://www.luogu.com.cn/paste/1fvt9usd)