「Math」Math Theory

| | 0 | 总字数 16.5k | 期望阅读时间 75 min
  1. 1. 数论
    1. 1.1. 基础知识
      1. 1.1.1. 唯一分解定理
      2. 1.1.2. 互质
      3. 1.1.3. 整除
      4. 1.1.4. 素数判定
      5. 1.1.5. 线性筛
        1. 1.1.5.1. 「ep1」 质因数分解$N!$。
        2. 1.1.5.2. 「ep2」 求$[L, R]$的质数个数。$L, R \leq 2^{31}, R - L \leq 10^{6}$。
      6. 1.1.6. 调和级数
      7. 1.1.7. 约数
      8. 1.1.8. 余数
        1. 1.1.8.1. 「ep3」求$\sum_{i = 1}^{n}{k ; mod ; i}$。
        2. 1.1.8.2. 「ep4」求$\sum_{i = 1}^{n}{\sum_{d | i}{d^2}} ; mod ; p$,$n \leq 10^{12}, p \leq 10^9$
      9. 1.1.9. 最大公约数和最小公倍数
        1. 1.1.9.1. 「ep5」给出$a_0, b_0, a_1, b_1$,求满足$gcd(x, a_0) = a_1, lcm(x, b_0) = b_1$的$x$的个数,$a, b \leq 10^9 $
      10. 1.1.10. 欧拉函数
        1. 1.1.10.1. 欧拉函数拓展
          1. 1.1.10.1.1. $O(n)$递推
          2. 1.1.10.1.2. 狄利克雷卷积和莫比乌斯反演初步
      11. 1.1.11. 同余
      12. 1.1.12. 欧拉定理
        1. 1.1.12.1. 关于欧拉定理的本质
        2. 1.1.12.2. 「ep6」求$a^{b^{b^{b…}}} \ mod \ (10^{9} + 7)$,$b$有$n$个。$a, b \leq 10^{16}$。
      13. 1.1.13. 拓(扩)展欧几里得算法
        1. 1.1.13.1. 「ep7」BZOJ1407 Savage
      14. 1.1.14. 乘法逆元
      15. 1.1.15. 线性同余方程
        1. 1.1.15.1. 中国单身狗定理
        2. 1.1.15.2. $EXCRT$ 中国EX单身狗定理(大雾
        3. 1.1.15.3. BSGS
      16. 1.1.16. 线性基
        1. 1.1.16.1. SCOI2016 幸运数字
        2. 1.1.16.2. BZOJ2844
        3. 1.1.16.3. T3
      17. 1.1.17. 数论函数补充
      18. 1.1.18. 莫比乌斯反演
        1. 1.1.18.1. 容斥原理
      19. 1.1.19. 矩阵乘法
        1. 1.1.19.1. 「ep8」求斐波那契数列的第$n$项,$n \leq 10^{18}$。
        2. 1.1.19.2. 「ep9」求斐波那契数列前$n$项和,$n \leq 10^{18}$。
        3. 1.1.19.3. 矩阵中的图论建模
          1. 1.1.19.3.1. 「ep10」工作 (by ihopenot)
          2. 1.1.19.3.2. 「ep11」给出一个满足对角线均为正数的非负矩阵,判断这个矩阵是否有某一次方为全正数矩阵。$n \leq 1000$ (by ihopenot)
      20. 1.1.20. 组合计数
        1. 1.1.20.1. 加法原理和乘法原理
        2. 1.1.20.2. 排列和组合
        3. 1.1.20.3. 组合数的性质
        4. 1.1.20.4. 组合数的求解
        5. 1.1.20.5. $Catalan$数列
      21. 1.1.21. 组合数学 ver2.0
      22. 1.1.22. 生成函数
      23. 1.1.23. 数学期望
        1. 1.1.23.1. 「ep8」某个星球有$n$天,抽取$k$个人,问至少两个人生日在同一天的概率是。$1 \leq k \leq n \leq 10^{6}$。
        2. 1.1.23.2. 「ep9」毛玉问题,有$K$只毛玉,每只生存一天就会死亡,每只毛玉在死之前有可能生下一些毛玉,生$i$个毛玉的概率是$pi$,问$m$天后所有的毛玉都死亡的概率是多少? 所有数据$\leq 1000$。($UVA11021$
        3. 1.1.23.3. 「ep10」咕咕咕
        4. 1.1.23.4. 「ep11」咕咕咕
        5. 1.1.23.5. 「ep12」咕咕咕
        6. 1.1.23.6. 「ep13」咕咕咕
        7. 1.1.23.7. 「ep14」Va-11 Hall-a (by ihopenot)
          1. 1.1.23.7.1. 「题目描述」
          2. 1.1.23.7.2. 「输入格式」
          3. 1.1.23.7.3. 「输出格式」
          4. 1.1.23.7.4. 「样例输入」
          5. 1.1.23.7.5. 「样例输出」
          6. 1.1.23.7.6. 「数据规模及约定」
          7. 1.1.23.7.7. 题解
        8. 1.1.23.8. HDU3853
        9. 1.1.23.9. POJ2151
        10. 1.1.23.10. POJ3071
        11. 1.1.23.11. CF148D
        12. 1.1.23.12. POJ3744
        13. 1.1.23.13. BZOJ4318
        14. 1.1.23.14. HDU4405
        15. 1.1.23.15. HDU4336
        16. 1.1.23.16. BZOJ3143
      24. 1.1.24. 泰勒展开
      25. 1.1.25. 指数型母函数
        1. 1.1.25.1. POJ3734
      26. 1.1.26. SG函数 $Sprague - Grundy$
        1. 1.1.26.1. LUOGU2575
  2. 2. 骚操作补充
    1. 2.1. 十进制快速幂
      1. 2.1.1. 求$a^b \ mod \ p$,$b \leq 10^{10000}$。
  3. 3. 一些题目备选

数论

这真的是一篇很长的数论笔记。

数论全笔记

基础知识

  • 整除
  • 素数判定
  • 线性筛
  • 互质
  • 约数
  • 调和级数
  • 余数
  • 最大公约数和最小公倍数
  • 欧拉函数

唯一分解定理

每个数,都可以唯一被分解成$p_1^{c_1}p_2^{c_2}…p_n^{c_n}$的形式,其中$p_i$是素数。

互质

$a$, $b$互质,即没有公共的质因子。即在唯一分解后,所有的$p_i$不相同。

整除

通常有两种写法…这份笔记中,所有的都依照后面一种。

  • 若$a ; mod ; b = 0$,则$a$能被$b$整除,或$b$能整除$a$,写作$a | b$
  • 若$b = ka$,记为$b$被$a$整除,$a$整除于$b$。写作$a | b$。

绕一绕的话…$n = km$,读作$m$整除$n$,$n$被$m$整除,$m | n$,$|$的前后顺序依照$x$整除$y$的形式…绕一绕…过一会儿就绕好了~总之记住,小的放前面,大的放后面。

整除的性质是一切证明的关键,这里给出:

  • $a | b, a | c$,则有$a | (b \pm c)$。

素数判定

若一个数$N$是合数,一定存在$T \leq \sqrt{n}$,且$T$能整除$N$。

反证法,假设命题不成立,那么一定存在$T > \sqrt{n}$且$T | N$。那么一定存在$\frac{N}{T} \leq \sqrt{n}$且$\frac{N}{T} | N$。则命题成立~

代码为试除法

inline bool prime(ll val)
{
  for (int i = 2; i <= sqrt(val); ++i)
    if(val % i == 0) return false;
  return true;
}

线性筛

普通筛法略过了,我们讲讲线性筛。

线性筛$O(n)$的原理是,使每个数只被自己最小的质因子筛一次。

都知道$a \in N$,$b$是质数,那么$a \cdot b$一定不是质数。我们令每个合数只被自己最小的质因子$p$筛出来,那么每个合数只会被筛一次.我们对于每一个数$a$,用$a$去乘上$\leq a$的所有质数。接下来给出,到每个数的时候,它一定被筛过的证明。

这里是我万年理解不到的…别的教程也不提这个…so郁闷,请把这一段认真看完…我尽量保证了语言没问题。

我们的筛法是,标记某个小于其本身质数 $\times$ 某个小于其本身的合数。那么,假设,在进行那个“小于其本身的素数”的处理的时候,我们枚举了所有小于其本身的合数,而那时的$break$规则是$prm[j] * val > n$,这个数一定是$\leq n$的,所以其一定被筛过。这种反向思考很赞,但是别人为啥都不提这一点呢。但是啊,普通筛的时候,这么看吧!假如说当前的数可以被分解成$p_1^{c_1}…$,那么它会被所有的$p$筛一次,而某个数的素因子的个数是$\log{n}$级别的,那么复杂度$n\log{n}$。线性筛保证每个数一定只会被其最小的质因子筛过一次,根据上面的描述,已经足够了,所以线性筛的复杂度是$O(n)$。

代码如下

inline void prime()
{
  for (int i = 2; i <= n; ++i)
  {
    if(!vis[i]) prm[++cnt] = i;
    for (int j = 1; j <= cnt; ++j)
    {
      if(i * prm[j] > n) break;
      vis[i * prm[j]] = 1;
      if(i % prm[j] == 0) break;
    }
  }
}

代码的顺序和刚才思维的顺序略有不同,而这正好是线性筛的妙处啊!

尝试一下,并不好实现的思维题

「ep1」 质因数分解$N!$。

这样看~

利用线性筛的思路,我们每个合数只被其最小质因子筛一次。

我们知道一个数的质因数分解形式后,用这个数乘上一个质数,能够知道计算结果的质因数分解形式。我们对结果的形式累乘,就是答案~不优化的话,时间复杂度和空间复杂度都是$O(n\log{n})$,实现也会很复杂。仅练习思维。

「ep2」 求$[L, R]$的质数个数。$L, R \leq 2^{31}, R - L \leq 10^{6}$。

可以筛$R - L$的,那么我们先把$[2, \sqrt{R}]$之间的数筛出来,这里的数一定可以组合出$[L, R]$的所有数。然后对于所有质数,我们进行$[L, R]$的标记。$vis[i \times p] = 1, i \in [\frac{L}{p}, \frac{R}{p}]$。

调和级数

并不能给出详细的解答,总之记住公式,$\sum_{i = 1}^{n}{\frac{n}{i}} = n\ln{(n+1)} + nr$。$r$为欧拉常数,约等于$0.5772156649$,所以遇到形如$\sum_{i = 1}^{n}{\frac{n}{i}}$的算式,在时间复杂度中通常记作$n\log{n}$,或$n\ln{n}$。我习惯前者。调和级数通常用作时间复杂度的证明。

约数

下面介绍一点约数常用定理。

定义$N$。

约数的定义为$d | N$,d为约数。

可以简单发现,$p_i$是$N$的约数,也就是说,$p_1^{c_1}p_2^{c_2}…p_n^{c_n}$的子集都是其一个约数。

假设$N$进行唯一分解后的数是$p_1^{c_1}p_2^{c_2}…p_n^{c_n}$。

  • $N$的正约数的个数 $=\prod_{i = 1}^{m}{(c_i + 1)}$。乘法原理
  • $N$的正约数和为$\prod_{i = 1}^{m}{(\sum_{j = 0}^{c_i}{(p_i)}^j)}$。手玩~
  • $N$的正整数约数集合是试除法,这里不再赘述…
    还有一个求法。
  • 对于数字$d$,$d$一定是$d \cdot k$的约数。这样筛下来,复杂度是$O(\sum_{i = 1}^{n}{\frac{n}{i}})$。利用调和级数,$O(n\log{n})$。比$O(n\sqrt{n})$要好得多。

余数

$a ; mod ; b = c$,称$c$是$a$除以$b$的余数。余数的定义式如下 $a ; mod ; b = a - \lfloor \frac{a}{b} \rfloor \cdot b$
看一个例题:$BZOJ1257$。

「ep3」求$\sum_{i = 1}^{n}{k ; mod ; i}$。

转化题目,求$\sum_{i = 1}^{n}{(k - \lfloor \frac{k}{i} \rfloor \cdot i)} \Rightarrow k \times n -\sum_{i = 1}^{n}{(\lfloor \frac{k}{i} \rfloor \cdot i)}$。由于复杂度的问题,我们从$\frac{k}{i}$入手,因为会有一段区间,使得其不变。我们设$\lfloor\frac{k}{i}\rfloor = x$。这段区间的值是$\frac{(i_{first} + i_{end}) \times (end - first + 1)}{2} \times x$。所以问题来了,我们需要快速获取什么区间内,$\lfloor\frac{k}{i}\rfloor$不变。
结论如下,我也不知道怎么推的。$i \in [x, \lfloor \frac{k}{\lfloor \frac{k}{x} \rfloor} \rfloor]$时,$\lfloor\frac{k}{i}\rfloor$不变。$x$是上一个的右端点 + 1,即这次的左端点,这是数论分块的经典写法。具体请见代码,lyd的代码如下:

#define ll long long
#define R register
#include <bits/stdc++.h>

using namespace std;

ll n, k, ans;
int main()
{
  scanf("%lld%lld", &n, &k);
  ans = n * k;
  for (int l = 1, r; l <= n; l = r + 1)
  {
    r = k / l ? min(k / (k / l), n) : n;
    ans -= (k / l) * (l + r) * (r - l + 1) / 2;
  }
  printf("%lld", ans);
}

「ep4」求$\sum_{i = 1}^{n}{\sum_{d | i}{d^2}} ; mod ; p$,$n \leq 10^{12}, p \leq 10^9$

首先,$\sum{i ^ 2} = \frac{n(n + 1)(2n + 1)}{6}$,是公式,至于怎么用,下面通过这道题来解释。

首先注意到,枚举$i$是不现实的。$10^{12}$不可能。我们转换思维,枚举$d$。

对于$d \leq n$,$d$的倍数的个数为$\lfloor \frac{n}{d} \rfloor$,每次的贡献是$\lfloor \frac{n}{d} \rfloor \cdot d^2$,对整体进行数论分块,对于$\sum_{i \in [L, R]}{i^2} = \frac{R(R + 1)(2R + 1)}{6} - \frac{(L - 1)(L)(2L - 1)}{6}$,我们对于$\lfloor \frac{n}{d} \rfloor$相同的整体进行计算,然后套数论分块模板~

// by kririae
#define ll long long
#include <bits/stdc++.h>

using namespace std;

ll n, mod, ans;

inline ll fast_pow(ll a, ll p)
{
  ll ans = 1; a %= mod;
  for (; p; p >>= 1)
  {
    if(p & 1) ans = (a * ans) % mod;
    a = (a * a) % mod;
  }
  return ans;
}

inline ll inv(ll a, ll p)
{
  return fast_pow(a, p - 2);
}

inline ll calc(ll val)
{
  static ll _inv = inv(6, mod); val %= mod;
  return (((((val * (val + 1)) % mod) * ((val << 1) + 1)) % mod) * _inv) % mod;
}

int main()
{
  scanf("%lld%lld", &n, &mod);
  for (ll l = 1, r; l <= n; l = r + 1)
  {
    r = (n / l) ? min(n / (n / l), n) : n;
    ans = (ans + (n / l) * ((calc(r) - calc(l - 1) + mod) % mod)) % mod;
  }
  printf("%lld", ans);
}

复杂度是$O(\sqrt{n})$。

简单总结下这道题过程中出现的问题…

  • calc(r) - calc(l - 1)出现了负数。
  • 逆元求太多次,忘了加static
  • 注意mod的问题。

逆元的问题我会在后面提到。

最大公约数和最小公倍数

定义:若存在$d$,$d | a$且$d | b$,$d$中最大的一个就是$gcd(a, b)$,$(a, b)$的最大公约数。若存在$a | m$且$b | m$。$m$取值最小的一个被称作$lcm(a, b)$,$(a, b)$的最小公倍数。

特别的,给出另一种$gcd$的理解方式。将$a, b$进行质因数分解,这俩重叠的部分就是$gcd(a, b)$。下面的证明将会用到。这种理解方式会被用到大量的证明中去。

最大公约数性质如下,$gcd(a, b) = gcd(b, a)$,$gcd(a, 0) = a$,$gcd(a, 1) = 1$, $gcd(ak, bk) = k \cdot gcd(a, b)$,$gcd(a + kb, b) = gcd(a, b)$,若$gcd(a, b) = 1$, $gcd(ab, k) = gcd(a, k) \cdot gcd(b, k)$。

给出最后一条的证明,这里会用到$gcd$的另一种理解方式~。

证明:$k = \prod{k_i^{f_i}}$,$a = \prod a_i^{q_i}$,$b = \prod b_i^{s_i}$ ,则根据定义:$gcd(a, k) = \prod a_i^{min(q_i, f_i)}$ ,$gcd(b, k) = \prod b_i^{min(s_i, f_i)}$ ,又$a$, $b$互质,所以不存在$a_i = b_i$,则$ab = \prod a_i^{q_i} \cdot \prod b_i^{s_i}$,从而$gcd(ab, k) = \prod a_i^{min(q_i, f_i)} \cdot \prod b_i^{min(s_i, f_i)} =gcd(a, k) \cdot gcd(b, k)$。$Q.E.D$

倒数第二条的证明我将在更相减损术处提到。

有定理,$gcd(a, b) \times lcm(a, b) = a \cdot b$。令$d = gcd(a, b)$,$x = \frac{a}{d}, y = \frac{b}{d}$。则$gcd(x, y) = 1, lcm(x, y) = x \cdot y$。则$lcm(x, y) \cdot d = \frac{a \cdot b}{d}$。

更相损减术,定理如下,$gcd(a, b) = gcd(b, a - b) = gcd(a, a - b)$。欧几里得算法,$gcd(a, b) = gcd(b, a ; mod ; b)$。由于更相损减术是欧几里得算法的特例,这里给出欧几里得算法的证明。若$a < b$,易得$gcd(a, b) = gcd(b, a)$。若$a \geq b$,不妨设$gcd(b, a ; mod ; b) = gcd(a - nb, b)$,$n$为任意整数。设$a = nb + k$,根据定义,有$k = a ; mod ; b$。对于公约数$d$,有$d | a$,$d | nb$。则$d | (a - nb)$。$d | k$,所以$d | b, d | a ; mod ; b$.,公约数集合相同,所以最大公约数相同。备注一句,因为$d$对于所有公约数都成立,所以说公约数集合成立,这是证明中的常见手段。

代码如下:

int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}

「ep5」给出$a_0, b_0, a_1, b_1$,求满足$gcd(x, a_0) = a_1, lcm(x, b_0) = b_1$的$x$的个数,$a, b \leq 10^9 $

朴素算法如下,我们知道,$x | b_1, b0 | b1$,$a_1 | x, a0 | a_1$,某个数的约数个数大约$2 \sqrt{n}$,我们枚举$b_1$的约数$x$,然后$check$是否满足$gcd(x, a_0) = a_1, lcm(x, b_0) = b_1$。具体来说,我们用搜索算法组合出$b_1$所有的约数,然后判断条件是否满足,可过,代码懒得给了qwq颓颓颓

机智的算法先咕咕咕着…

欧拉函数

之前提到过,对于$gcd(a, b) = 1$的情况,我们称$a, b$互质,互质的另一种解释方法是:$a = \prod{a_i^{q_i}}$,$b = \prod{b_i^{e_i}}$,所有的$a_i != b_i$。也就是${a} \cap {b} = \emptyset$。对于三个及更多,互质称作“两两互质”,即所有的数没有公共质因子。

欧拉函数,定义为$[1, n]$中和$n$互质的数的个数,记作$\varphi(n)$。

$\varphi(n)$有以下公式:

$$\varphi(n) = n \cdot \prod_{(prime;p) | n}{(1 - \frac{1}{p})}$$

证明:

设$p$为$n$的质因子,则$p | n$,而$kp \leq n$的所有$kp$都不与$n$互质。而$kp$有$\lfloor \frac{n}{p} \rfloor$个,而$q$为$n$质因子,$kq$有$\lfloor \frac{n}{q} \rfloor$个,而$pq$的倍数又被重复计算,所以$n$中含有$\lfloor \frac{n}{pq}\rfloor$个重复计算的,需要剔除。$[1, n]$中不含$p, q$为质因子的数的个数是$n - \frac{n}{p} - \frac{n}{q} + \frac{n}{pq} = n(1 - \frac{1}{p})(1 - \frac{1}{q})$。同理可得。代码如下:注意精度问题,需要特殊处理。

inline int phi(int n)
{
  int ans = n;
  for (int i = 2; i <= sqrt(n); ++i)
    if(n % i == 0)
    {
      ans = (ans - ans / i);
      while(n % i == 0) n /= i;
    }
  if(n > 1) ans = ans - ans / n;
  return ans;
}

$\varphi$函数的性质有:

  • $[1, n]$的数中和$n$互质的数的和是$\frac{n \cdot \varphi(n)}{2}$。就是$gcd(a, n) = 1$,$a$的和。由九章算术,$gcd(n, a) = gcd(n, n - a)$。所以我们要求出$(n, n - a)$的平均数,手玩可得,平均数为$\frac{n}{2}$。
  • 若$a, b$互质,则$\varphi(ab) = \varphi(a) \cdot \varphi(b)$。这是积性函数的性质,积性函数我将会在后面进行讨论。设$a = \prod{a_i^{c_i}}$,$b = \prod{b_i^{d_i}}$。则$\varphi(a) = a \cdot \prod_{i \in {a_i}}{(1 - \frac{1}{i})}$,$\varphi(b) = b \cdot \prod_{i \in {b_i}}{(1 - \frac{1}{i})}$。又${a_i} \cap {b_i} = \emptyset$,则$\varphi(a) \cdot \varphi(b) = ab \cdot \prod_{i \in {a_i}}{(1 - \frac{1}{i})} \cdot \prod_{i \in {b_i}}{(1 - \frac{1}{i})}$,且$\varphi(ab) = ab \cdot \prod_{i \in ({a_i} \cup {b_i})}{(1 - \frac{1}{i})}$,得证。写公式好累。通过这个性质,可以$O(n)$预处理$\varphi$值。这个先不忙。
  • $n$为质数时,$\varphi(n) = n - 1$。这个没必要解释吧QwQ
  • $\sum_{d | n}{\varphi(d)} = n$。这条的证明已经折磨了我一个小时了…可以用狄利克雷卷积来证明。有一个初等证明,但还是不简单。对逻辑要求极高。
    证明:
    首先,对于分母为$b$,分子为$a$,$a < b$的既约分数,假如说固定$b$的取值,那么$a$的取值有$\varphi(b)$种。关于这道题,我们考虑所有的$\frac{i}{n}, i \in [1, n]$,将其约分,对于约分后的分数$\frac{a}{b}$,一定有$gcd(a, b) = 1, b | n, a | i$且$a < b$。假定一个$d | n$,那么在之前的分数集合中,以$d$为分母的既约分数个数就有$\varphi(d)$个。而$|$分数集合$| = n$,所以$\sum_{d | n}{\varphi(d) = n}$
    $Q.E.D.$
    举个例子来演示一下吧
    对于$6$,我们构造出了$\frac{1}{6}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3},\frac{5}{6}, \frac{1}{1}$。这其中,以$1 | 6$为分母的有$\varphi(1)$个,也就是$\frac{1}{1}$。以$2 | 6$为分母的有$\varphi(2)$个,也就是$\frac{1}{2}$。以此类推,我们可以发现,分母$d$的取值只有$d | n$,而$\varphi(i)$的和正是前面分数集合的大小。
    真是妙极了
  • $n = \prod{p_i^{c_i}}$,则$f(n) = \prod{f(p_i^{c_i})}$。首先,易得,$gcd(p_i^{c_i}, p_j^{c_j}) = 1$,满足积性函数,则易证。
  • 若$p | n$,则有$\varphi(p \cdot n) = \varphi(n) \cdot p$
  • 反之,$\varphi(p \cdot n) = \varphi(n) \cdot (p - 1)$。
    因为$p$是质数,且$p \nmid n$(?),所以$gcd(p, n) = 1$。有$\varphi(p) = p - 1$,由积性函数性质可证明。对于$p | n$,带入定义式,$\varphi(n) = n \cdot \prod_{(prime;p) | n}{(1 - \frac{1}{p})}$,因为$p | n$,所以直接在前面的$n \cdot p$,得证。(好方法啊

欧拉函数拓展

$O(n)$递推

证明参见刚才的最后俩条

inline void phi(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if(!vis[i]) prm[++cnt] = i;
        for (int j = 1; j <= cnt; ++j)
        {
            if(i * prm[j] > n) break;
            vis[i * prm[j]] = 1;
            if(i % prm[j] == 0)
            {
                phi[i * prm[j]] = phi[i] * prm[j];
                break;
            } else phi[i * prm[j]] = phi[i] * (prm[j] - 1);
        }
    }
}
狄利克雷卷积和莫比乌斯反演初步

