[关闭]
@Cyhlnj 2019-04-06T12:33:45.000000Z 字数 119281 阅读 858

退役前的部分记录/计划

Cyhlnj算法总结
Myblog

注意!!!

ios :: sync_with_stdio(false);
用了这个后只能 cin,cout,不然会

Contest online

AtCoder(Yahoo Programming Contest 2019)
A
个选前两个贪心
B
判断是否是一条链
C
如果 那么只进行操作一
否则先凑足 个,每次换完钱后再换饼干
D
这场比赛最难的题目?
假设枚举了一个起点和终点
那么 之间的贡献就是其间 为奇数的个数,可以转化为前缀和的形式
考虑 向左或 向右走的贡献
同样的枚举一个边界,贡献就是边界之外的 加上边界内的偶数()的个数,算上 的贡献,这个都可以预处理,都是前(后)缀相减取 的形式
最后枚举 ,也是前(后)缀相减取 的形式,乱搞搞就行了
E
枚举一个行的集合,如果这些行中有 个列的异或和为 个列的异或和为
那么列的选择方案就是
只需要统计异或和不为 的行向量集合个数
即总方案 异或和为 的行向量集合个数,线性基即可
F
不难发现序列第 个可以是前 个人手中的球
只需要 个的序列,剩下的组合数即可

Codeforces Global Round 1
A
模拟即可
B
总长度减去前 大的间距
C
,那么一定能找到一个数字 使得
否则,,输出 的最大因子
D
记录这每个数字的个数,
表示从小到大的第 个数字,这个数字还有 个,上一个有
理论上 ,一个位置能出的不同顺子最多三种,如果 ,那么一定有一种出了三次,直接拆开每个出三连即可
考场上写到了9
E
这个变换在差分数组上表现为相邻两个数的交换,直接判断即可
F
在线就是维护每个点到所有点的距离,主席树存储,两遍 预处理,空间有点卡
直接离线存储询问一起 就行了
G
官方题解
首先黑点不会获胜,如果黑点获胜,那么白点一定可以在按照黑点获胜的策略在之前获胜
考虑如果没有选过的点的做法,分情况讨论
1. 存在一个度数大于 的点,显然白点
2. 存在一个度数大于 的,且有大于 个非叶子的相邻点的点,还是
3. 剩下的情况就是一些度数为 的点,以及不超过两个的度数为 的点有大于一个叶子的相邻点的点,不难发现这种情况只有当点数为奇数的时候才会
4. 其它情况均为
考虑有选过的点怎么办,题解里面把这样的点变成了四个没有被选过的点
懒得放图片就描述一下中间一个点,然后周围挂三个点,选挂的三个点中任意一个为原来的点连回原图
这样为什么是对的呢,因为在双方绝顶聪明的时候,白的选了原来的点,黑的就一定会选中间的那一个,如果黑的再次选一个点,那么白的可以拿走剩下的点,状态不变
H
首先如果合法的串不多就是一个简单的 自动机 +
考虑到自动机上有很多状态是存在所有转移的,也就是数位 ,第一个满足 的地方
把所有这样的前缀加入 自动机,最多
表示从 点开始,任意再选 个能得到的合法串的个数
这样就把那些没有新建的状态的贡献加上了

Codeforces Round #545 (Div. 1)
T1
对于每行每列分别离散化,求出大于这个位置的数字的个数即可。
T2
每次选择当前串的最长的 接上去即可
T3
拆点,对于一个点 ,拆成 ,在原图中如果有边 则连边
可以发现如果 能到 ,那么 也一定能到达
所以 要么在同一个强连通分量里,要么不在同一条直链上。
所以直接缩点 即可。
T4
判环法,一个人 一次 步,另一个人 一次 步。
走了 步, 走了 步。
不难发现 ,而 是一次 步,所以 一定没有走完一个环,所以只要再次走 步就可以刚好到了终点。
其它的点也是一样。
总步骤
T5
不难发现每次加的一些 只要保留第一个就行了。
一操作很好做,直接扔掉前面的信息即可。
考虑二三操作,可以想到用单调队列来维护。
假设 ,那么一次三操作 变得小于 的条件显然是
,所以维护一个 的斜率单调递增的下凸壳即可。
T6
首先可以以最后烧掉的点为根,变成有根树。
考虑一次 操作的影响,设原来的根为 ,那么会使得 这条链的顺序变成 烧到 并且是最后烧的链,其它点相对顺序不变。
现在问题是怎么统计每个点在它之前的点的个数。
可以把 操作看成是一种区间(链)覆盖一个新的最大编号,然后换根。
那么一个点的排名就变成了小于等于它的编号的点个数减去它祖先编号和它相同的点的个数。
这种染色问题可以用 维护, 就直接 ,同一个编号的点一定在一棵 中,直接覆盖即可。
外加一个树状数组维护小于等于它的编号的点个数。

