数论

发布于 2018-07-30  66 次阅读


数论

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

krr数论全笔记

基础知识

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

唯一分解定理

每个数,都可以唯一被分解成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,记为ba整除,a整除于b。写作a | b

绕一绕的话...n = km,读作m整除nnm整除,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 Nb是质数,那么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)} + nrr为欧拉常数,约等于0.5772156649,所以遇到形如\sum_{i = 1}^{n}{\frac{n}{i}}的算式,在时间复杂度中通常记作n\log{n},或n\ln{n}。我习惯前者。调和级数通常用作时间复杂度的证明。

约数

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

定义N

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

可以简单发现,p_iN的约数,也就是说,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的正整数约数集合是试除法,这里不再赘述...
    还有一个求法。
  • 对于数字dd一定是d \cdot k的约数。这样筛下来,复杂度是O(\sum_{i = 1}^{n}{\frac{n}{i}})。利用调和级数,O(n\log{n})。比O(n\sqrt{n})要好得多。

余数

a \; mod \; b = c,称ca除以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 \; pn \leq 10^{12}, p \leq 10^9

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

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

对于d \leq nd的倍数的个数为\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的问题。

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

最大公约数和最小公倍数

定义:若存在dd | ad | bd中最大的一个就是gcd(a, b)(a, b)的最大公约数。若存在a | mb | mm取值最小的一个被称作lcm(a, b)(a, b)的最小公倍数。

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

最大公约数性质如下,gcd(a, b) = gcd(b, a)gcd(a, 0) = agcd(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 | ad | 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_1x的个数,a, b \leq 10^9

朴素算法如下,我们知道,x | b_1, b0 | b1a_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})}
证明:

pn的质因子,则p | n,而kp \leq n的所有kp都不与n互质。而kp\lfloor \frac{n}{p} \rfloor个,而qn质因子,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) = 1a的和。由九章算术,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,分子为aa < b的既约分数,假如说固定b的取值,那么a的取值有\varphi(b)种。关于这道题,我们考虑所有的\frac{i}{n}, i \in [1, n],将其约分,对于约分后的分数\frac{a}{b},一定有gcd(a, b) = 1, b | n, a | ia < 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) = 124 |12。然后,之后会在拓欧降幂处提到。

「ep6」求a^{b^{b^{b...}}} \ mod \ (10^{9} + 7)bn个。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时有解,进而推导bmod \ 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_iM_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单身狗定理(大雾

相比CRTEXCRT有个区别,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,求aa中第一次出现的下标是?

对于线性基的组合出来的集合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<typename T>
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<typename T>
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}。代码如下~

#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的条件,ix的某个因数。所以我们枚举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 1000q \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。我在k1中放隔板,和一定为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中剔除in,对剩余的进行隔板法,然后放回这in,放回的情况个数是\binom{m}{i}。这时,我们的计算结果是忽略掉了\sum{a_j} \leq i的,利用这个性质进行容斥即可得答案。

生成函数

首先吧,定义如下:

对于序列a_0, a_1, a_2, a_3, a_4 \cdots a_ng(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}) = 1P(a) \in [0, 1]。对于互斥事件a_i, a_jP(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是个有创造力和上进心的女孩,她并不满足于仅为客人调制菜单上的饮料,她想自己去创造属于自己的饮料。虽说如此,她并不知道怎么去创造一种受客人欢迎的饮料,于是她想出了一个绝妙的办法。Jilln瓶酒摆成一列,每瓶酒初始评价值都为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)后的数yx \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 nn \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 + 1p_i的概率是11 - 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 jj的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 \ pb \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 里加上一篇数论笔记也能体现我真的不是文科生吧


君子以自强不息。