$Dirichlet$定义如下:$qwq(n) = \sum_{d | n}{f(n)g(\frac{n}{d})}$ 。简化记为$qwq(n) = f(n) * g(n)$。我只会这点(逃

同余

同余的定义如下,$a ; mod ; m = b ; mod ; m$,则称$a, b$同余,写作$a \equiv b ; (mod ; m)$ ,a \equiv v \ (mod \ m).

对于$i \in [0, m - 1], {a + km}$,$i ; mod ; m = a$。这是$; mod ; m$下的同余类。模数$x$的同余类有$x - 1$个,构成完全剩余系

$[1, m]$中$gcd(i, m)$,$i$组成的集合叫做简化剩余系$S$。设$a \in S, b \in S$,由欧几里得算法可得$gcd(a \cdot b, m) = 1 \Rightarrow gcd(a \cdot b ; mod ; m, m) = 1$。则$a \cdot b \ mod \ m \in S$。

欧拉定理

欧拉定理的定义如下:如果$gcd(a, n) = 1$,则$a^{\varphi(n)} \equiv 1 \ (mod \ n)$。我并不会证明。欧拉定理可以推导出费马小定理。费马小定理如下:若$p$是质数,则$a^p \equiv a \ (mod \ p)$。我也不会证。

欧拉定理有重要推论,$a^b \equiv a^{b \ mod \ \varphi(n)} \ (mod \ n)$。若$a, n$互质。

关于欧拉定理的本质

这里又要提到一个别人不常提到的东西了。这样测试:$a^{i} \ mod \ p$。循环节的长度一定是$\varphi(p)$。但不一定是最小的。$5^i \ mod \ 13$的循环节是$5 \ 12 \ 8 \ 1$,长度为$4$,$\varphi(13) = 12$。$4 |12$。然后,之后会在拓欧降幂处提到。

「ep6」求$a^{b^{b^{b…}}} \ mod \ (10^{9} + 7)$,$b$有$n$个。$a, b \leq 10^{16}$。

首先需要知道,后面挂着的那一坨该怎么处理。我们看$b^b$的本质是什么?$b^b = \underbrace{b \times b \times \cdot\cdot\cdot \times b}_{b}$。转化为$a^{a^{b - 1}} \ mod \ (10^9 + 7)$。根据费马小定理$a^{p - 1} \equiv 1 \ (mod \ p)$。所以$a^{a^{b - 1}} \equiv a^{(a^{b - 1}) \ mod \ (p - 1)} \ (mod \ p)$。不懂这一步的话可以考虑$1$哪去了。然后用快速幂解决。

拓(扩)展欧几里得算法

拓欧的定理如下$ax + by = gcd(a, b)$。而我们就是要解这个不定方程。

问题来了,如何解?根据欧几里得算法,有$ax + by = bx’ + (a \ mod \ b)y’ = gcd(a, b) = gcd(b, a \ mod \ b)$。而根据之前提到过的模数的定义,$a \ mod \ b = a - \lfloor \frac{a}{b} \rfloor \cdot b$,得出$ax + by = bx’ + (a - \lfloor \frac{a}{b} \rfloor \cdot b)y’$。化简得到$ax + by = ay’ - b \cdot (x’ - \lfloor \frac{a}{b} \rfloor \cdot y’)$。我们令$x = y’, y = x’ - \lfloor \frac{a}{b} \rfloor \cdot y’$。当$b = 0$时,$x = 1, y = 0$。因为$ax = gcd(a, 0) = 1$。

$$
代码如下

inline void exgcd(int &x, int &y, int a, int b)
{
  if(b == 0) return x = 1, y = 0, void();
  else return exgcd(y, x, b, a % b), y -= (a / b) * x;
}

注意,由$bezout$定理可得,$exgcd$必定有整数解。简单解释一下代码,由于写成递归形式,某一层和上一层的$x, y$是反过来的。就有$y -= (a / b)*x$,对应原本的算式是$y = x’ - \lfloor \frac{a}{b} \rfloor \cdot y’$。

「ep7」BZOJ1407 Savage

推完公式后…出了各种各样的问题…干脆面向题解。

公式如下:$c_i + xp_i \equiv (c_j + xp_j) \pmod{M}$.如果存在解,那么可以有两个同一时刻在同一位置。转换为$x(p_i - p_j) - km = c_i - c_j$。首先判定有无整数解,如果有的话,$x \leq min(l[i], l[j])$。因为在死亡之后碰面不做数~

代码如下

// by kririae
#include <bits/stdc++.h>

using namespace std;

inline void exgcd(int &x, int &y, int a, int b)
{
  if(b) exgcd(y, x, b, a % b), y -= (a / b) * x;
  else x = 1, y = 0;
}

inline int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}