数学

导数积分表

导数


积分

各种东西

牛顿二项式


其中

MR素数测试

大整数分解/Pollard Rho

ExLucas

意义下的值

那么就只要求出模 的值,然后 合并即可
考虑求


1. 首先可以把分子分母中 的因子约分
的个数为

2. 提出 后,就只要求出 就好了,逆元也可以直接
先把 中含有 这个因子的项单独拿出,那么

对于 之前提出来算过了,所以递归处理后面的就好了
考虑前面的求法,
由于是模 意义下的,所以这些东西被分成若干段相乘,每段值一样,直接预处理即可

  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. namespace IO {
  5. const int maxn((1 << 21) + 1);
  6. char ibuf[maxn], *iS, *iT, c;
  7. int f;
  8. char Getc() {
  9. return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++);
  10. }
  11. template <class Int> void In(Int &x) {
  12. for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
  13. for (x = 0; c <= '9' && c >= '0'; c = Getc()) x = (x << 3) + (x << 1) + (c ^ 48);
  14. x *= f;
  15. }
  16. }
  17. using IO :: In;
  18. const int maxn(1e6 + 5);
  19. int mod, p[20], a[20], x[20], b[20], num, fac[maxn];
  20. inline int Pow(ll x, ll y, int m) {
  21. ll ret = 1;
  22. for (; y; y >>= 1, x = x * x % m)
  23. if (y & 1) ret = ret * x % m;
  24. return ret;
  25. }
  26. inline void ExGcd(int a, int b, int c, int &xx, int &yy, int m) {
  27. if (!b) {
  28. xx = (c / a + m) % m, yy = 0;
  29. return;
  30. }
  31. ExGcd(b, a % b, c, yy, xx, m);
  32. yy = (yy - 1LL * (a / b) * xx % m + m) % m;
  33. }
  34. inline ll Gcd(ll a, ll b) {
  35. return !b ? a : Gcd(b, a % b);
  36. }
  37. inline ll F(ll xx, int yy) {
  38. return xx < yy ? 0 : xx / yy + F(xx / yy, yy);
  39. }
  40. int ans, cur, xx, yy;
  41. inline int Inv(int a, int m) {
  42. return ExGcd(a, m, Gcd(a, m), xx, yy, m), xx;
  43. }
  44. inline int Fac(ll n, int pi, int xi) {
  45. return n <= pi ? fac[n] : 1LL * Pow(fac[xi], n / xi, xi) * fac[n % xi] % xi * Fac(n / pi, pi, xi) % xi;
  46. }
  47. ll n, m;
  48. inline ll Solve(int pi, int ai, int xi) {
  49. ll nn = F(n, pi) - F(m, pi) - F(n - m, pi);
  50. if (nn >= ai) return 0;
  51. nn = Pow(pi, nn, xi);
  52. int facn = Fac(n, pi, xi), im = Inv(Fac(m, pi, xi), xi), inm = Inv(Fac(n - m, pi, xi), xi);
  53. return 1LL * facn * im % xi * inm % xi * nn % xi;
  54. }
  55. int main() {
  56. In(n), In(m), In(mod), cur = mod, fac[0] = 1;
  57. for (int i = 2; i * i <= cur; ++i)
  58. if (cur % i == 0) {
  59. p[++num] = i, x[num] = 1;
  60. while (cur % i == 0) cur /= i, ++a[num], x[num] *= i;
  61. }
  62. if (cur > 1) p[++num] = cur, ++a[num], x[num] = cur;
  63. for (int i = 1; i <= num; ++i) {
  64. for (int j = 1; j <= x[i]; ++j)
  65. if (j % p[i]) fac[j] = 1LL * fac[j - 1] * j % x[i];
  66. else fac[j] = fac[j - 1];
  67. b[i] = Solve(p[i], a[i], x[i]);
  68. }
  69. for (int i = 2; i <= num; ++i) {
  70. int xx, yy, c = b[i] - b[1], lcm = x[1] * x[i];
  71. ExGcd(x[1], x[i], c, xx, yy, lcm);
  72. b[1] = (1LL * xx * x[1] % lcm + b[1]) % lcm, x[1] = lcm;
  73. }
  74. printf("%d\n", b[1]);
  75. return 0;
  76. }

伯努利数(坑)(重要)

拉格朗日乘数法(坑)

