数学
主要是计数和数论函数相关。
[AGC031F] Walk on Graph
题意：有一张 \(n\) 个点 \(m\) 条边的无向连通图 \(G\)，每条边有长度 \(L_i\)，有一个人在上面游走。
有 \(q\) 组询问，每组询问给出 \(s_i,t_i,r_i\)，询问是否存在一条从 \(s_i\) 出发到 \(t_i\) 结束且长度为 \(r_i\) 的路径。其中路径长度的定义为：假设走过了的边长度为 \(L_1,L_2,\cdots, L_k\)，则这条路径的长度为 \((\sum_{i=1}^kL_i\times 2^{i-1}) \bmod MOD\)。
思路：首先，因为正着走不好处理，考虑倒着走，每走一条边，权值变为\(2w+w_i\)，于是设计二元状态\((x,w)\)表示走到\(x\)时权值是\(w\)，那么目标就是从\((x,0)\)走到\((y,t)\)。
接着可以发现一些性质。
如果从\((x,i)\)可以到\((y,j)\)，那么从\((y,j)\)也可以到\((x,i)\)。假设有一条从\(u\)到\(v\)的路径长度为\(l\)，权值为\(w\)，那么走完就是\((y,i\times 2^l+w)\)，如果走\(t\)次，权值就是\(i\times 2^{tl}+w2^l(2^t-1)\)，于是走\(t=2\varphi(p)\)次就可以走回\((u,x)\)。
接着，假设有两条边的边权是\(a,b\)，那么\((u,x)\Leftrightarrow (u,x+3(a-b))\)。证明可以考虑如果这两条边与一个点相连，那么\((u,x)\Leftrightarrow(u,4x+3a),(u,x)\Leftrightarrow(u,4x+3b)\)，又因为4有逆元，于是\((u,x)\Leftrightarrow(u,x+3(a-b))\)，其他情况可以类推。
根据裴蜀定理，设\(g'=\gcd\limits_{x,y\in E}(x-y),g=gcd(g',p)\)，就有\(x\equiv y\pmod{3g}\)时有\((u,x)\Leftrightarrow(u,y)\)，反推有\(x\equiv\pmod{\gcd(3g,p)}\)时有\((u,x)\Leftrightarrow(u,y)\)，而\(g'=\gcd\limits_{i=2}^m(w_i-w_1)\)。
于是每条边可以表示为\(gx+z\)的形式，这时可以把所有边减去\(z\)，把第二维都加上\(z\)，这样所有边权是\(g\)的倍数，所以\((u,x)\Leftrightarrow(v,x2^p+gq),q\in\{0,1,2\}\)。又因为\((u,x)\Leftrightarrow(u,4x+3w)\Leftrightarrow(u,4x)\)，这样\(p\in\{0,1\}\)。于是所有状态只有6种。这样就很好做了。
P3747 [六省联考 2017] 相逢是问候
题意：把区间中的数 \(a_i\) 变成 \(c^{a_i}\) 和求区间和。
思路：属于是比较板但有点难的线段树维护一些改变量为 \(O(\log n)\) 的数学题。
根据拓展欧拉定理，\(a^c\equiv \begin{cases} a^c& c\le \varphi(m)\\a^{(c\bmod\varphi(m))+\varphi(m)}&c>\varphi(m) \end{cases}\)
而 \(\varphi\) 最多嵌套 \(O(\log)\) 层，于是可以直接线段树暴力维护，如果区间内所有修改次数都超过了层数就不修改。用光速幂就是 \(O(n\log^2)\)。
[ARC089F] ColoringBalls
题意：有 \(N\) 个白色的小球排成一排，有一个长为 \(K\) 的字符串 \(S\)。接下来进行 \(K\) 次操作。
第 \(i\) 个操作，选择一段连续的小球（可以为空），若 \(S\) 中第 \(i\) 个字符是 r，则将这些球染成红色；若是 b，则将它们染成蓝色。由于染料的特性，不能直接用蓝色来染白色。
求在进行完所有操作后，所有小球的颜色序列可以有多少种。
思路：arc就连数学题思维量都这么大。
大致是官方题解的思路。
首先，把计数转成判定一种最终结果是否合法。我们想办法把最终状态划分等价类来减少枚举结果的量。
接着，可以不管\(W\)，把剩下的连续段拿出来，然后把同色连续段缩成一个，这样就形如
\[[RBRBR],[R],[RB],[RBR] \]接着我们有一个惊人的发现，设\(c_i\)为第\(i\)个连续段中\(B\)的个数，有：
1.\(c_i=0\)，\(r\)。
2.\(c_i=1\)，\(rb\)。
3.\(c_i\geqslant 2\)，需要\(c_i+1\)次，而前两次操作一定是\(rb\)，后面无论怎么操作都可以达到。
这样就可以很简单地判定了。具体地，我们把缩完的连续段按\(c_i\)从大到小排序，然后分配操作序列，设连续段数为\(m\)，先分\(m\)个\(r\)给每一段，再给\(c_i>0\)的分配之前的\(r\)后面的\(b\)，最后给\(c_i>1\)的分配之前的\(b\)后\(c_i\)个没用过的就行了。
我们还可以发现，连续段之间的顺序是不重要的，因此不同的状态只有\(O(\text{划分数})\)个，可以直接暴力枚举。
最后就是对每种合法的序列计算贡献。记\(len(x)=[x=0]+[x\geqslant1](2x-1)\)表示有\(x\)个\(B\)的连续段至少有多长，因此总共占了\(A=m-1+\sum f(x)\)个位置。考虑剩下的\(n-A\)个怎么插入空隙。可以把每个BR当做是自己所在的连续段最后一个，这样有\(x\)个\(B\)的连续段就有\(2x+1\)个空隙，两边也有空隙，于是共有\(B=m+1+\sum(2c+1)\)个空隙，因此方案数为\(\binom{n-A+B-1}{B-1}\)。
Make Square
题意：我们称一个数列\(b\)是“优秀的”，当且仅当存在 \(b_i\times b_j(i<j)\)是一个完全平方数。
给定一个数列\(a\)，每次询问使\(a_l,a_{l+1},\cdots,a_{r-1},a_r\)这个数列成为一个“优秀的”数列至少要进行几次操作，共\(q\)次询问。
每一次操作，你可以将数列中的任意一个数乘以/除以一个质数\(p\)
思路：首先，容易想到把每个数的质因子成对去掉，这样每个数最多包含7个质因子和128个因数。设 \(f_x\) 表示 \(x\) 的质因子数，这样两个数的答案就是 \(f_x+f_y-2f_{\gcd(x,y)}\)。于是可以想到枚举 \(d=\gcd(x,y)\) 来算贡献，这样就需要求出 \(d|x\) 中 \(f_x\) 的最小、次小值。如果只有一次询问，可以暴力统计最小、次小值，但是有多次询问，就只能求出所有可以对答案做贡献的点对然后离线扫描线。
具体地，我们枚举次小值所在位置，用单调栈求出前、后第一个小于它的位置作为最小值，然后用这个区间作为可以产生贡献的点对。考虑扫描线的过程，相当于是单点改和查后缀min，可以改成前缀取min和单点查，又因为 \(f_x+f_y\) 最大只有 14，均摊下来次数不超过 \(14n\)。
P6276 [USACO20OPEN] Exercise P
题意：计算出所有长为 \(n\) 的排列的置换环大小的 \(lcm\) 的积。
思路：首先，每个排列的贡献是置换环长的 lcm。先转成计数，求 \(x=lcm\) 的排列个数。
发现 \(x\) 可能很大，不方便计算，然后转成求前缀和，即 \(x|lcm\) 的排列个数。
这样就只用对每个质数的幂次进行考虑，设 \(F(p^c)\) 表示 \(p^c|lcm\) 的排列个数，那么答案就是 \(\prod\limits_{p,c}p^{F(p^c)}\)。
现在考虑怎么求 F。因为至少有一个不好求，我们可以转成求补集，即不存在长度为 \(x\) 的置换环排列数 \(f(x)\)，我们再设 \(g(x)\) 表示所有置换环长度都是 \(x\) 的倍数的排列个数，那么有：
\[f_i=i!-\sum\limits_{j<i}\binom{i}{j}f_jg_{i-j} \]\[g_i=\sum\limits_{j<i}\binom{i-1}{i-j-1}(i-j-1)!g_j \]而对于每个 \(x\)，\(f,g\) 只有 \(\dfrac{n}{x}\) 个是有用的，因此复杂度为 \(O(n^2)\)。
[AGC045F] Division into Multiples
题意：给定 \(A,X,B,Y,C\) 有 \(X\) 个球上面数字是 \(A\)，\(Y\) 个球上面数字是 \(B\)，一个组是好的当且仅当组不为空且内部的球的和是 \(C\) 的倍数，求最多有几个好的组。
思路：首先可以让 \(A,B,C\) 互质，先让 \(\gcd(A,B)=1\)，再让 \(\gcd(A,C)=1\)，即如果 \(Ax+By\equiv0\pmod C\)，那么记 \(d=\gcd(A,C)\)，那么 \(A\leftarrow \dfrac{A}{d},C\leftarrow\dfrac{C}{d},Y\leftarrow\left\lfloor\dfrac{Y}{d}\right\rfloor\)，\(B,C\) 同理。
记 \((i,j)\) 表示 \(i\) 个 A 球和 \(j\) 个 B 球，那么有 \(Ai+Bj\equiv0\pmod C\)，即 \(j\equiv-\dfrac{A}{B}i\pmod C\)，于是记 \(D\equiv\dfrac{A}{B}\pmod C\)，那么就是 \((0,C),(1,(-D)\pmod C),\dots,(i,(-iD)\pmod C)\)。
发现如果存在两组 \((x,y),(x_1,y_1)\) 满足 \(x\le x_1,y\le y_1\)，那么 \((x_1,y_1)\) 就没用了。于是我们就需要找 \(C,(-D)\pmod C,(-iD)\pmod C\) 的前缀最小值。
如果 \(C\ge D\)，设 \(t=\left\lfloor\dfrac{C}{D}\right\rfloor\)，于是当前前缀最小值就是 \(C,C-D,\cdots C-tD\)。设 \(C'=C\pmod D\)，那么如果当前是 \(x\)，下一个就是 \((x-D)\pmod{C'}\)，设 \(D'=D\pmod{C'}\)，于是就是 \(C',(-D')\pmod{C'},\cdots,(-iD')\pmod{C'}\)，发现这就相当于是欧几里得算法的过程，而且会形成 \(O(\log n)\) 个等差序列。
同样，因为公差是递减的，因此一定在同一段里才最优，于是在每一段里可以二分来找最优答案。
复杂度 \(O(T\log^2V)\)。
The Films
题意：给定 \(n,m,q\)，给定长为 \(n\) 的序列 \(\{a\}\)，满足 \(a_i\in [1,m]\)。
多组查询，每次给出区间 \([l_i,r_i]\) 与 \(k\)，表示如下操作：
- 令集合 \(S\) 为序列 \(a\) 构成的可重集。
- 对于每种颜色 \(c\in [1,m]\)，加入 \(k\) 个此颜色的元素。
- 从中随机选出 \(n\) 个元素，然后随机排成一个排列。
- 计算最后区间 \([l_i,r_i]\) 与初始序列相等的方案数。
思路：莫队+数学题。
假设 \(k\) 给定，设 \(s_i\) 为 \(i\) 在整个序列的出现次数，\(c_i\) 为 \(i\) 在区间 \([l,r]\) 的出现次数，那么有 \(ans=\prod\limits_{i=1}^m(s_i+k)^{\underline{c_i}}\times (mk+n-(r-l+1))^{\underline{n-(r-l+1)}}\)，直接用莫队维护即可。
可是现在有 \(t\) 种不同的 \(k\)，可以直接对于每一种 \(k\) 都跑一遍，根据卡尔松不等式可以知道复杂度是 \(O(n\sqrt{tq})\) 的。
Move by Prime
题意：给你一个长度为 \(n\) 的数列 \(a_i\)，你可以进行任意次操作：将其中一个数乘上或者除以一个质数。使得最终所有数相同，并使得操作数尽可能小。现在我们想要知道 \(a_i\) 的所有子序列的操作数之和是多少。
思路：不算太难的计数题。
首先，每个质数的贡献是独立的，可以分开计算。对于一个质数 \(p\)，假设每个数的指数是 \(x_i\)，那么答案就是 \(\sum|x-x_i|\)，其中 \(x\) 为 \(x_i\) 的中位数。
如果我们把 \(x_i\) 排序，那么如果小于 \(i\) 的选了 \(a\) 个，大于的选了 \(b\) 个，就有 \(a<b\) 时贡献为 \(-x_i\)，\(a=b\) 时贡献为 0，\(a>b\) 时贡献为 \(x_i\)，即贡献为 \(x_i(\sum\limits_{j=i}^{n-1}\binom{n-1}{j}-\sum\limits_{j=0}^{i-2}\binom{n-1}{j})\)。
我们预处理出 \(f(i)=\sum\limits_{j=i}^{n-1}\binom{n-1}{j}-\sum\limits_{j=0}^{i-2}\binom{n-1}{j}\)，然后枚举 \(p,x\) 可以 \(O(1)\) 计算，于是可以做到 \(O(V\log\log V)\)。
CGCDSSQ
题意：维护一个序列 \(a\)，长度为 \(n\)，有 \(m\) 次操作：
1. 1 l r：对于 \(l\le i\le r\)，将 \(a_i\) 加上 \(f_{i-l+1}\)。
2. 2 l r：求 \(\displaystyle\left(\sum_{i=l}^ra_i\right)\bmod(10^9+9)\)。
思路：
首先有规律：\(f_i=f_{i-1}f_2+f_{i-2}f_1\)。
因为有加操作，考虑用线段树维护。
于是对于一个区间，可以把每个数 \(a_i\) 写成 \(f_{i-1}a_2+f_{i-2}a_1\)，然后发现和就是 \(f_na_1+(f_{n+1}-1)a_2\)，因此只用维护 \(a_1,a_2\) 即可。
Please, another Queries on Array?
题意：区间乘，区间乘积的 \(\varphi\)，每个数不超过 300。
思路：用 \(long long\) 状压。
300 以内的质数只有 62 个，而 \(varphi\) 又只和区间乘积以及有哪些质因子有关，于是可以考虑用状压来维护，外层用线段树即可。
Instant Noodles
题意：给出一张点数为 \(2N\) 的二分图，其中右侧的第 \(i\) 个点有点权为 \(c_i\)。
- 令 \(S\) 表示左侧点的一个非空点集，设 \(f(S)\) 表示右侧点中至少与 \(S\) 中一个点相连的点的点权和。
- 请你求出，对于所有非空集合 \(S\)，\(f(S)\) 的 \(\gcd\) 为多少。
思路：很厉害的题目。
对于一侧的两个点 \(i,j\)，设邻居集合为 \(S_i,S_j\)，分 3 种情况讨论：
- \(S_i\cap S_j=\varnothing\)，那么贡献就是 \(\gcd(c_i,c_j)\)。
- \(S_i=S_j\)，那么对于左边的任意一个点集，\(i,j\) 一定同时在或者不在这个 \(f(S)\) 里，因此可以将 \(c_i,c_j\) 合并。
- \(S_i\cap S_j\ne\varnothing\)，那么求的结果也是 \(\gcd(c_i,c_j)\)。
Modular Stability
题意：求有多少个长度为 \(k\) 的序列 \(a\)，满足以下条件：
- \(\forall 1 \le i < k,a_i < a_{i+1}\)
- \(\forall 1 \le i \le k,1 \le a_i \le n\)
- 对于任意一个 \(1\) 至 \(k\) 的排列 \(p\)，满足 \(( (((x \bmod a_1)\bmod a_2)\bmod a_3)\bmod \cdots \bmod a_k) = ((((x \bmod a_{p_1})\bmod a_{p_2})\bmod a_{p_3})\bmod \cdots \bmod a_{p_k})\)。其中 \(x\) 为任意非负整数。
思路：假设只有两个数 \(a,b(a<b)\)，且要满足 \((x\bmod a)\bmod b=(x\bmod b)\bmod a\)，因为 \(x\bmod a\) 一定小于 \(a\)，于是 \((x\bmod a)\bmod b=x\bmod a\)，于是有 \(x\bmod b\equiv x\pmod a\)，那么就说明 \(b\) 是 \(a\) 的倍数。
拓展到更多的数，就意味着所有数都是最小的数的倍数，就可以直接计数了。
Wish I Knew How to Sort
题意：给定一个长度为 \(n\) 的 01 序列 \(a\) 和一种操作，你需要用这种操作将序列从小到大排序。
操作如下：
- 等概率随机选取两个位置 \(i,j\ (i<j)\)，若 \(a_i>a_j\)，则交换 \(a_i,a_j\)。
注意：当 \(a_i\le a_j\) 时，交换失败，也算作一次操作。
请你求出操作被执行的 期望次数。
思路：最终一定是一段前缀上是 0，对应后缀是 1，那么如果当前前缀中有 \(x\) 个 1，有效的交换方法有 \(x^2\) 种，于是期望次数为 \(\dfrac{\binom{n}{2}}{x^2}\)，于是最终答案就是 \(\sum\limits_{i=1}^{cnt_0}\dfrac{\binom{n}{2}}{i^2}\)。
P1306 斐波那契公约数
题意：求斐波那契数列第 \(n\) 项和第 \(m\) 项的公约数。
思路：结论：\(\gcd(f_n,f_m)=f_{\gcd(n,m)}\)
引理 1：\(\gcd(f_{n+1},f_n)=1\)
证明 1：\(\gcd(f_{n+1},f_n)=\gcd(f_n+f_{n-1},f_n)=\gcd(f_{n-1},f_n)=\cdots=\gcd(f_1,f_2)=1\)。
引理 2：\(f_{n+m}=f_{m-1}f_n+f_mf_{n+1}\)
证明 2：\(f_{n+m}=f_{n+m-2}+f_{n+m-1}=f_{n+m-3}+2f_{n+m-2}=2f_{n+m-4}+3f_{n+m-3}=\cdots=f_{m-1}f_n+f_mf_{n+1}\)
引理 3：\(\gcd(f_{n+m},f_n)=\gcd(f_n,f_m)\)
证明 3：
\[\begin{aligned} \gcd(f_{n+m},f_n)&=\gcd(f_{n+1}f_m+f_nf_{m-1},f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}\]这个式子就和辗转相除是一样的，于是就可以证明出 \(\gcd(f_n,f_m)=f_{\gcd(n,m)}\)。
P1999 高维正方体
题意：求出在 \(a\) 为空间的元素中，包含着多少个 \(b\) 维空间的元素。
思路：神仙题。
首先看每个 \(i\) 维立方体有多少个点，可以发现是 \(2^i\)。
设 \(f[i][j]\) 表示 \(i\) 维立方体 \(j\) 维元素数。从 \(i=3\) 开始找规律，每个点连 3 条边，每条边有两个点，于是 \(f[3][1]=\dfrac{3f[3][0]}{2}\)；每条边连两个面，每个面有 4 个边，于是 \(f[3][2]=\dfrac{2f[3][1]}{4}\)，同理有 \(f[3][3]=\dfrac{f[3][2]}{6}\)。
可以发现有 \(f[i][j]=\dfrac{(i+1-j)f[i][j-1]}{2j}\)，而我们又可以很快算出 \(f[i][0]\)，于是就可以 \(O(m)\) 算出 \(f[n][m]\)。
P4550 收集邮票
题意：有 \(n\) 种邮票，第 \(i\) 次购买要 \(i\) 元，求买到所有邮票的期望钱数。
思路：考虑如果当前已经有了 \(i\) 种邮票，那么买到新邮票的期望次数是 \(\dfrac{n}{n-i}\)，而平均价格是买前 \(i\) 种邮票的期望次数之和，于是就可以直接计算。
P7322 「PMOI-4」排列变换
题意：就是给定一个长度为 \(k\) 的滑动窗口在长度为 \(n\) 的排列上滑，问滑动窗口中的 \(max\) 变化了多少次。
思路：发现答案增加可能是最左边的数是最小值，可能是新加进来的数是最小值。
考虑第一种情况，贡献是 \(\sum\limits_{i=1}^n\binom{n-i}{k-1}(k-1)!(n-k)!(n-k)\)，\(i\) 枚举的是最小值，组合数和第一个阶乘是窗口中的情况，第二个阶乘是外面的情况。
考虑第二种情况，贡献是 \(\sum\limits_{i=1}^n\binom{n-i}{k}(k!)(n-k-1)!(n-k)\)。
不过还要容斥掉两种都有的情况，这一部分是 \(\sum\limits_{i=1}^n\binom{n-i}{k-1}(k-1)!(n-k-1)!(n-k)(i-1)\)。
这样就做完了。
[AGC019F] Yes or No
题意：有 \(N+M\) 个问题，其中有 \(N\) 个问题的答案是 YES，\(M\) 个问题的答案是 NO。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。
思路：可以做一个很神仙的转化，就是可以当成在一个网格上，从 \((n,m)\) 走到 \((0,0)\)，向左相当于答案是 Yes，向下是 No。
最优策略是还剩的 Yes 多就回答 Yes，如果 NO 多就是 No，否则随便问。
可以发现，我们的策略相当于是往靠近 \(y=x\) 这条线走。
怎么显然可以答对 \(\max(n,m)\) 个，还剩下的就是在线上时能蒙对多少个，那么求出经过这个点的总路径数，乘上 \(\dfrac{1}{2}\) 即可。
[AGC003D] Anticube
题意：给定 \(n\) 个数 \(s_i\)，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。
思路：首先，我们可以想到划分等价类，每一个等价类唯一对应一个和它乘起来是完全立方数的等价类。
划分方式也很简单，把质因数分解后的幂次对 3 取模即可。
然后就是这一题最大的难点：每个数的范围是 \(10^{10}\)，直接质因数分解肯定不行，用 PR 又有点大材小用。
我们发现，大于 \(\sqrt[3]{V}\) 的质数最多只有两个，而且我们也仅仅只需要知道能与他们组成完全立方数的数是多少，于是可以只把不超过 \(\sqrt[3]{V}\) 的质因数筛出来，然后判断剩下的是否是完全平方数即可。
Side Transmutations
题意：给你一个包含 \(m\) 个整数的序列 \(b\) (\(b_1<b_2<\dots<b_m\))。你可以对字符串 \(S\) 作以下的操作：
1.选择一个合法的 \(i\) ,并且令 \(k=b_i\) ;
2.取出 \(S\) 中前 \(k\) 个字符 \(Pr_k\) ;
3.取出 \(S\) 中后 \(k\) 个字符\(Su_k\) ;
4.将 \(S\) 中前 \(k\) 个字符替换成翻转后的 \(Su_k\) ;
5.将 \(S\) 中后 \(k\) 个字符替换成翻转后的 \(Pr_k\) ;
举个例子，我们令 \(S=\) "abcdefghi"，\(k=2\) 。这时\(Pr_2=\) "ab"，\(Su_2=\) "hi"，翻转后有 \(Pr_2=\) "ba"，\(Su_2=\) "ih"，那么最终得到的字符串 \(S\) 就是 "ihcdefgba"。
这个操作可以被执行许多次（可能是零次），任何一个 \(i\) 也可以被使用多次。
我们将字符串 \(S\) 和 \(T\) 称为相等的字符串，当且仅当存在一个操作序列，将字符串 \(S\) 变成 \(T\)。对于上面的例子来说，"abcdefghi" 和 "ihcdefgba" 是相等的。注意到 \(S\) 和它自己也是相等的。
你的任务很简单，数出互不相同的字符串的个数。
思路：其实并不难。
我们可以通过 \(b\) 被字符串划分成若干段，对于任意一段，我们可以且仅可以把这一段关于中点翻转。
考虑每一段，左边有 \(|A|^{len}\) 种情况，如果右边和左边不同，那么就会被算两次，贡献是 \(\dfrac{|A|^{len}(|A|^{len}-1)}{2}\)，否则贡献是 \(|A|^{len}\)。你可以对字符串
考虑中间的一段，因为无法操作，于是方案数是 \(|A|^{n-2b_m}\)。
将每一段的贡献累加即可。
Wrong Answer on test 233 (Hard Version)
题意：给定 \(n\)，\(k\) 和值域 \([1,k]\) 的 \(n\) 个整数 \(h_i\)，求有多少个长为 \(n\) 的整数序列 \(a\) 满足值域 \([1,k]\)，且 \(\sum\limits_{i=1}^n[a_i=h_i]<\sum\limits_{i=1}^n[a_i=h_{(i\bmod{n})+1}]\)。
思路：设 \(f[i]\) 表示差值为 \(i\) 的方案数，容易发现 \(f[i]=f[-i]\)，那么我们要求的就是总共的方案数减去两式相等的方案数。
假设有 \(m\) 个位置可以产生不同，那么枚举值，答案就是 \(\sum\limits_{i=0}^{\left\lfloor\frac{m}{2}\right\rfloor}k^{n-m}C_m^iC_{m-i}^i(k-2)^{m-2i}\)。
最终用 \(k^n\) 减去答案即可。
P1943 LocalMaxima
题意：给出一个排列，求前缀最大值的期望个数。
思路：答案为 \(\sum\dfrac{1}{i}\)。
证明：如果 \(i\) 要成为前缀最大值，那么比 \(i\) 大的要在 \(i\) 后面，其他的随便放，如果比 \(i\) 小的数有 \(p\) 种放法，概率就是 \(p(n-i)!/p(n-i+1)!\)，即 \(\dfrac{1}{n-i+1}\)。
P3643 [APIO2016] 划艇
题意：给出序列 \(a,b\)，求有多少序列 \(c\)，满足 \(c_i=-1\) 或者 \(c_i\in[a_i,b_i]\)，且非 -1 的部分单增。
思路：先考虑所有 \(a_i,b_i\) 分别相等的情况，可以设 \(f[i][j]\) 表示考虑前 \(i\) 个数，最大值为 \(j\) 的方案数，然后发现 \(f[i][j]\) 是 \(i\) 次多项式，那么就可以用拉格朗日插值。
考虑一般的情况，发现每个区间都是 \(n\) 次多项式，于是可以分别用拉格朗日插值来求。复杂度 \(O(n^3)\)。
P3239 [HNOI2015] 亚瑟王
题意：给 \(n\) 个技能，每个技能有权值，有 \(r\) 轮，开始时 \(j=1\)，每张牌有 \(p_j\) 的概率被选择，如果选择就进入下一轮，否则就令 \(j+1\)。一个技能只能用一次，求技能的权值和的期望。
思路：根据期望的线性性，可以把每个技能的期望加起来，那么可以转成求每个技能被使用的概率 \(a[i]\)。
对于第一个，不出的概率是 \((1-p[1])^r\)，即每次到第一个技能都不选的概率。
对于其他牌，因为如果选择了就会直接跳过，我们并不好直接处理。考虑设 \(f[i][j]\) 表示前 \(i\) 个技能中选了 \(j\) 个的概率。那么对于第 \(j\) 个技能，如果前 \(i-1\) 轮选了 \(j\) 张个技能，那么有 \(j\) 轮不会考虑第 \(i\) 个技能，有 \(r-j\) 轮会考虑，于是有 \(a[i]=\sum f[i-1][j](1-(1-p[i])^{r-j})\)。
现在考虑怎么求 \(f[i][j]\)。
如果最终没有选第 \(i\) 张，那么有 \(f[i][j]=f[i-1][j](1-p[i])^{r-j}\)。
如果选择了，就有 \(f[i][j]=f[i-1][j-1](1-(1-p[i])^{r-j+1})\)。
复杂度 \(O(Tnr)\)。
P3251 [JLOI2012] 时间流逝
题意：给定 \(n\) 种价值不同的元素，你需要维护一个可重集（开始是空集）。每一步你有 \(p\) 的概率删除集合中一个价值最小的元素，如果当前是空集则这种情况概率为
0；否则你将等概率的获得一个元素，满足这个元素的价值不大于任何一个已经获得的元素的价值。求达到（或超过）给定的一个阈值 T 所需的期望步数。
思路：设 \(f(S)\) 表示当前集合为 \(S\)，要到达阈值的期望步数，那么记 \(P\) 为 \(S\)\ \(\min{S}\)，后继为 \(suf(S)\)，那么转移就是 \(f(S)=1+pf(P)+\dfrac{1-p}{|suf(S)|}\sum\limits_{T\in suf(S)}f(T)\)。
我们发现这个形式就是树上高斯消元的形式，可以套路的把 \(f(S)\) 写成 \(kf(P)+b\)，这样一遍 DFS 就可以解决。
对于所有集合，我们发现我们只关心和以及最小值，那么可以在 dfs 时只维护这两个值，然后暴力搜索即可。
P3292 [SCOI2016] 幸运数字
题意：在多次询问，每次在树上选择一条路径，求这条路径上的点的异或最大值。
思路：考虑类似时间戳线性基，求出每个点到根的线性基，并且保留离 \(x\) 最近的数。
询问时先找出两个点可以用的数，然后把两个线性基合并，就可以求答案了。
P3830 [SHOI2012] 随机树
题意：给出二叉树的生成方式：每次选择一个点然后加上左右儿子，直到有 \(n\) 个叶节点，问叶节点的平均深度的期望和树深度的期望。
思路：对于第一问，设 \(f[x]\) 表示有 \(x\) 个叶子结点的平均深度，那么有 \(f[x]=\dfrac{f[x-1](x-1)+f[x-1]+2}{x}=f[x-1]+\dfrac{2}{x}\)。
对于第二问，设 \(f[i][j]\) 表示有 \(i\) 个叶子的树中，树的深度大于等于 \(j\) 的概率，那么有 \(f[i][j]=\sum\limits_{k=1}^{i}\dfrac{f[k][j-1]+f[i-k][j-1]-f[k][j-1]f[i-k][j-1]}{i-1}\)。
怎么证明是除 \(i-1\) 呢？
设 \(p_k\) 表示左儿子有 \(k\) 个叶子，右儿子有 \(i-k\) 个叶子的树，深度不小于 \(j\) 的概率为 \(p_k=f[k][j-1]+f[i-k][j-1]-f[k][j-1]f[i-k][j-1]\)，假设操作 \(i-1\) 次，这样的树的概率是 \(p_k'\)，那么总的概率就是 \(\sum\limits_{k=1}^{i-1}p_kp_k'\)，那么我们就要证明 \(p_1'=p_2'\cdots p_{i-1}'=\dfrac{1}{i-1}\)。
我们考虑把操作写序列，L 表示在左子树加，R 表示在右子树，那么总共就会有 \(k\) 个 L，\(i-k\) 个 R，除掉根节点的 L,R，一共有 \(C^{k-1}_{i-k+1+k-1}=\dfrac{(i-2)!}{(k-1)!(i-k-1)!}\) 种。考虑生成 \(k\) 个叶子的树的方案数，就是 \((k-1)!\)，因此左边有 \((k-1)!\)，右边有 \((i-k-1)!\) 种，一共就是 \((k-1)!(i-k-1)!\) 种，乘起来发现答案就是 \((i-2)!\)，与两边的叶子数无关。于是就可以直接除以 \(i-1\)。
P4804 [CCC2016] 生命中的圆
题意：有一个圆环，每个位置是 0/1，每个时刻，每个位置会变成两边的异或和，求 T 轮后的状态。
思路：因为 T 很大，而且显然不能矩阵快速幂，于是考虑找结论。
我们假设进行 \(2^k\) 轮，那么就有 \(f[i][j]=f[i-2^k][j-2^k]\oplus f[i+2^k][j+2^k]\)。
证明可以采用数学归纳法。
\(k=0\) 时显然成立。
当 \(k>0\) 时，有 \(f[i][j]=f[i-2^{k-1}][j-2^{k-1}]\oplus f[i-2^{k-1}][j+2^{k-1}]=(f[i-2^k][j-2^k]\oplus f[i-2^k][j])\oplus(f[i-2^k][j]\oplus f[i-2^k][j+2^k])\)，于是得证。
因此直接把 T 二进制分解即可。复杂度 \(O(n\log T)\)。
P4681 [THUSC2015] 平方运算
题意：给一个序列，要求支持区间平方和查区间和，给定可能用的质数。
思路：因为给了会用的质数，考虑能否从这方面入手。我们知道，在模意义下平方是有循环节的，而且可以发现，对于给定的质数，循环节长度不超过 60，于是可以直接上线段树，如果没有进入循环节就暴力修改，否则就打标记。
复杂度 \(O(wn\log n)\)。
P6620 [省选联考 2020 A 卷] 组合数问题
题意：给一个 \(m\) 次多项式 \(f(x)\)，求 \(\sum\limits_{k=0}^n(f(k)x^k\binom{n}{k})\)。
思路：因为有幂次和组合数，于是考虑转下降幂。假设转成下降幂多项式之后是 \(\sum b_ix^i\)，于是有：
\[\begin{aligned} \sum\limits_{k=0}^n\sum\limits_{i=0}^mb_kk^{\underline{i}}x^k\binom{n}{k}&=\sum\limits_{i=0}^mb_in^{\underline{i}}\sum\limits_{k=0}^n\binom{n-i}{k-i}x^k\\ &=\sum\limits_{i=0}^mb_in^{\underline{i}}\sum\limits_{k=0}^{n-i}\binom{n-i}{k}x^{k+i}\\ &=\sum\limits_{i=0}^mb_in^{\underline{i}}x_i\sum\limits_{k=0}^{n-i}\binom{n-i}{k}x^k\\ &=\sum\limits_{i=0}^mb_in^{\underline{i}}x_i(x+1)^{n-i}\\ \end{aligned}\]那么现在的问题就是怎么把普通幂转下降幂。
因为有 \(x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\)，于是有 \(\sum\limits_{i=0}^ma_ik^i=\sum\limits_{i=0}^ma_i\sum\limits_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}=\sum\limits_{i=0}^mk^{\underline{i}}\sum\limits_{j=i}^m\begin{Bmatrix}j\\i\end{Bmatrix}a_j\)
求出第二类斯特林数就可以了。
标签：gcd,limits,记录,dfrac,sum,数学题,可以,题意 From： https://www.cnblogs.com/Xttttr/p/18014833