int n, c[20], p[20], l[20];

inline bool judge(int M)
{
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
    {
      int a = p[i] - p[j], b = c[j] - c[i];
      a = (a % M + M) % M;
      int g = gcd(a, M);
      if(b % g == 0)
      {
        // 有解
        int x = 0, y = 0;
        exgcd(x, y, a, M);
        x = ((x * (b / g)) % (M / g) + (M / g)) % (M / g);
        if(x <= min(l[i], l[j])) return false;
      }
    }
  return true;
}

int main()
{
  scanf("%d", &n);
  int mx = 0;
  for (int i = 1; i <= n; ++i) scanf("%d%d%d", &c[i], &p[i], &l[i]), mx = max(mx, c[i]);
  for (int M = mx; M <= 1e6; ++M)
    if(judge(M)) return printf("%d", M), 0;
}

乘法逆元

多数时候用于处理除法带$mod$的情况,$\frac{a}{b} \equiv a \cdot \mathrm{inv}(b) \pmod{m}$。$\mathrm{inv}(b)$就是$b$的逆元。逆元存在的前提是:…先不说这个,我们用丢番图方程的整数解来证明。上式可以化为$a \equiv ab \cdot \mathrm{inv}(b) \pmod{m}$。再次化简得到$b \cdot \mathrm{inv}(b) \equiv 1 \pmod{m}$。$b \cdot \mathrm{inv}(b) - km = 1$。此方程当且仅当$gcd(b, m) = 1$时有解,进而推导$b$在$mod \ p$意义下的乘法逆元当且仅当$gcd(b, m) = 1$时存在。第一种方法,对于逆元存在的时候,可以求$exgcd$。从而得出逆元。

还有一种解法,当$p$为质数时,利用费马小定理:$b^p \equiv b \pmod{m}$。$b \cdot b^{p - 2} \equiv \pmod{m}$。所以$b^{p - 2}$是$b$在模$p$意义下的乘法逆元。代码分别是exgcd(x, y, a, p), return (x % p + p) % preturn fpow(a, p - 2, p)

但是,还有一种球法!$inv[1] = 1, inv[i] = (p - \lfloor\frac{p}{i}\rfloor) \cdot inv[p \ mod \ i] \ mod \ p$。

写成代码是这样

for (int i = 2; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p % i] % p;

前两种复杂度是$O(log{n})$,最后一种是$O(n)$,不常用。

顺带一提,$inv(b, p) = inv(b \ mod \ p, p)$,不然用个锤。因为定义,$ax \equiv 1 \pmod{m}$。$ax \ mod \ m = a \ mod \ m \cdot x \ mod \ m$。

