临时抱佛脚
还是一样，模板都有标记
P3197
减法原理。
(m^n - m(m-1)^{n-1})
【记录】
P2822
被 k 整除相当于膜 k = 0， 所以直接做。
P2290【prufer序列】
直接 prufer 序列， 度数为 d 相当于在 prufer 序列中出现 d-1 次， 所以直接可重集排列。
【darkbzoj记录】全是小数据耶
【lg86pts】说好的答案 (le 10^{17}) 呢？
P3807【lucas 定理】
背板子，
【记录】
P7044
题面似曾相识（
考虑某个子串对最终答案的贡献。
设 (p_{l,r,k}) 表示子串 ([l,r]) 的 (k) 级偏值。
那么：
那么对于一个固定的 (l_0,r_0)， 来算一下它对整个答案的贡献。
这个就是 (1,l_{k-1},dots, l_0) 这边和 (r_0,r_1,dots,n) 这边的情况， 是本质一样的问题。
以前者为例，这个其实就是 (x_k+x_{k-1}+cdots+x_1 = l_0-1) 的非负整数解。（这里的每个变量都表示某个 (l_{i+1}-l_i)， 即左边的 l 到右边的 l 的距离，总的来说，说得随便一点就是从 (1) 开始不断加 (Delta) 要正好到达 (l_0)）
那么：
继续考虑 (p_{l,r,0})， 这个就是对区间做一次括号匹配后无法匹配的括号总个数。
然后这个怎么算呢
这个牛逼式子或许可以分治算，但我没深入想， 还是想题解里提出的枚举一个数据维护一堆东西的做法。
这个做法必须要能计算一个括号对于一堆 (p_{l,r,0}) 的贡献。
但是这里说的 “贡献” 太谜语人了， 需要进一步考察。
首先序列括号匹配的基本事实是， 整个序列的所有单个括号， 如果其有匹配的括号， 那么这个括号是一定的， 能否找出这对括号， 只取决于扫描的区间是否覆盖了这对括号。
现在考虑从 (l) 扫到 (r) 做一次括号匹配。
再明确一些事实：
- 如果从 (l) 开始从左往右扫括号匹配， 某个位置 i 的
)可以得到匹配， 那么在固定 (r) 的情况下，从小于 (l) 的位置开始扫也可以得到匹配，。 - 如果扫到 (r) 可以使某个位置 (i) 的
(可以得到匹配， 那么在固定 (l) 的情况下， 扫到大于 (r) 的位置也可以得到匹配
所以先考虑从 1 扫到 n 进行括号匹配， 对于第 i 个位置， 设 p(i) 为与 i 上的括号匹配的括号的位置。
那么考虑 i 上是左括号， 会对哪些区间产生贡献， 依据上面的分析， 是左区间在 ([1,i])， 右区间在 ([i,p(i)-1]) 的所有区间；考虑 i 上是右括号， 则是右区间在 ([i,n])， 左区间在 ([p(i)+1,i]) 的所有区间。
所以如果考虑从 1 到 n 枚举 r，然后维护 (sumlimits_{1le lle r}p_{l,r,0}dbinom{l+k-2}{k-1}) ， 就可以：
如果当前是左括号， 当前维护的区间都要加上 1 的贡献，然后到 p(i) 时取消。
如果是右括号， 则对 (l) 为 ([p(i)+1,i]) 的区间加上贡献，不取消。
【记录】
P2480
显然指数高精都存不下， 考虑欧拉定理。
由于膜数是质数， 所以只要算 (sum_{kmid n}inom nkmod 999911658) 就可以快速幂了。
这个数是个偶数， 将其质因数分解， 得到的结果是 (2 imes 3 imes 4679 imes35617)。
可以直接分别计算然后 CRT 合并。
【记录】看我优美代码！
P4769【折线法】
不考虑字典序的限制， 等价于求最长下降子序列的长度不超过 2 的排列的数量。
考虑 dp， 设 (f_{i,j}) 为从左扫描到了第 i 个， 最大值为 j 且合法的方案数。
考虑接下来放在 i+1 的那个数， 如果大于 j， 那么显然可以， 如果小于 j， 那么就恰好形成了一个长度为 2 的下降子序列， 进而， 再放更小的话， 就不合法了， 所以如果小于 j， 应该放最小的， 但是会不会让原本合法的序列不合法？不会的， 因为这样的话说明在前面的决策点没有遵循小于 j 的放最小的决策原则。
所以，
也可以写成
这等价于只可以向右或向上走，从 ((0,0)) 走到 ((i,j))， 且一直在直线 (y=x) 上方的方案数。
现在加上字典序的限制， 枚举第一次高于限制的位置 i，计算答案。
现在若要计算从 ((i,j)) 到 ((n,n)) 的不计字典序限制的方案数， 可以采用折线法。
具体来说， 第一次走到 (y=x) 下方等价于第一次接触到 (y=x-1) 这条直线， 将路径沿着这条直线翻折， 发现相当于一个从对称后的起始点走到 ((n,n)) 的方案， 直接算这种方案数就等于不合法的方案数。
(x,y) 在与 y = x-1 对称后变为 (y+1,1-x)。
【记录】
P4931
首先选出 k 对情侣让他们乖♂乖♂坐♂好♂， (dbinom nkdbinom nkk! 2^k)。
然后剩下的错排， 设 (f_n) 为 n 对都不匹配的方案数。
考虑第一排座位， 选出一对不是情侣的， 有 (2n imes (2n-2)) 种选法， 然后考虑这一对各自的情侣， 如果坐在一起， 就是 (2 imes (n-1) imes g[n-2])， 反之， 就是相当于这两个是情侣（不能坐在一起）， 就是 (g[n-1])， 所以：
预处理之后在线回答询问就行了。
【记录】
P2532【卡特兰数】
【推理过程】
高精先不写。
P5395【第二类斯特林数 · 行】
第二类斯特林数有一个性质：
组合意义的证明：左边是把 n 个不同的数放在至多 m 个不同的集合的方案数， 右边则是枚举放在了多少个集合里， 然后选出药放的集合， 然后放， 然后标号。
由二项式反演：
卷积即可。
【记录】
P6620【O(n2)普通幂转下降幂】
首先 n 这么大肯定要交换求和号
可以把 (f(k)) 转成下降幂多项式。
如此， 只要 (O(n^2)) 处理下降幂再 (O(n^2log w)) 计算就行了。
转下降幂的方法：
【记录】
P3200
稍加分析即可知道答案是卡特兰数。
exLucas！
分解质因数就行了。
【记录】
CF814E
首先用 bfs 确立最短路树。
由于最短路树是唯一的，所以原图中没有连接在 bfs 树上深度不同的两个点的边。
由于最短路长度随编号递增，所以 bfs 树中同深度的节点的编号必定都是连续的一段。
区间 DP：
设 (f(i,j)) 表示只考虑前 i 个点的情况下， 第 i 个点所在深度有 j 个点， 且更浅的深度的点的度数的限制均被满足， i 的深度的点除了与父亲的连边都暂时不考虑， 方案数是多少。
记 (g(i,j,k)) 表示这一层有 (i) 个点， 上一层有 (j) 个度数为 2 的点， (k) 个度数为 3 的点， 满足上一层的度数限制的方案数。
那么转移就是：
其中， (k2,k3) 分别表示度数为 2 和为 3 的点。
最终答案：
考虑计算 (g)：
(g(0,0,0) = 1)。
考虑 (g(0,0,k))， 只能靠层内成环实现，由于不能有重边，环还得是长度 >3 的：
[g(0,0,k) = sum_{l=3}^k g(0,0,k-l)inom {k-l}{l-1}frac{(l-1)!}2 ]考虑 (g(0,j,0))， 只能靠层内配对实现， 进一步得到 (2mid j)， 考虑标号为 1 的点与谁配对：
[g(0,j,0) = g(0,j-2,0)cdot (j - 1) ]考虑 (g(0,j,k))， 考虑一个度数为 2 的点， 它可以连接一个度数为 2 的点， 也可以连接一个度数为 3 的点：
[g(0,j,k) = (j-1)cdot g(0,j-2,k) + kcdot g(0,j, k-1) ]考虑 (g(i,j,k))， 考虑 i 个点中的一个， 它可以连接一个度数为 2 的点， 也可以连接一个度数为 3 的点：
[g(i,j,k) = jcdot g(i-1,j-1,k) + kcdot g(i-1,j+1,k-1) ]
【记录】
bzoj 1005
明♂明♂的 fa♂ 恼♂
prufer 序列。
如下定义一个有标号无根树 (T) 的 prufer 序列：
选取 T 上标号最小的度数为 1 的点 x， 将与 x 相邻的点的标号加入好序列的末尾， 然后删去 x 和对应的边， 重复以上操作，直到树中只剩下 2 个点。
显然对于一个树， 用其生成的 Prufer 序列是唯一的。
接下来证明对于每个序列，都存在唯一对应的树。
初始令 (G = {1,2,cdots,n})， 取 (x = min(G-Prufer))， 将 x 与 Prufer 的第一项相连， 然后删去 Prufer 的第一项和 G 中的 x。
重复以上操作， 直到 Prufer 为空。
此时 (|G| = 2)， 最后连接 G 中的两个点即可。
如此，得到的树一定是能生成这个 Prufer 序列的树。
显然若一个点 i 的度数为 (d_i)， 那么它在 Prufer 序列中出现了 (d_i-1) 次。
那么对于原题， 求有多少个长度为 (n - 2) 的 Prufer 序列， 满足度数的限制。
无解显然很好判断， 有解也好判断。
Py♂thon♂ is♂ good♂。
对高精 PTSD， 不写了。
loj6244
由于一个 k 排列中有 x 个是正确的， 有 (dbinom kx) 种方案， 剩下 k - x 个位置就可以看作是从 n-x 个元素的子集中选出 k-x 个排列， x = 0 的方案数。
使用容斥原理， 记命题 (P_i) 表示排列中 i 还在位置 i， 那么就是求不满足所有命题的方案数：
代码就不写了。
bzoj 1089
考虑深度 (le d) 的 n 元树的数目， 记为 (f_d)。
那么显然按照符号化方法的思想， (f_d = f_{d-1}^n + 1)。
(f_d - f_{d-1}) 即为最终的答案。
代码就不写了。