拉格朗日反演(坑)




扩展

杨氏矩阵(坑)

集合幂级数(坑)

线性插值(坑)

N/二次剩余

N次剩余

给定 ,且 最好为质数
可以算出 的解
首先可以算出 的原根
解方程 ,这个直接

那么 ,这个直接
无解在 的时候判掉,最后快速幂得到答案

二次剩余

的一个解 ,其中 为一个奇素数
1. 有二次剩余的条件


证明
首先有
若存在一个解 ,那么
所以

2. 算法一
如果 的原根,且 那么解就是
证明
结合上面的条件,有
因为 ,那么 一定为偶数
可以在 的复杂度内找到解
3. 算法二
随机一个数字
使得 不存在二次剩余,期望次数为
定义一个新的数域,设 (类似于 )
那么所有的数都可以表示为 的形式
根据有解的条件可以得到

所以
定理
证明
二项式定理展开得到
显然除了第 项和第 项的组合数不是 的倍数
那么就是
由于
那么得到

这就好了,因为
所以
现在只要证明 不存在 项就好了
假设
那么
所以 或者
如果 ,那么
因为 没有二次剩余,而 显然有二次剩余
所以 没有二次剩余,矛盾
得到
总结一下
第一步随机一个 ,使得 不存在二次剩余
第二步直接重载运算求出 的二次剩余

单纯型法(坑)

类欧几里德算法

类欧几里得算法的推导Cyhlnj

形式上类似于欧几里得算法,把 转化成 可能就是是类欧几里得算法的精髓

Catalan数

,卡塔兰数满足递归式:
(其中 )


第二类斯特林数

一类求解 的方法
  1. 二项式展开,通常合并的复杂度为
  2. 斯特林展开,通常是要计算 ,可以递推 转移。

表示 个球放进 个无标号的盒子内,要求盒子不为空的方案数
1. ,其中
2. ,其中
3. ,其中
4.
结论


的球放在 个不同的盒子内没有无空盒限制的方案数,枚举不是空的的盒子)
公式

可以容斥得到
转简得到

第一类斯特林数

表示 个不同元素,分成 个圆,排列的方案数
那么
显然有


结论

证明
一个排列对应一个置换
把这个置换中的上下对应位置连边,可以得到许多的环
由于排列和置换是一一对应的,所以我们要求排列的个数,就是求用n个元素组成环的方案数,所以我们枚举环的个数
它的生成函数


nlogn倍增

那么
考虑利用 推出

那么



所以可以反转之后

bell数

的集合划分数,显然是第二类斯特林数的前缀和


即枚举 的划分

BurnSide&Polya

置换个数 等价类个数 不动点数

Tarlor展开

斐波拉契数列的性质Cyhlnj






扩展欧拉定理

原根

定义
两种
1.对于一个数的最小正整数,那么就称的原根
2.假设一个数对于来说是原根,那么的结果两两不同,且有 ,那么可以称为是的一个原根
性质

求法

求模原根的方法:对素因子分解

若恒有成立,则就是的原根

容斥

反演




下面的直接带入到上面


如果 ,那么 之间是能够反演的
都是下三角矩阵, 就是单位矩阵
知道这个就可以矩阵求逆打表了,而且你发现直接求逆是

二项式反演

证明



单位根反演

不能丢!!!


证明:
,那么

否则,等比数列求和

如果能快速求出某个多项式的点值,那我们就可能能求出 的特定倍数幂的系数和。
形式化的,我们可以求

带入到所求的东西中去





stirling反演

把第一类Stirling数看成无符号的

第一类Stirling数幂与下降幂的关系

第二类Stirling数幂与下降幂的关系

反转公式

证明



那么

另外一个同理

Min-Max容斥以及kthmax扩展

证明
考虑一种第 大值被作为最小值计算的次数

kthmax
求第 大元素
构造容斥系数
使得


考虑第 大值被作为最小值计算的次数

它应该等于


二项式反演得到

那么

X X
X
X
X X

(数字即为满足要求的, 为对角线)

显然, 为一组, 为一组
两两互不干扰,每一组相当于是不能同时选两个相邻的位置(组中)
然后就可以 出 忽略 个,有 个满足要求的方案
这样再乘上 就可以算出 表示至少有 个位置满足要求的排列方案
要算出恰好 个的,然而答案不是 (虽然看上去很对)

因为 个受了限制,另外 个没有限制的也会有满足要求的情况
这样就导致一种情况被算了多次,并且显然在 个的时候和 的时候被重复算的次数不同

假设 表示恰好有 个位置满足要求的排列方案
那么
因为每一种恰好 个的被算了