线性同余方程

给定$ax \equiv b \pmod{m}$。可以得到$ax + my = b$,有解当且仅当$gcd(a, m) | b$。方程的所有解是$\ mod \ \frac{m}{gcd(a, m)}$和$x$同余的整数。

中国单身狗定理

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

中国单身狗定理要求以下方程组的解

$$\begin{equation}
\left{
\begin{array}{lr}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\cdots \
x \equiv a_n \pmod{m_n}
\end{array}
\right.
\end{equation}$$

其中,$gcd(m_1, m_2, \cdots, m_n) = 1$。我被这玩意儿折腾半个月了,这里重新来认真搞一搞。

令$M = \prod{m_i}$,$M_i = \frac{M}{m_i}$。令$t_i$是$M_it_i \equiv 1 \pmod{m_i}$的一个解,(也就是$M_i$关于模$m_i$意义下的一个逆元。则$x$的唯一一组解是$x = (\sum_{i = 1}^{n}{a_it_iM_i}) \ mod \ M$。

证明:
因为$gcd(m_i, m_j) = 1$,所以$gcd(m_i, M_i) = 1$。所以,存在$t_i$,是$M_i$在$\ mod \ m_i$意义下的乘法逆元。即$t_iM_i \equiv 1 \pmod{m_i}$,可以得到$a_it_iM_i \equiv a_i \pmod{m_i}$,又$m_j | M_i$,所以$a_it_iM_i \equiv 0 \pmod{m_j}$。构造$x = \sum{a_it_iM_i}$,所以满足$x = a_it_iM_i + 0 \equiv a_i \pmod{m_i}$。$Q.E.D.$

$EXCRT$ 中国EX单身狗定理(大雾

相比$CRT$,$EXCRT$有个区别,$m_i, m_j$不一定互质。重新看方程:

$$\begin{equation}
\left{
\begin{array}{lr}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\cdots \
x \equiv a_n \pmod{m_n}
\end{array}
\right.
\end{equation}$$

既然无法一次合并,那就考虑两两合并。

我们考虑前俩方程:$x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod{m_2}$。转换成以下形式,$x = a_1 + k_1m_1, x = a_2 + k_2m_2$,减一下变成$k_1m_1 - k_2m_2 = a_2 - a_1$,根据某打起来太麻烦的定理,这里存在整数解的前提是$gcd(m_1, m_2) | a_2 - a_2$。然后解啊!用扩欧解出特解$k_1, k_2$。令$g = gcd(m_1, m_2), k_1’, k_2’$为俩特解,则$k_1 = \frac{m_2}{g}t + k_1’, k_2 = \frac{m_1}{g}t + k_2’$,带回原式:令$x_0 = a_1 + m_1k_1’$,$x \equiv x_0 \pmod{lcm(m_1, m_2)}$。

代码如下

// by kririae
// 题解ver
#define ll long long
#include <bits/stdc++.h>

using namespace std;

inline void exgcd(ll &x, ll &y, ll &g, ll a, ll b)
{
  if(b) exgcd(y, x, g, b, a % b), y -= (a / b) * x;
  else x = 1, y = 0, g = a;
}

inline ll EXCRT(ll *_a, ll *_m, ll n)
{
  ll a = _a[1], m = _m[1], g, x, y, mod;
  for (int i = 2; i <= n; ++i)
  {
    exgcd(x, y, g, m, _m[i]);
    if((_a[i] - a) % g) return -1;
    x *= (_a[i] - a) / g, mod = _m[i] / g, x = (x % mod + mod) % mod;
    a = m * x + a, m = m / g * _m[i], a %= m;
  }
  return (a % m + m) % m;
}

const int maxn = 1e5 + 5;
ll n, m[maxn], a[maxn];

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> m[i] >> a[i];
  cout << EXCRT(a, m, n) << endl;
}

BSGS

问题如下:

求解方程,$a^x \equiv b \pmod {p}$。其中$gcd(a, p) = 1$。

考场写不来BSGS咋办!暴力啊!

由费马小定理可得,$a^{p - 1} = 1$,所以只用从枚举$[0, p - 1]$。

然后考虑,如何优化爆搜。这时候就要拉出我们可爱的分块妹子。

设$x = i \cdot t - j$,其中$t = \sqrt{p}$。$j \in [0, t - 1]$。分块成功~方程转化为$a^{it - j} \equiv b \pmod{p}$。也就是$a^{it} = b \cdot a^j \pmod{p}$。注意$t$是定值,然后枚举$b \cdot a^j$,插入$hash$方便查询。再枚举$a^{it}$,到$hash$表去查询。代码如下:(SDOI2011 计算器)

// by kririae
#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline void exgcd(ll &x, ll &y, ll &g, ll a, ll b)
{
  if(b) exgcd(y, x, g, b, a % b), y -= (a / b) * x;
  else x = 1, y = 0, g = a;
}
inline ll fpow(ll a, ll p, ll mod)
{
  ll ans = 1;
  for (; p; p >>= 1) {
    if(p & 1) (ans *= a) %= mod;
    (a *= a) %= mod;
  } return ans;
}
inline ll BSGS(ll a, ll b, ll p)
{
  static map<ll, ll> fd;
  fd.clear(); int t = sqrt(p) + 1; b %= p;
  for (int j = 0; j < t; ++j)
    fd[(b * fpow(a, j, p)) % p] = j;
  if((a = fpow(a, t, p)) == 0) return b == 0 ? 1 : -1;
  for (int i = 0; i <= t; ++i) {
    ll val = fpow(a, i, p);
    int j = fd.find(val) == fd.end() ? -1 : fd[val];
    if(j >= 0 & i * t - j >= 0) return i * t - j;
  } return -1;
}
ll t, k, a, b, p, g, x, y;
int main()
{
  scanf("%lld%lld", &t, &k);
  switch(k) {
    case 1:
      while(t--) {
        scanf("%lld%lld%lld", &a, &b, &p);
        printf("%lld\n", fpow(a, b, p));
      } break;
    case 2:
      while(t--) {
        scanf("%lld%lld%lld", &a, &b, &p);
        exgcd(x, y, g, a, p);
        if(b % g) puts("Orz, I cannot find x!");
        else printf("%lld\n", ((x * (b / g)) % p + p) % p);
      } break;
    case 3:
      while(t--) {
        scanf("%lld%lld%lld", &a, &b, &p);
        ll ans = BSGS(a, b, p);
        if(ans == -1) puts("Orz, I cannot find x!");
        else printf("%lld\n", ans);
      } break;
  }
}

线性基

线性无关。

基的概念。

寻找线性基。

求出的线性基需要和原集合的选线性组合完全一致。

求线性基方法如下:

对于我新加入的某个数,我对它进行二进制的扫描,从高到低位。如果当前位$i$已经有一个线性基$a[i]$,那么我们可以认为,当前数如果要表示,一定选取了那个基,所以我们剔除基的影响,也就是$s[i] \ xor \ a[i]$。最后所得的$a[i]$就是所有的线性基。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5;
ll n, mx, t, ans, s[N], a[N];
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%lld", &s[i]);
  for (int i = 1; i <= n; ++i)
    for (int j = 51; j >= 0; --j)
      if(s[i] & (1ll << j)) {
        if(a[j] == 0) {
          a[j] = s[i];
          break;
        }
        s[i] ^= a[j];
      }
  for (int i = 51; i >= 0; --i) ans = max(ans, ans ^ a[i]);
  printf("%lld", ans);
}

SCOI2016 幸运数字

给出一棵树,每个结点都有一个值$a[i]$,求$i \rightarrow j$路径上的异或最大值。$n \leq 20000$

倍增上跑线性基。对于每个点$f[i][j]$,存一个$vector$,表示从$i$向上$2^j$的线性基有哪些…每次用$merge$进行暴力合并。最后查询的时候,找到$lca(i, j)$,然后对于$i \rightarrow lca(i, j)$,$j \rightarrow lca(i, j)$的线性基进行合并。复杂度$O(n\log^3{n})$。

再次跪拜q234rty神犇,没有他窝就A不了这道题。
因为。

for (int i = 0; i <= 60; ++i) if(b[i]) insert(b[i], a);

开始没加if。

第一种是树剖ver,复杂度$O(nlog^4n)$,不开O2跑不过。

#include <bits/stdc++.h>
#define ll long long
#define ls t[k].son[0]
#define rs t[k].son[1]
using namespace std;

namespace BZOJ4568 {
inline char gc()
{
  static char buf[1 << 18], *fs, *ft;
  return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline ll read()
{
  register ll k = 0, f = 1;
  register char c = gc();
  for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
  for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
  return k * f;
}
const int N = 20005;
struct Node {
  int l, r, son[2];
  ll b[65];
} t[N << 2]; int root, tcnt; ll g[N], w[N];
int n, q, head[N], ver[N << 1], nxt[N << 1], tot;
int siz[N], son[N], fa[N], dep[N], id[N], top[N], cnt;
inline void addedge(int u, int v) {
  ver[tot] = v;
  nxt[tot] = head[u];
  head[u] = tot++;
}
inline void dfs1(int x) {
  siz[x] = 1, son[x] = 0;
  for (int i = head[x], to; ~i; i = nxt[i]) {
    if((to = ver[i]) == fa[x]) continue;
    fa[to] = x, dep[to] = dep[x] + 1;
    dfs1(to);
    if(siz[to] > siz[son[x]]) son[x] = to;
    siz[x] += siz[to];
  }
}
inline void dfs2(int x, int topf) {
  id[x] = ++cnt, w[cnt] = g[x], top[x] = topf;
  if(!son[x]) return;
  dfs2(son[x], topf);
  for (int i = head[x], to; ~i; i = nxt[i]) {
    if((to = ver[i]) == fa[x] || to == son[x]) continue;
    dfs2(to, to);
  }
}
inline void insert(ll x, ll *a) {
  for (int j = 60; j >= 0; --j)
    if(x & (1ll << j)) {
      if(a[j] == 0) return a[j] = x, void();
      x ^= a[j];
    }
}
inline void merge(ll *a, ll *b) {
  for (int i = 0; i <= 60; ++i) if(b[i]) insert(b[i], a);
}
inline ll gmax(ll *a, ll ans = 0) {
  for (int i = 60; i >= 0; --i) ans = max(ans, ans ^ a[i]);
  return ans;
}
inline void pushup(int k) {
  merge(t[k].b, t[ls].b), merge(t[k].b, t[rs].b);
}
inline void build(int &k, int l, int r) {
  k = ++tcnt, t[k].l = l, t[k].r = r;
  if(l == r) return insert(w[l], t[k].b), void();
  int mid = l + r >> 1;
  build(ls, l, mid), build(rs, mid + 1, r);
  pushup(k);
}
inline void query(int k, int l, int r, ll *ans) {
  if(t[k].l == l && t[k].r == r) return merge(ans, t[k].b), void();
  int mid = t[k].l + t[k].r >> 1;
  if(r <= mid) query(ls, l, r, ans);
  else if(l > mid) query(rs, l, r, ans);
  else query(ls, l, mid, ans), query(rs, mid + 1, r, ans);
}
inline ll work(int x, int y) {
  static ll ans[65], tmp[65];
  memset(ans, 0, sizeof(ans));
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) swap(x, y);
    memset(tmp, 0, sizeof(tmp));
    query(root, id[top[x]], id[x], tmp);
    merge(ans, tmp);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) swap(x, y);
  memset(tmp, 0, sizeof(tmp));
  query(root, id[x], id[y], tmp);
  merge(ans, tmp);
  return gmax(ans);
}
inline void solve() {
  memset(head, -1, sizeof(head));
  n = read(), q = read();
  for (int i = 1; i <= n; ++i) g[i] = read();
  for (int i = 1, x, y; i < n; ++i) {
    x = read(), y = read();
    addedge(x, y);
    addedge(y, x);
  }
  dfs1(1), dfs2(1, 1), build(root, 1, n);
  for (int i = 1, x, y; i <= q; ++i) {
    x = read(), y = read();
    printf("%lld\n", work(x, y));
  }
}
}

int main() {
  return BZOJ4568::solve(), 0;
}

第二种是倍增ver,不开O2跑得过,复杂度$O(nlog^3n)$

#include <bits/stdc++.h>
#define ll long long
#define ls t[k].son[0]
#define rs t[k].son[1]
using namespace std;

namespace BZOJ4568 {
inline char gc()
{
  static char buf[1 << 18], *fs, *ft;
  return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline ll read()
{
  register ll k = 0, f = 1;
  register char c = gc();
  for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
  for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
  return k * f;
}
const int N = 20005;
struct Node {
  int l, r, son[2];
  ll b[65];
} t[N << 2]; int root, tcnt; ll g[N], f[N][25][65];
int n, q, head[N], ver[N << 1], nxt[N << 1], tot;
int fa[N][25], dep[N];
inline void addedge(int u, int v) {
  ver[tot] = v;
  nxt[tot] = head[u];
  head[u] = tot++;
}
inline void dfs(int x) {
  for (int i = head[x], to; ~i; i = nxt[i]) {
    if((to = ver[i]) == fa[x][0]) continue;
    dep[to] = dep[x] + 1, fa[to][0] = x;
    dfs(to);
  }
}
inline void insert(ll x, ll *a) {
  for (int j = 60; j >= 0; --j)
    if(x & (1ll << j)) {
      if(a[j] == 0) return a[j] = x, void();
      x ^= a[j];
    }
}
inline void merge(ll *a, ll *b) {
  for (int i = 0; i <= 60; ++i) if(b[i]) insert(b[i], a);
}
inline ll gmax(ll *a, ll ans = 0) {
  for (int i = 60; i >= 0; --i) ans = max(ans, ans ^ a[i]);
  return ans;
}
inline ll lca(int x, int y) {
  static ll ans[65];
  memset(ans, 0, sizeof(ans));
  if(dep[x] < dep[y]) swap(x, y);
  for (int i = 20; i >= 0; --i)
    if(dep[fa[x][i]] >= dep[y])
      merge(ans, f[x][i]), x = fa[x][i];
  if(x == y) return merge(ans, f[x][0]), gmax(ans);
  for (int i = 20; i >= 0; --i)
    if(fa[x][i] != fa[y][i]) {
      merge(ans, f[x][i]), merge(ans, f[y][i]);
      x = fa[x][i], y = fa[y][i];
    }
  merge(ans, f[x][0]), merge(ans, f[y][0]), merge(ans, f[fa[x][0]][0]);
  return gmax(ans);
}
inline void solve() {
  memset(head, -1, sizeof(head));
  n = read(), q = read();
  for (int i = 1; i <= n; ++i) insert(g[i] = read(), f[i][0]);
  for (int i = 1, x, y; i < n; ++i) {
    x = read(), y = read();
    addedge(x, y);
    addedge(y, x);
  }
  dfs(1);
  for (int t = 1; t <= 20; ++t)
    for (int i = 1; i <= n; ++i)
      fa[i][t] = fa[fa[i][t - 1]][t - 1],
      memcpy(f[i][t], f[i][t - 1], sizeof(f[i][t])),
      merge(f[i][t], f[fa[i][t - 1]][t - 1]);
  for (int i = 1, x, y; i <= q; ++i) {
    x = read(), y = read();
    printf("%lld\n", lca(x, y));
  }
}
}

int main() {
  return BZOJ4568::solve(), 0;
}

BZOJ2844

给出集合$S$,将集合$S$的所有子集取出来,对于每一个子集求出其异或和,排序,放到数组$a$中,给出数$k$,求$a$在$a$中第一次出现的下标是?

对于线性基的组合出来的集合$S_1$,我们把这个$S_1$分成两部分,第一部分是线性基,第二部分是由线性基组合出来的数字。假如$|S_1| = 2^n$,并且线性基有$m$个。对于查询的某一个数$j$,这个数一定可以由后面的$2^{n - m}$种组合再加上唯一的线性基的补全方案来组合。所以对于某一个数$j$,组合方案数和$j$是多少其实是无关的,所以只需要我们知道$j$在线性基的组合中排第几位。

重复一次,子问题就是求$j$是在线性基的所有子集的组合中的第几大。解决方式如下,对于$j$的每一位,假如说当前这一位$i$拥有一个$a[i] != 0$,那么我们可以称这一位是“流动”的。假如说不存在,那么一定选取了一个比它大的线性基。要理解这里还要明确“排序”的意义,假如说我选取了基$a_8$,那么对于第$8$位一定是选取了的。所以对于第$8$位的排序,一定是与流动的二进制位有关,这么看来,在集合$S_1$中的位置也只是由流动的二进制位决定的,对于数字$j$,我们抽离出所有的流动的二进制位,抽离的二进制位表示对应的$a$中的基的选取情况。因为选取更大的基,数字也就更大,所以二进制位的数值就是在$S_1$中的位置,最后套上$2^{n - m}$处理即可。

T3

给出$n$个数,把这些数分成两部分,使得这两部分的异或和差最小。$n \leq $

数论函数补充

以下公式都基于唯一分解定理。假设我们已经分解了$n$。
除了莫比乌斯函数,之前的都提到过:

  • $\varphi(n)$,欧拉函数,$[1, n]$中和$n$互质的数的个数。
  • $\sigma(n)$,$n$的正约数之和$\prod_{i = 1}^{m}{\sum_{j = 0}^{c_i}{p_i^{j}}}$。
  • $\mathrm{d}(n)$,$n$的正约数个数。$\prod{c_i + 1}$。

这几个的计算原理都很简单,就不给予证明了~。
然后,如题,补充的是莫比乌斯函数和莫比乌斯反演,我们直接进入下一个版块。

莫比乌斯反演

容斥原理

某小学学的东西,$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$。其实就是,首先算每个集合的大小,发现算重了旁边的,就减去,结果发现又算少了,又加上,这个思想在欧拉函数的计算上用到过。我们不如换个写法:

$$|\bigcup_{i = 1}^{n}{A_i}| = \sum_{i = 1}^{n}{|A_i|} - \sum_{1 \leq i < j \leq n}{|A_i \cap A_j|} + \sum_{1 \leq i < j < k \leq n}{|A_i \cap A_j \cap A_k|} - \cdots - (-1)^{n - 1}|A_1 \cap A_2 \cap \cdots \cap A_n|$$

咕咕咕

矩阵乘法

定义我不详细解释了,大概来说,是这个样子的:$c_{i, j} = \sum_{k = 1}^{m}{a_{i, k} * b_{k, j}}$。

矩阵乘法的前提是行列必须对应另一个矩阵的行列。矩阵乘法满足结合律, 分配率,但是不满足交换律。注意,不满足交换律。

举个例子吧,最经典的题

「ep8」求斐波那契数列的第$n$项,$n \leq 10^{18}$。

$f[i] = f[i - 1] +f[i - 2]$。所以,可以构造矩阵如下:

$$\begin{bmatrix}
1 & 1 \
1 & 0 \
\end{bmatrix}
\times
\begin{bmatrix}
f[n] \
f[n - 1]
\end{bmatrix}=
\begin{bmatrix}
f[n + 1] \
f[n]
\end{bmatrix}$$

我也不知道咋证,反正矩阵可以求快速幂。
于是

$$\begin{bmatrix}
1 & 1 \
1 & 0 \
\end{bmatrix}^n
\times
\begin{bmatrix}
1 \
1
\end{bmatrix}=
\begin{bmatrix}
f[n + 1] \
f[n]
\end{bmatrix}$$

「ep9」求斐波那契数列前$n$项和,$n \leq 10^{18}$。

其实是差不多的,构造如下:

$$\begin{bmatrix}
1 & 1 & 0 \
0 & 1 & 1 \
0 & 1 & 0
\end{bmatrix}
\times
\begin{bmatrix}
S[n] \
f[n + 1] \
f[n]
\end{bmatrix}=
\begin{bmatrix}
S[n + 1] \
f[n + 2] \
f[n + 1]
\end{bmatrix}$$

后面会有更多的题涉及矩阵,所以这个基础知识一定要搞好。
我们来看一个矩阵 + 概率的题。

矩阵中的图论建模

矩阵通常可以和图论中的邻接矩阵联系起来,看到图论的时候不妨往矩阵这里想一想。

「ep10」工作 (by ihopenot)

$Ambiguous$是居住在$byte$镇的量子居民,$byte$镇可以看成是$n$个点,$m$条单向边的联通图。每天清晨,$Ambiguous$都会以$P_i$的概率出现在$i$号节点,之后由于工作原因,$Ambiguous$每小时会有一定概率移动。具体而言,$Ambiguous$如果在$i$号节点并且存在一条编号为$j$的边从$i$出发,那么她就有$p_j$的概率走这条边。
可以保证从每个节点出发的边概率和不超过$1$,但不保证为$1$,如果$Ambiguous$没有走任何一条边,那么她就会留在当前节点。
今天清晨来临之前$Ambiguous$突然想知道,今天工作结束后自己在每个节点的概率是多少。
$n \leq 300, m \leq 100000, t \leq 10^{18}$。

这道题算是矩阵优化的基础题目,虽然原题暴力也可过,但是$t \leq 10^{18}$呢QAQ
矩阵这么构造,最开始的矩阵

$$\begin{bmatrix}
P_1 \
P_2 \
P_3 \
\cdots \
P_n
\end{bmatrix}$$

每次转移的矩阵是题中构造的邻接矩阵,对于这个邻接矩阵$pow(t)$之后乘上原矩阵,这个矩阵中的每一个位置表示到达某个点的概率。因为$c_{i, j} = \sum_{i = 1}^{k}{a_{i, k} \times b_{k, j}$。所以最后的某个点的点权是 所以入边的概率之和,没问题qwq。

「ep11」给出一个满足对角线均为正数的非负矩阵,判断这个矩阵是否有某一次方为全正数矩阵。$n \leq 1000$ (by ihopenot)

首先一看,莫名其妙…考场上写的矩阵快速幂验算,想苟50,结果只苟到了20…
下来听到有人说“不是图论建模么”,我心里一惊,然后反应过来了。
哇这道题吹爆!!!
首先,我们把$A$矩阵看成一个邻接矩阵,可以发现,转化为01矩阵之后是没有影响的。而矩阵的某一个位置$i, j$表示$i \rightarrow j$有一条边。矩阵中所有全为正数,表示这个图全连通,而矩阵乘法之后,我们考虑乘法的意义是什么。
写写就知道(其实我也是感性理解),乘出来的矩阵表示$i \rightarrow j$经过$k$条边就几种方案。(?
如果$a[i][j] = 0$,代表$i$不能到$j$。也就是$i, j$不处于一个$SCC$。
$SCC!$,启发我了…不处于一个$SCC$的点,无论怎么搞都不会处于一个$SCC$,所以,对最开始的图求一个$tarjan$,看全部是否都处于同一个联通快中。

// 贼棒的图论建模
// by kririae
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
inline char gc()
{
  static char buf[1 << 18], *fs, *ft;
  return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read()
{
  register int k = 0, f = 1;
  register char c = gc();
  for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
  for (; isdigit(c); c = gc()) k = (k << 3) + (k << 1) + (c - '0');
  return k * f;
}
}

namespace Life
{
const int maxn = 1005;

int n, t, a[maxn][maxn], dfn[maxn], low[maxn], cnt, tot;
stack<int> s;
bitset<maxn> vis;

inline void tarjan(int x)
{
  dfn[x] = low[x] = ++cnt;
  s.push(x), vis[x] = 1;
  for (int i = 1; i <= n; ++i)
  {
    if(!a[x][i]) continue;
    if(!dfn[i])
    {
      tarjan(i);
      low[x] = min(low[x], low[i]);
    } else if(vis[i]) low[x] = min(low[x], dfn[i]);
  }
  if(low[x] == dfn[x])
  {
    int curr; ++tot;
    do {
      curr = s.top(); s.pop(); vis[curr] = 0;
    } while(curr != x);
  }
}
inline void solve()
{
  using namespace IO;
  t = read();
  while(t--)
  {
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(a, 0, sizeof(a));
    while(!s.empty()) s.pop();
    vis.reset(); cnt = 0; tot = 0;
    n = read();
    int flag = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        a[i][j] = read();
    for (int i = 1; i <= n; ++i)
          if(!dfn[i]) tarjan(i);
    if(tot == 1) puts("YES");
    else puts("NO");
  }
}
}

int main()
{
  return Life::solve(), 0;
}

组合计数

加法原理和乘法原理

可以简单想想成一张图,如果图是这样的:

$1 \rightarrow 2, 1 \rightarrow 2, 1 \rightarrow 2 \cdots$

那么$1 \rightarrow 2$的路径数就是所有边的总和,这就是加法原理。

如果图是这样的

$1 \rightarrow 2, 1 \rightarrow 2, 1 \rightarrow 2 \cdots$

$2 \rightarrow 3, 2 \rightarrow 3, 2 \rightarrow 3 \cdots$

$3 \rightarrow 4, 3 \rightarrow 4, 3 \rightarrow 4 \cdots$

问$1 \rightarrow 4$的路径和,就是每个关键点的路径条数的乘积,这就是乘法原理。

排列和组合

$\binom{n}{m} \Rightarrow \binom{n}{m}$。

写作$P_n^{m}$,表示从$n$个物品中取出$m$个排成一排,产生的不同的排列的数量为。$P_n^{m} = \frac{n!}{(n - m)!}$,可以这么推导:第一次选,有$n$个,第二次选,有$n - 1$个,第三次选…以此类推,最后可以选的有$n - m +1$个。

写作$\binom{n}{m}$,表示从$n$个物品中选取$m$个组成集合,产生的不同的集合的数量为。$\binom{n}{m} = \frac{n!}{m!(n - m)!}$。这么考虑,对于一个长度为$m$的序列,排列方式有$P_m^{m} = m!$。总数量除以排列数就是组合数。

组合数的性质

  • $\binom{n}{m} = \binom{n}{n - m}$。$\binom{n}{m} = \frac{n!}{(n - m)!}$,$\binom{n}{n - m} = \frac{n!}{(n - m)!}$。当然,对于组合数来说,硬核证明是不好的。从$n$个钟选取$m$个,剩下的组成一个补集。补集的取值情况和原集合是一一对应的。
  • $\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$。硬核证明免了,谁都会带公式。我们考虑第$n$号元素选和不选,如果选了,剩下的情况是$\binom{n - 1}{m - 1}$,如果不选,剩下的情况是$\binom{n}{m - 1}$。
  • $\sum_{i = 0}{n}{\binom{n}{i}} = 2^n$。硬核证明也免了,谁都会带公式。公式等同于对$n$个数中选取任意多个数,也就是每个数有取或者不取,也就是$2^n$种情况。

额…之后统一写法…

组合数的求解

  • 利用递推式求解,性质2。复杂度$O(n^2)$。
  • 利用定义求解,复杂度$O(n\log{n})$。其实可以用逆元递推到$O(n)$。
    #define ll long long
    #include <bits/stdc++.h>
    

using namespace std;

const int maxn = 10005;
const int mod = 1e9 + 7;

int fac[maxn];
template
inline void exgcd(T &x, T &y, T a, T b)
{
if(b) exgcd(y, x, b, a % b), y -= (a / b) * x;
else x = 1, y = 0;
}
template
inline T inv(T a, T x = 0, T y = 0)
{
// ax \equiv 1 \pmod {p} -> ax = pk + 1 -> ax - pk = 1
exgcd(x, y, a, mod);
return (x % mod + mod) % mod;
}

inline void init()
{
fac[0] = 1;
for (int i = 1; i < maxn; ++i)
fac[i] = (1ll * fac[i - 1] * i) % mod;
}

inline ll C(int n, int m)
{
return ((((1ll * inv(fac[m]) * fac[n]) % mod) * inv(fac[n - m])) % mod);
}

int main()
{
init();
// code…
}


#### 二项式定理
$$
(a + b)^n = \sum_{k = 0}^{n}{\binom{n}{k}a^kb^{n - k}}
$$
证明我不会。

#### $Lucas$定理

若$p$是质数,则有$\binom{n}{m} \equiv \binom{n \ mod \ p}{m \ mod \ p} \cdot \binom{\frac{n}{p}}{\frac{m}{p}}$。证明我也不会,貌似需要生成函数。

##### 给定$n, g$,求$g^{\sum_{d | n}{\binom{n}{d}}} \mod{99911659}$。

因为$99911659$是质数,$ex$欧拉定理可知,费马小定理也行,$a^b \equiv a^{b \mod{\varphi(n)}} \mod{n}$,所以$g^{\sum_{d | n}{\binom{n}{d}}} \mod{99911659} = g^{\sum_{d | n}{\binom{n}{d}} \mod{99911658}} \mod{99911659}$。目前的问题就是快速求$\sum_{d | n}{\binom{n}{d}} \mod{99911658}$。$n \leq 10^9$,所以$n$的约数个数不超过$2\sqrt{n}$。也就是说跑的过。那么问题来了,$Lucas$定理的适用范围仅仅是质数,怎么办怎么办(捧读)。分解$9911658 = 2 \cdot 3 \cdot 4679 \cdot 35617$。对于几个分解后的质数,我们带入中国剩余定理,求出正确的$\binom{n}{d} \mod{9911658}$。代码如下~
```cpp
#define ll long long
#include <bits/stdc++.h>

using namespace std;

namespace BZOJ1951
{
const int mod = 999911658;
const int prm[4] = {2, 3, 4679, 35617};

inline ll fpow(ll a, ll p, ll mod)
{
  ll ans = 1;
  for (; p; p >>= 1) {
    if(p & 1) ans = (a * ans) % mod;
    a = (a * a) % mod;
  } return ans;
}
int g, n, factor[40000], cnt, fact[40000], a[4];
inline void init()
{
  for (int i = 1; i * i <= n; ++i)
    if(n % i == 0) {
      factor[++cnt] = i;
      if(i != n / i) factor[++cnt] = n / i;
    }
}
inline int C(int n, int m, int p)
{
  if(m > n) return 0;
  return fact[n] * fpow(fact[m] * fact[n - m], p - 2, p) % p;
}
inline int lucas(int n, int m, int p)
{
  if(m == 0) return 1;
  return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
inline int work(int p)
{
  memset(fact, 0, sizeof(fact));
  fact[0] = 1;
  for (int i = 1; i <= p; ++i)
    fact[i] = fact[i - 1] * i % p;
  ll ans = 0;
  for (int i = 1; i <= cnt; ++i)
    ans = (ans + lucas(n, factor[i], p)) % p;
  return ans;
}
inline int CRT()
{
  ll ans = 0, M = 999911658;
  for (int i = 0; i < 4; ++i)
    ans = (ans + (a[i] * (M / prm[i]) % mod) * fpow(M / prm[i], prm[i] - 2, prm[i])) % mod;
  return ans;
}
inline void solve()
{
  cin >> n >> g;
  if(g == 999911659) return puts("0"), void();
  init();
  for (int i = 0; i < 4; ++i) a[i] = work(prm[i]);
  printf("%lld\n", fpow(g, CRT(), 999911659));
}
}

int main()
{
  return BZOJ1951::solve(), 0;
}

$Catalan$数列

定义如下:$Cat(n) = \frac{\binom{2n}{n}}{n +1}$。

有以下问题:

  • $n$个左括号和右括号组成的合法序列的个数。
  • $[1, n]$形成的合法出栈序列的个数。
  • 在平面直角坐标系上,不越过$x - y = 0$一条直线,每次只能向上或者向右走,的路线的条数。

$Catalan$数列通常采用朴素的组合数求法,也有递推版本的。

组合数学 ver2.0

排列与组合。

$\frac{n!}{(n - m)!}$。$n!$是全排列的数量,$(n - m)!$是除去$m$个以外的排列顺序个数。除一下就好了。

$\frac{n!}{m!(n - m)!}$。总数除以算重的。圆上的排列问题。$\frac{n!}{(n - m)!n}$ 。

具体求法。逆元预处理,阶乘预处理。

$\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$的杨辉三角理解方式。

HDU4135

求$\sum_{i = 1}^{n}{[gcd(i, x) = 1]}$。$n \leq 10^9$。

对于一个固定的$x$,我们要求$i$的个数。但是我们发现,求互质没法下手,我们尝试用不互质去解决。$gcd(x, i) != 1$的条件,$i$是$x$的某个因数。所以我们枚举$x$的所有质因数$p_i$,满足条件的$p_i \cdot k \leq n$就是$x$的个数。但是,会发现,我们算重了很多情况,于是进行容斥。进行一次$dfs$,因为$n \leq 10^9$的条件下,$p_i$的个数不超过10,对于每一个,容斥$\frac{n}{i}$,最后用$n$减去该答案。

???

给出$n \times m$的矩阵,$q$个询问,每次询问$(x_1, y_1) \rightarrow (x_2, y_2)$的路径个数。$n, m \leq 1000$,$q \leq 10^5$。

$dp$的解法不用说了,小学难度。

问题是让用组合数。引出隔板法,隔板法是这么一个东西:

将$k$个物品用板子分成$m$份。能够分的情况个数是:$\binom{k + m - 1}{m - 1}$。

将$k$个物品分成$m$份,需要添加$m - 1$个板子,我们可以把板子看成别的物品,总和也有就$k + m - 1$个物品,从中选出$m - 1$物品,也就有$\binom{k + m - 1}{m - 1}$种情况。

再转回原题目,首先,假如说是从$(1, 1) \rightarrow (n, m)$,我们考虑把路径分成横着的$n$份,总共要下降$m$次,也就是说,把$m$次下降分到$n$份中,也就是隔板法的经典问题,答案是$\binom{n + m - 1}{n - 1}$。(写反了,懒得改,将就看看吧。

HDU6397

给出$n, m, k$,从$[0, n - 1]$中选取$m$个数,使得合为$k$,问方案数,数字可重复。$n, m, k \leq 10^5$

首先考虑简化版本的问题,$k \leq n - 1$。我在$k$个$1$中放隔板,和一定为$k$,个数是$\binom{k + m - 1}{m - 1}$,那么问题来了,$k > n - 1$咋办。我们将每一个数字表示为$a_1x + b$。我们将情况用$\sum{a_i}$分类,$\sum{a_i} = [1, \frac{k}{n}]$。假如说忽略$n$,我们直接用隔板法计算所得结果是$\sum{a_i} \in [1, \frac{k}{n}]$的情况数之和,因为隔板法隔出了所有的情况,这些情况等于分类后的全集。我们考虑从$k$中剔除$i$个$n$,对剩余的进行隔板法,然后放回这$i$个$n$,放回的情况个数是$\binom{m}{i}$。这时,我们的计算结果是忽略掉了$\sum{a_j} \leq i$的,利用这个性质进行容斥即可得答案。

生成函数

首先吧,定义如下:

对于序列$a_0, a_1, a_2, a_3, a_4 \cdots a_n$,$g(x) = \sum_{i = 0}^{n}{a_ix^i}$,称$g(x)$是序列的生成函数。

你有$1, 3, 5$面额的硬币,每种数量无限,总共用$k$个,能够组合出多少种面额。

考虑多项式的乘法,用$x^1$表示用$1$元的硬币,用$x^3$表示用$3$元的,以此类推。
$$
(x^1 + x^3 + x^5)^k
$$
用幂表示面额数,最后求有多少种幂,在这里忽略系数就是多项式的用处。

HDU1028

求出和为$n$的数的组合的个数,$n \leq 120$

$(1 + x + x^2 + x^3 + \cdots) \cdot (1 + x^2 + x^4 + \cdots) \cdots$.最后统计$x^n$的系数。

POJ 1942 1850 1019 HDU 1028 1398 1085 2082 1709 2065

数学期望

因为明天要考期望,紧急添加…

妈耶我期望不要爆零。

对于样本空间$A$,随机事件$a$发生的概率是$P(a)$,$P(\sum{a}) = 1$,$P(a) \in [0, 1]$。对于互斥事件$a_i, a_j$,$P(a_i) +P(a_j) = P(a_i \cup a_j)$。

对于$X$的取值$x_i, x_j \cdots$,取到某一个值的概率是$p_i$,则取到这个值得数学期望是$E(x_ip_i)$d,对于随机变量$X$的期望是$\sum{x_ip_i}$。假如说掷骰子吧,取值有$[1, 6]$,而掷到每一个数值的概率是$\frac{1}{6}$,则掷一个骰子的值的数学期望是$\frac{1}{6} \cdot 1 + \frac{1}{6} \cdot 2 + \cdots + \frac{1}{6} \cdot 6 = \frac{21}{6}$。

光说不练假把式。

「ep8」某个星球有$n$天,抽取$k$个人,问至少两个人生日在同一天的概率是。$1 \leq k \leq n \leq 10^{6}$。

这种,一般都要转换问题,转换为“所有人生日都不同”的问题。第一天,某个人可以选择$\frac{n}{n}$天,第二个人可以选择的是$\frac{n - 1}{n}$,第$k$个人可以选择的是$\frac{n - k + 1}{n}$,所以答案就是$\prod_{i = 0}^{k - 1}{\frac{n - i}{n}}$。可以线性计算。

「ep9」毛玉问题,有$K$只毛玉,每只生存一天就会死亡,每只毛玉在死之前有可能生下一些毛玉,生$i$个毛玉的概率是$pi$,问$m$天后所有的毛玉都死亡的概率是多少? 所有数据$\leq 1000$。($UVA11021$

代码如下…解释的话…会很复杂。好吧…我承认这道题搞了我俩天。
设$f[i]$表示,对于一直毛玉,其子孙后代在$i$天“内”死亡的概率是。假设这一天死了这一只小毛玉死了,概率是$p_0$,如果生下一只的话,生下的小毛玉已经被限制了生命,在$i - 1$天内死的概率是$f[i - 1]$,其中$i - 1$的意思是它的寿命是$i - 1$。对于生下的所有小毛玉,可以独立考虑,则全部死光的概率需要$f[m]^k$。这道题的关键是搞清楚,$f[i]$到底是啥意思QAQ就是这玩意儿害了我俩天。

// by kririae
#define R register
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;

int t, n, k, m;
double p[maxn], f[maxn];

inline double fpow(R double a, R int p)
{
  double ans = 1;
  for (; p; p >>= 1)
  {
    if(p & 1) ans = a * ans;
    a = a * a;
  }
  return ans;
}

int main()
{
  scanf("%d", &t);
  for (int qwq = 1; qwq <= t; ++qwq)
  {
    memset(f, 0, sizeof(f));
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 0; i < n; ++i) scanf("%lf", &p[i]);
    f[1] = p[0];
    for (R int i = 2; i <= m; ++i)
      for (R int j = 0; j < n; ++j)
        f[i] += p[j] * fpow(f[i - 1], j);
    printf("Case #%d: %.7lf\n", qwq, fpow(f[m], k));
  }
}

「ep10」咕咕咕

「ep11」咕咕咕

「ep12」咕咕咕

「ep13」咕咕咕

「ep14」Va-11 Hall-a (by ihopenot)

「题目描述」

$Jill$是在$Vallhalla$工作的调酒师。为客人送上美味的饮料是她的工作内容。但$Jill$是个有创造力和上进心的女孩,她并不满足于仅为客人调制菜单上的饮料,她想自己去创造属于自己的饮料。虽说如此,她并不知道怎么去创造一种受客人欢迎的饮料,于是她想出了一个绝妙的办法。$Jill$将$n$瓶酒摆成一列,每瓶酒初始评价值都为$1$,然后有$m$次操作。每次操作$Jill$会在$[l,r]$内的酒中随机选择任意瓶每瓶加入一个评价值随机(不一定相同)的配料,并重复这个操作$k_i$次。由于原料和配料会发生剧烈的化学反应,所以混合之后评价值并不是相加 那么简单。据$Jill$观察,一瓶评价值为$a$酒在加入评价值为整数$b(0 \leq b < c)$,的配料后评价值会变为$a\cdot b \ mod \ c$。现在$Jill$想知道她最终调制出的酒的评价值的和期望是多少。

一句话题意:给你一个初始全为$1$的长度为$n$的序列,$m$次操作,每次操作重复$ki$次,对于$[l,r]$间的随机一些数$a$,再对每个数选择一个随机整数$b(0 \leq b < c)$,将这些数变成$a\cdot b \ mod \ c$。问最终所有数的和期望是多少。 为了方便保证精度,你需要输出答案对$10^9+7$取模后的结果。 提示:如果答案是$\frac{a}{b}$的形式,那么你需要输出$a \cdot b^{-1} \ mod \ (10^9 + 7)$的结果。由于费马小定理,你只需输出$a \cdot b^{10^9 + 5} \ mod \ (10^9 + 7)$就可以了。

「输入格式」

第一行三个正整数$n, m, c$接下来每行三个数$l_i, r_i, k_i$表示操作的区间和重复次数。

「输出格式」

一行一个整数表示答案对$10^9+7$取模后的整数。

「样例输入」

3 1 3 1 2 1

「样例输出」

500000007

「数据规模及约定」

对于$30%$的数据$n=10, m \leq 10, k_i \leq 10, c \leq 5$
对于$100%$的数据$n \leq 100, m \leq 1e6, k_i \leq 100, c \leq 50$

题解

由于期望的可加性,我们可以这么处理这道题。对于每个数,我们求出它最后为某一个数的期望,然后求和。因为它最后的值一定属于$[0, c)$。所以我们建立矩阵:
$$
\begin{bmatrix}
p_0 \
p_1 \
p_2 \
\cdots \
p_{c - 1} \
\end{bmatrix}
$$
$p_i$表示最后值为$i$的概率是。当然,现在的矩阵是初始的,我们考虑如何对这个矩阵进行转移。即转移到某一次操作后,某一个数变换成某一个数的概率是。转移矩阵的第$i$行第$j$列定义为,数值$i$变换到数值$j$的概率是。特别的,这个矩阵有第$0$行第$0$列。对于一次$[L, R]$的操作,选取到某个数的概率是$\frac{1}{2}$。而选取到这个数之后,进行的操作可能是乘上$[0, c)$中的任意一个数,乘这个数的概率就是$\frac{1}{c \cdot 2}$。所以我们在某个数$x$乘上$[0, c)$后的数$y$,$x \rightarrow y$之间的边加上概率$\frac{1}{c \cdot 2}$。

对于这道题的矩阵乘法,我们这么考虑:$a_{1, 2}$的意思是经过一次操作后,$1$变到$2$的概率,则在乘上原矩阵第二列之后,最后的变为$2$的概率自然加上了某个值,这个值是$1$变为$2$的概率。

按照套路,这个时候该进行矩阵快速幂了。但是,如果直接进行矩阵快速幂的话…我们看看复杂度:$O(nc^3log{km})$,$2.5 \cdot 10^8$有点玄乎啊。这个时候,考虑优化矩阵乘法。我们$n \times n$的矩阵乘法的复杂度是$O(n^3)$,如果是$n \times n$和$n \times 1$的矩阵乘法,不就是$O(n^2)$了。我们预处理出转移矩阵的$2^k$次方,复杂度是$O(n^3log{k})$,可以接受,然后,用预处理出的信息和$n \times 1$的矩阵一一结合,得出的就是最后的矩阵,然后对所有求和,得出期望。

$std$代码如下

#include<bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define LL long long

int n,m,c,ans;
int num[105];

struct Matrix{
    int x[55][55];
    Matrix operator * (const Matrix &b) const {
        Matrix ret;
        memset(ret.x,0,sizeof(ret.x));
        for(int i=0;i<c;i++)
            for(int j=0;j<c;j++)
                for(int k=0;k<c;k++)
                    ret.x[i][k]=(ret.x[i][k]+(LL) x[i][j]*b.x[j][k])%MOD;
        return ret;
    }
}pw[35],st;
int now[55],t[55];

void Merge(int k) {
    memset(t,0,sizeof(t));
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            t[i]=(t[i]+(LL) now[j]*pw[k].x[i][j])%MOD;
    for(int i=0;i<c;i++) now[i]=t[i];
}

int fpow(int a,int b) {
    LL t=a,ret=1;
    while(b) {
        if(b&1) ret=ret*t%MOD;
        b>>=1;t=t*t%MOD;
    }
    return ret;
}

int main() {
    freopen("bar.in","r",stdin);
    freopen("bar.out","w",stdout);

    scanf("%d%d%d",&n,&m,&c);
    for(int l,r,k,i=1;i<=m;i++) {
        scanf("%d%d%d",&l,&r,&k);
        num[r+1]-=k;num[l]+=k;
    }
    for(int i=1;i<=n;i++) num[i]+=num[i-1];
    LL rev_2=fpow(2,MOD-2),rev_c=fpow(c,MOD-2);
    for(int to,i=0;i<c;i++) {
        for(int j=0;j<c;j++) {
            to=i*j%c;
            st.x[i][to]=(st.x[i][to]+rev_2*rev_c)%MOD;
        }
        st.x[i][i]=(st.x[i][i]+rev_2)%MOD;
    }
    pw[0]=st;
    for(int i=1;i<=30;i++) pw[i]=pw[i-1]*pw[i-1];
    for(int i=1;i<=n;i++) {
        memset(now,0,sizeof(now));
        now[1]=1;
        for(int j=0;j<=30;j++) if(num[i]>>j&1) Merge(j);
        for(int j=0;j<c;j++)
            ans=(ans+(LL)now[j]*j)%MOD;
    }
    printf("%d\n",ans);
    return 0;
}

概率$dp$

$$P(B) = \sum{P(A)P(B | A)}$$

$B$事件是及格,$A$事件是$100$分以上,所以说$B$事件发生的概率是$A$发生的概率乘$A$发生的前提下$B$发生的概率。

$P(B | A) = \frac{P(A, B)}{P(A)}$。$A, B$不是独立事件,所以不能直接相乘。可以这么$A$发生的前提下$B$发生的概率。

期望$dp$

$E(A) = \sum{P(a_i) \times a_i} = \sum{E(a_i)}$;

经常会出现$a_i$的值一定的时候,也就是贡献一定的时候,有时会转化为求$P(a_i)$,$a_i$不同的时候,就需要单独计算了。

HDU3853

POJ2151

$f[i][j][k]$,选到第$i$个队伍,从前$j$个中选$k$个,所有合法情况的概率之和为$f[i][j][k]$。

所有队伍至少做出一个的概率就是$1 - f[n][m][0]$。所有队伍都做出$n$以下的概率是$f[i][m][n]$的前缀和。

POJ3071

二进制性质优化概率dp

对于所有点建树,树状数组式建树,对于$i$层,编号从$0$开始,可以发现性质,当前>> 1之后是起父亲节点,当前>> 1 xor 1是其父亲节点的右节点。然后进行普通的转移。对于第$i$层,先把某个值右移$i - 1$层,然后异或$1$,相等,能打。什么骚操作。。。

CF148D

$f[i][j]$表示剩余$i$只白鼠,$j$只黑鼠,$A$先手,胜利的概率。

$f[i][0] = 1$,因为$A$先手,如果没有黑鼠就赢了。

$f[0][i] = 0$,没有白鼠$B$胜利。

在这一场胜利有三种情况,这一次抓到白鼠,上一次$B$抓到黑鼠,跑出来只白鼠、这一次抓到白鼠,上一次$B$抓到黑鼠,跑出来只黑鼠。输出$f[w][b]$。

POJ3744

先考虑数值范围很小的情况,$a_i \leq 1000$,假如说$i$位置有雷,到达$i - 1$位置的概率乘以转移两步的概率就是到达$i + 1$位置的概率,然后跳过$i$位置的计算,中间分开的部分用矩阵快速幂优化一下。

BZOJ4318

$f[i][j]$表示到了$i$位置,连续$1$的长度为$j$,的期望分数。$i + 1$,$p_i$的概率是$1$,$1 - p_i$的概率是0.$f[i + 1][j + 1]$的概率是$p_i$,转移到$f[i + 1][0]$的概率是$1 - p_i$。第二种的权值是$0$,前者的权值是$(j + 1)^3$。不过。。。我貌似搞忘看数据范围了,$n \leq 10^6$。

所以说,$f[i]$表示到$i$位置的期望分数,$g[i]$表示到$i$的期望长度。

TODO

HDU4405

本题目的大体意思是有n个格子,掷色子的掷出的数目就是你一次到移动格数。其中有m个飞行通道可以让你直接从第xi格飞到第yi格。问你走到终点的期望是多少。

HDU4336

有N种卡片,每一袋零食里面最多有一张卡片,给出一袋零食里面每种卡片的概率,问平均要买多少袋零食能收集到所有的卡片。

BZOJ3143

首先求出每个点到达的期望次数,$x_i​$,$x_i = \sum{x_j \cdot \frac{1}{d[j]}$。列出系数矩阵,$x_n = 0$。高斯消元解出每个点到达的期望次数。然后每条边到达的期望次数是$w_k = x_i \cdot \frac{1}{d[i]} + x_j \cdot \frac{1}{d[j]}$。对期望次数从大到小排序,然后依次分配权值。

泰勒展开

非线性的函数 $\rightarrow$ 函数多项式。

$f(x) = f(x_0) + f^{‘}(x_0)(x - x_0) + frac{f^{‘’}(x_0)(x - x_0)^2}{2!} \cdots$。

指数型母函数

假如说有$8$个元素,数值可重复。从中取出$k$个元素,求排列数。

$1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} \cdots$。进行排列计数。$\frac{x^i}{i!}$表示某物品选取了$i$次,排列个数。

除以阶乘的原因是排除自身重复排列的影响。

POJ3734

$e^x$通过在$0$处的泰勒展开,其实就是指数型母函数的标准形式。

$e^{-x}$在$0$处泰勒展开,和指数型母函数进行加法或减法运算,可以得出奇数项,偶数项的和。备注:$f^{n \cdot ‘}(x) = (-1)^n \cdot e^-x$。

SG函数 $Sprague - Grundy$

在DAG上进行。

先手必败态。非先手必败,都是先手必胜!

假设是$NIM$游戏,对于每一堆有$a_i$个物品,则当前堆的$SG(i) = a_i$。结论:对于任意一个$SG$异或值为0的状态,通过一步只能变为$SG$异或值非零。对于任意一个$SG$异或和非零的状态,一定能一步转移到$SG$异或和为0的状态。

阶梯上的博弈问题。给出$n$级阶梯,每次可以把上级阶梯的石子移到下一层。最后当石子全在1时无法移动。$A$先手,问谁胜利。$n \leq 10^6$。加入说$A$将一堆石子从奇数层移到了偶数层,我们可以再进行一次移动使得局面不变,依然$A$先手。假如说我们将偶数层移动到奇数层,就等同于把一堆石子拿走了,因为奇数层的都可以xjb处理。对于所有偶数层的进行$NIM$,得出答案。

LUOGU2575

首先考虑暴力求解,状压枚举,不说了。

问题在于这道题tmd居然还有阶梯博弈的抽象。。。

我们知道,我们每次移走一个棋子的时候,空格的个数是不会改变的,我们把每个0看成一个阶梯的分界线,假如说把$i \rightarrow j$,$j$的0没了,$i$多出一个$0$,也就是阶梯的分界线变为了$i$,也就是说,把$i$分界线对应阶梯的一部分棋子放到$j$对应阶梯上了。对于每一行,抽出偶数位置,进行$NIM$,作为当前行的$SG$,然后对于每一行$SG$,可以解决问题。

骚操作补充

十进制快速幂

首先,快速幂要求一下东东$a^b \ mod \ p$。但是,直接跑太慢啦,于是我们队$b$进行了二进制的拆分,拆分成了$2^0 + 2^j \cdots$,于是变成了$a^{2^0 + …}$,化为$a^{2^{0}} \cdot a^{2^{j}} \cdots$。注意到只有$\log{n}$项,所以复杂度是$O(\log{n})$。但是,细心的人就会发现,关于$b$,还有一个拆分方法。$while(b)\ a[++curr] = b % 10, b /= 10;$。这样,拆分成了$b = \sum_{i = 1}^{n}{c_i \cdot 10^{i - 1}}$。$a^b = a^{c_i \cdot 10^{i - 1}} \cdots$。因为带上了$c_i$,实现上还会有一些小问题,这些一会儿解决~这样,我们就可以写出十进制的快速幂!更快!更重要的是,可以部分代替高精度,不信请看。

求$a^b \ mod \ p$,$b \leq 10^{10000}$。

大概,只能用数组来存了,不过无所谓。看代码:

const int N = 10005;
char b[N];
inline ll fpow2(ll a, ll p, ll mod)
{
  ll ans = 1;
  for (; p; p >>= 1) {
    if(p & 1) (ans *= a) %= mod;
    (a *= a) %= mod;
  } return ans;
}
inline ll fpow10(ll a, char p[], ll mod)
{
  ll ans = 1;
  int l = strlen(p + 1);
  for (int i = l; i >= 1; --i) {
    (ans *= fpow2(a, p[i] - '0', mod)) %= mod;
    a = fpow2(a, 10, mod);
  } return ans;
}

一些题目备选

概率:BZOJ2318,BZOJ4720,BZOJ2720,BZOJ3720,收集邮票

各种:NOI2010能量采集

在 daily blog 里加上一篇数论笔记也能体现我真的不是文科生吧