历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

算法提高课第五章笔记2

作者：

左手影视 , 2020-02-23 15:31:41 , 所有人可见 , 阅读 2096

5

2

Acwing1290越狱

已知有n个房间，m种宗教，每个房间只关一名犯人，每个人的信仰自由，如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。要求有多少种状态可能发生越狱，答案对100003取余。

可以看出这个题目是组合数学的模型。

（1）直白的从题面来考虑，相邻两个房间宗教相同就会发生越狱，为了求方案数，我们先确定是哪几个宗教相同，有m种可能。再确定哪几个房间发生相同的情况，可以只有两间房间相同，也可以是所有房间两两配对相同，想到这里我们会发现情况太多了，很难列举完全。

（2）从直接求相邻房间宗教相同的情况入手走不通了，不妨从反面来考虑，会发现其实这题隐藏了容斥原理

在里面：发生越狱的情况 = 方案总数 - 不发生越狱的情况。不发生越狱的情况就是相邻房间信仰不同，画一下图就可以发现是一个简单的排列组合

房间：1 2 3 4 n

m * (m-1) * ( m - 1) * (m - 1) ..............

第一个房间可以有m种信仰，第二间不能与第一间相同，有m-1种信仰，第3间不能与第2间相同，但是可以与第1间相同，所以也是m-1种。

结论：方案总数： n个犯人每人都有m种信仰，等于n ^ m

不发生越狱的情况 :m * (m - 1) ^ (n - 1) （一共有n - 1个房间的信仰为m - 1 ,第一间为m）

因为n , m很大，需要用快速幂。

细节：在计算答案的时候可能会出现负数的情况，因为c++的负数取模机制的原因，所以需要把答案加上一个mod 再取一次模。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 100003;  

int qmi(int a ,ll k){

    int res = 1;
    while(k){

        if(k & 1) res = (ll)res * a % mod;
        a = (ll)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main(){

    int m;
    ll n;
    cin >> m >> n;

    cout << (qmi(m , n) - (ll)m * qmi(m - 1 , n - 1) % mod + mod) % mod << endl;

    return 0;
}

Acwing1291 轻拍牛头

题目很长，只看最后一句就可以，共有 N 个整数 A1,A2,…,AN，对于每一个数 Ai，求其他的数中有多少个是它的约数。

题目模型:求约数个数

（1）首先考虑最直接的，n方遍历这个数组，但是发现1e5 ，n方会T ，否决

（2）从直接求情况入手走不通了，习惯性地来思考一下反面，我们无法求一个数的约数个数，但是求它的倍数十分好求，记录一个数出现的次数，它每出现一次，就会给这个数组里它的倍数增加一个约数个数，那么我们只要枚举每个数的倍数，将它出现的次数加到它的倍数上去即可。

结论：数组记录一个数出现的次数，枚举从1到1e6每个数的倍数，将它出现的次数加到它的倍数上去。

细节：求的是除了它本身以外约数的个数，记得减1

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n , q[N] , cnt[N] , ans[N];

int main(){

    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d" , &q[i]) ,cnt[q[i]] ++ ;

    for(int i = 1; i < N; i ++)
        for(int j = i; j < N; j += i)
            ans[j] += cnt[i];

    for(int i = 0; i < n; i ++) printf("%d\n" , ans[q[i]] - 1);

    return 0;
}

Acwing1294 樱花

给定一个整数 n，求有多少正整数数对 (x,y) 满足 1 / x + 1 / y = 1 / n!

题目模型：数学推导 + 求约数个数 + 线性筛素数

（1）题目只有一个公式，让我们求出满足条件的x ， y ,因为n为已知量，

只要正整数x确定了，y也必然有确定的正整数的值，考虑将y用x表示出来，

这样应该能看出x和y的关系。

数学推导开始：

首先通分：

x + y      1
_____  = _____   
x * y      n!

两边乘开

（x + y） * n! = x * y

将y用含有x的式子表示出来

    x * n!  
y = ______
    x - n!

因为n是常数，可以分离常数得到

    (x - n! + n !) * n!                 (n!）^ 2
y = __________________         y = n! + _______
         x - n!                          x - n!

到了这一步可以发现，如果y是正整数，那么对应的（x - n! ) 一定要能整除 n! ^ 2 ,换句话说满足条件的x的个数就是n! ^ 2 的约数个数。

结论：至此已经整理出来了题目的真正目的，求 n！^ 2 的约数个数。

复习一下求约数个数的公式：

n! = p1 ^ c1 + p2 ^ c2 + p3 ^ c3 ..... + pk ^ ck(其中P1 ----- Pk为n！的质因子 ，
    c1 -----ck为对应质因子的次数)
    n!的约数个数 = （c1 + 1) * (c2 + 1) * (c3 + 1)...... * （ck + 1）

那么：

n! ^ 2 = p1 ^ 2c1 + p2 ^ 2c2 + p3 ^ 2c3...... pk …… 2ck （其中P1 ----- Pk为n！的质因子 ，
    c1 -----ck为对应质因子的次数)
    n! ^ 2的约数个数 = （2c1 + 1) * (2c2 + 1) * (2c3 + 1)...... * （2ck + 1）

n为1e6 ，很大，参考阶乘分解的做法 ,先线性筛出1e6以内的所有质数，再求n内每个质数出现的次数。

细节：两个10w以内的数字相乘可能会爆int ,要加（long long）来防止因为爆int而出现负数

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10 ,mod = 1e9 + 7;

int n ,primes[N] , cnt;
bool st[N];

void init(int n){

    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;

        for(int j = 0; i * primes[j] <= n; j ++){

            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;

        }
    }

}

int main(){

    cin >> n;

    init(n);

    int res = 1;
    for(int i = 0; i < cnt; i ++){
        int p = primes[i];
        ll sum = 0;

        for(int j = n; j > 0; j /= p) sum += j / p;

        res = (ll)res * ( 2 * sum + 1 ) % mod;
    }

    cout << res << endl;

    return 0;
}

Acwing 198反素数

题目描述：

对于任何正整数x，其约数的个数记作g(x)，例如g(1)=1、g(6)=4。

如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。

例如，整数1，2，4，6等都是反素数。

现在给定一个数N，请求出不超过N的最大的反素数。

题目模型：爆搜 + 求约数个数

（1）刚看到题目，爆搜的解法很难想到，当觉得没思路时，可以分析题目的性质，从性质入手。

（2）哪个数是1~N中最大的反素数？就是约数个数最多的里面最小的那个

性质：    1.不同的质因子 最多只有9个  因为 2 * 3 * 5 * 7 * 13 .... 29 >10^9 （质数从2乘到29已经大于1e9了 ，可见质因子的个数最多只有9个）

        2.每一个质因子的次数最大是30 因为 2 ^ 31 >  1e9

        3.所有质因子次数一定递减（为了让其值最大）

结论：因为空间内最多只有9个质因子，可以采用爆搜搜遍所有的质因子和相应的次数的组成情况，可以找出约数个数最多的最小的那个数。

约数个数公式：

n = p1 ^ c1 + p2 ^ c2 + p3 ^ c3 ..... + pk ^ ck(其中P1 ----- Pk为n的质因子 ，
    c1 -----ck为对应质因子的次数)
    n 的约数个数 = （c1 + 1) * (c2 + 1) * (c3 + 1)...... * （ck + 1）

细节：详细见代码注释

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int primes[] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23};
int n , maxn , num;

void dfs(int u , int last ,int p ,int sum){

    if(sum > maxn || sum == maxn && p < num){ // 如果当前这个数的约数个数大于等于maxn并且数值比答案小 ，更新他们
        maxn = sum;
        num = p;
    }

    if(u >= 9) return ; // 如果枚举完了所有质数就可以直接返回

    for(int i = 1; i <= last; i ++){
        if((ll)p * primes[u] > n) break; // 如果这一次的乘积已经大于n了 ，直接退出
        p *= primes[u];
        dfs(u + 1 , i , p  ,sum * (i + 1)); // 枚举下一个质数对应的情况
    }
}

int main(){

    cin >> n;

    dfs(0 , 30 , 1 , 1); // dfs参数：当前枚举到了哪个质数 ，上一个质因子的次数 ，总的乘积 ，约数的个数

    cout << num << endl;

    return 0;
}

Acwing200Hankson的趣味题

题目描述：

已知正整数a0,a1,b0,b1，设某未知正整数x满足：

1、 x和a0的最大公约数是a1；
2、 x和b0的最小公倍数是b1。

Hankson的“逆问题”就是求出满足条件的正整数x。

对于每组数据：若不存在这样的x，请输出0；

若存在这样的x，请输出满足条件的x的个数；

算法模型：

求约数 + 线性筛素数 + gcd/Lcm

求解：

（1）首先从题面直接考虑，能否直接枚举x判断是否满足条件，看到2e9的数据范围，pass

（2）再考虑gcd和lcm的性质，如何来缩小需要枚举的x的范围。可以看到x和b0的Lcm是b1 ，也就是满足条件的x一定是d的约数。

（3）现在问题转化为了如何求d的所有约数，先考虑采用试除法直接求约数，时间复杂度大约为1e8的级别（如果是1s的话可以过，但是0.3s肯定TLE）

（4）现在考虑如何优化求约数的步骤，用到之前分解质因数的方法：先线性筛出素数，再求出每个质数在d里出现的次数，因为已知int范围内约数个数最多也就1600个，空间并不大，所以可以分解质因数过后可以直接用dfs暴搜出d的所有约数，这样时间复杂度约为1e6 ，没问题。

细节：

两个小于1e5的数乘在一起可能会爆int ，要使用（longlong）转化，（这题对于数论问题时间复杂度的分析十分有益）。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e4 + 10;

int n,cnt,primes[N];
bool st[N];

struct node{ // 存储d的每个质因子和质因子的次数
    int p , s;
}fac[N];
int fcnt;

void init(int n){ // 线性筛素数

    for(int i = 2; i <= n; i ++){

        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; i * primes[j] <= n; j ++){

            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;

        }
    }
}

int dcnt = 0 ,divv[N];
void dfs(int u , int p){

    if(u == fcnt){
        divv[dcnt ++] = p;
        return ;
    }

    for(int i = 0; i <= fac[u].s; i ++){

        dfs(u + 1 , p);
        p *= fac[u].p;

    }


}

int main(){

    init(N - 1);

    int T;
    cin >> T;
    while(T--){

        int a , b , c ,d;
        cin >> a >> b >> c >> d;

        int t = d;
        fcnt = 0;
        for(int i = 0; primes[i] <= t / primes[i]; i ++){ // 对d进行分解质因数 ，求出每个质因子出现的次数
            int q = primes[i];

            if(t % q == 0){
                int sum = 0;

                while(t % q == 0) t /= q ,sum++;

                fac[fcnt ++] = {q ,sum};

            }
        }
        if(t > 1) fac[fcnt ++] = {t ,1};

        dcnt = 0; // 暴搜出d的所有约数
        dfs(0 ,1);

        int res = 0;
        for(int i = 0; i < dcnt; i ++){ // 判断满足条件的约数的个数

            if(gcd(divv[i] ,a) == b && (ll)divv[i] * c / gcd(divv[i] , c) == d) res++;
        }

        cout << res << endl;
    }

    return 0;
}

Acwing201可见的点

题目描述：

在一个平面直角坐标系的第一象限内，如果一个点(x,y)与原点（0,0）的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点(4,2)就是不可见的，因为它与原点的连线会通过点(2,1)。

编写一个程序，计算给定整数N的情况下，满足0≤x，y≤N0≤x，y≤N的可见点（x，y）的数（可见点不包括原点）

算法模型：

欧拉函数

求解：

（1）通过对样例给出的图观察，可以发现是关于y = x这条直线对称的，求出一半即可。

（2）由题面入手，可以转化为对于每一条y = kx 的直线来说，有且仅有第一个点（x0 ,y0）会被光照到，其实等价于：在第一个点x0 ，y0 左下方，没有一个点属于y = kx这条直线。

                     y0          y0
y0 = k * x0     k = ____    y = ____ * x       其实最终变换为y0和x0互质
                     x0          x0


证明一下：如果y0 和 x0 不互质 ，那么必定存在一个大于0的正整数D ，满足gcd（y0 ，x0） = D
                x0       y0
        那么 （ _____  , _____) 这个点的坐标一定都是正整数 ，而且这个点在y = kx这条直线上 ，并且在
                D        D
                (y0 , x0) 的左下方。

（3）终于发现了欧拉函数的踪影了，对于每一个正整数x ，我们求一下当前x的欧拉函数，再累加起来，就是下半部分能被照到的点的数量，再乘2 ，加上y = x这条直线上的第一个点即可。

细节：

y = x 这条直线上还有一个点不要忘记 + 1；

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int  cnt  , primes[N] , phi[N];
bool st[N];

void init(int n){ // 线性筛求欧拉函数

    phi[1] = 1;
    for(int i = 2; i <= n; i ++){

        if(!st[i]){
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; i * primes[j] <= n; j ++){

            st[i * primes[j]] = true;
            if(i % primes[j] == 0){

                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);

        }
    }
}

int main(){

    init(N - 1);

    int T;
    cin >> T;
    for(int i = 1; i <= T; i ++){

        int n;
        cin >> n;

        int res = 1;
        for(int i = 1; i <= n; i ++) res += 2 * phi[i];

        cout << i << " " << n << " " << res << endl;
    }

    return 0;

}

Acwing220最大公约数

题目描述：

给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。

算法模型：

欧拉函数 + 前缀和

求解：

（1）N为1e7 ，首先直接暴力枚举不行。

（2）从gcd的性质入手，因为题目要求 gcd（x , y） = p ,p为质数，换句话说

GCD( X / p ,Y / p ) = 1 。

（3）那么题目就转化为了，在 1到N / p ，之间有多少对（x ,y）互质的数对。

细节：

数据范围需要变化一下，因为x属于1到N ，那么x / p 就属于N / p ;

为了快速查询，采用前缀和来求欧拉函数的和。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e7 + 10;
int n , cnt , primes[N] , phi[N];
bool st[N];
ll s[N];

void init(int n){

    for(int i = 2; i <= n; i ++){

        if(!st[i]) primes[cnt ++] = i , phi[i] = i - 1;
        for(int j = 0; i * primes[j] <= n; j ++){

            st[primes[j] * i] = true;
            if(i % primes[j] == 0){
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }

    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + phi[i];

}

int main(){

    cin >> n;

    init(n);

    ll res = 0;
    for(int i = 0 ; i < cnt ; i ++){

        int p = primes[i];

        res += 2 * s[n / p] + 1;
    }

    cout << res << endl;

    return 0;
}

Acwing203同余方程

题目描述：

求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。

算法模型：

扩展欧几里得算法 + 线性同余方程

求解：

（1）线性同余方程：给定a,b,m,求一个整数x满足a * x ≡ b ( mod m )

（2）因为a * x ≡ b( mod m ) 等价于a * x−b 是m的倍数,如果y为一个负数,那么这个方程可以改写为a * x + m * y = b

（3）题意为 a * x ≡ 1( mod b )

（4）我们先用exgcd求出特解，再取其最小值。

细节：

正余数的求法 :(x % b + b) % b (c++负数取余会返回负数，所以要先加上b再取余)

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e9 + 10;

int exgcd(int a , int b , int &x ,int &y){

    if(!b){

        x = 1 , y = 0;
        return a;
    }
    int d = exgcd(b , a % b ,y , x);

    y -= a / b * x;

    return d;
}

int main(){

    int a , b;
    cin >> a >> b;

    int x , y;
    exgcd(a , b , x , y);

    cout << (x % b + b) % b << endl;

    return 0;
}

AcWing 222. 青蛙的约会

题目描述：

设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。

青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。

纬度线总长L米。

现在要你求出它们跳了几次以后才会碰面。

这两只青蛙只有在同一时间跳到同一点上，不然是永远都不可能碰面的。

算法模型：

扩展欧几里得 + 线性同余方程 + 数学推导

求解：

（1）首先画图，列好已知条件，再来列方程。

速度：             m                      n
——————————————————————————————————————————————————————————————————
位置：             A                      B                        

根据题意 ，数轴长度为L
我们假设这两只青蛙跳x次后相遇  ，那么意味着A要追上B ，就要追上（B - A）米
每跳一次 ，根据速度 ，可以追上（m - n）米

因为题目里是一根纬线 ，也就是一个圈 ，追上的路程可以表达为 ： （B - A） + y * L 米
（y属于正整数 ，也就是跑了几圈）

由此可以列出一个方程 ： （m - n） * x = b - a + y * L
移项：
    （m - n） * x - y *  L     =     b - a
      常数              常数          常数

（2）我们得到了一个不定方程，可以用扩展欧几里得算法来解出一个特解

（3）得到了一组特解x0 ，y0 就可以表示出通解

x = x0 + k * L / d (d为gcd)

y = y0 + k * (m - n) / d;

也就是要求x的一个最小的正整数解

细节：

exgcd求出的是刚好等于d的特解，我们还要把它放大（b - a ） / d 倍才是答案。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e9 + 10;

ll exgcd(ll a , ll b , ll &x , ll &y){

    if(!b){

        x = 1, y = 0;
        return a;
    }

    ll d = exgcd(b , a % b , y , x);
    y -= a / b * x;

    return d;

}

int main(){

    ll a , b , m , n , L;
    cin >> a >> b >> m >> n >> L;

    ll x ,y;
    ll d = exgcd(m - n , L ,x ,y);

    if((b - a) % d != 0) cout << "Impossible" << endl;
    else {

        x *= (b - a ) / d;
        ll t = abs(L / d);
        cout << (x % t + t) % t << endl;

    }

    return 0;
}

Acwing202最幸运的数字

题目描述：

8是中国的幸运数字，如果一个数字的每一位都由8构成则该数字被称作是幸运数字。

现在给定一个正整数L，请问至少多少个8连在一起组成的正整数（即最小幸运数字）是L的倍数。

算法模型：

枚举约数 + 快速幂 + 同余 + 数学推导

求解：

（1）对得到的式子进行化简，根据引理/性质：由 x 个 y 组成的数的公式是 y ∗（（10 * x - 1）/ 9 ）。比如 888888 这种数**

（2）若正整数 a,n 互质，则满足 a ^ x ≡ 1 ( mod n ) 的最小正整数 x0 必定是 φ(n)(n的欧拉函数值) 的约数。

（数学推导）

令 d=gcd(L,8)，那么：

                    9 ∗ L / d | 10 ^ x − 1

                    10 ^ x − 1 ≡ 0 ( mod 9 ∗ L / d)

                    10 ^ x ≡ 1 (mod 9 ∗ L / d)

（4）我们首先求出L和8的gcd ，算出 9 * L / d = C , 求出C的欧拉函数，利用（2）枚举C的约数，找到满足条件的C的约数最小的那个。

细节：

这题在算10的次方的时候用快速幂，居然会爆longlong ，必须在快速幂里面用”龟速乘“ 。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL qmul(LL a, LL k, LL b)
{
    LL res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % b;
        a = (a + a) % b;
        k >>= 1;
    }
    return res;
}

LL qmi(LL a, LL k, LL b)
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = qmul(res, a, b);
        a = qmul(a, a, b);
        k >>= 1;
    }
    return res;
}

LL get_euler(LL C)
{
    LL res = C;
    for (LL i = 2; i <= C / i; i ++ )
        if (C % i == 0)
        {
            while (C % i == 0) C /= i;
            res = res / i * (i - 1);
        }
    if (C > 1) res = res / C * (C - 1);
    return res;
}

int main()
{
    int T = 1;
    LL L;
    while (cin >> L, L)
    {
        int d = 1;
        while (L % (d * 2) == 0 && d * 2 <= 8) d *= 2;

        LL C = 9 * L / d;

        LL phi = get_euler(C);

        LL res = 1e18;
        if (C % 2 == 0 || C % 5 == 0) res = 0;
        else
        {
            for (LL d = 1; d * d <= phi; d ++ )
                if (phi % d == 0)
                {
                    if (qmi(10, d, C) == 1) res = min(res, d);
                    if (qmi(10, phi / d, C) == 1) res = min(res, phi / d);
                }
        }

        printf("Case %d: %lld\n", T ++, res);
    }

    return 0;
}

欧拉函数与中国剩余定理补

Acwing873 欧拉函数

题目描述：

给定n个正整数ai，请你求出每个数的欧拉函数。

欧拉函数的定义：1 ~N中与N互质的数的个数被称为欧拉函数

（1）如何计算欧拉函数：若对N分解质因数得N = p1 ^ a1 * p2 ^ a2 * p3 ^ a3....pm ^ am

（2）phi(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 * ..... * (pm - 1) / pm

当我们在求1到N中和N互质的数的个数的时候（容斥原理）：

1：从1到N中去掉p1 , p2 , … , pk的所有倍数（P1 ---- Pk 为N的质因子）

2：因为所有pi * pj （i , j 属于1 — k）都会被多减了一次，所以要加回来

3：以此类推，pi * pj * pk 会多加三次...........

4：将整个式子整理出来：可得 N * (p1 - 1) / p1 * (p2 - 1) / p2 * ..... * (pm - 1) / pm

代码：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int T;
    cin >> T;

    while(T --){
        int a;
        cin >> a;

        int res = a;
        for(int i = 2; i <= a / i; i ++){

            if(a % i == 0){

                res = res / i * (i - 1);
                while(a % i == 0) a /= i;
            }
        }
        if(a > 1) res = res / a * (a - 1);

        cout << res << endl;

    }

    return 0;
}

Acwing874筛法求欧拉函数

题目描述：

给定一个正整数n，求1~n中每个数的欧拉函数之和。

（1）因为欧拉函数和质数之间紧密的关系，我们可以在筛质数的同时将欧拉函数一起求出。

线性筛复习：

void get_eulers(int n)
{

    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;

        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {

                break;
            }

        }
    }
}

（1）当一个数P是质数的时候，它的欧拉函数值就是P - 1 ，因为P前面每一个数都和P互质。

（2）下面开始枚举每个 i 的质数倍，如果primes[j] 已经是 i 的最小质因子了，那么phi[i * primes[j]]

就比我们已知的phi[i] 多乘了一个primes[j] ,即对phi[i] 分解质因数，里面已经乘过了一个（1 - 1 / prmies[j]）

那么我们可以观察到

phi[primes[j] * i ] = phi[i] * primes[j];

（3）那么如果pemies[j] 不是 i 的最小质因子，再对primes[j] * i 分解质因数的话就会多乘一个（1 - 1 / prmies[j]）（因为我们对 i 分解质因数里面是没有的），

把primes[j] * （1 - 1 / prmies[j]））乘开，可得

phi[primes[j] * i ] = phi[i] * (primes[j] - 1);

分别按情况整合到一起，于是就得到了线性筛+欧拉函数：

void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

代码：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1000010;


int primes[N], cnt;
int euler[N];
bool st[N];


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}


int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += euler[i];

    cout << res << endl;

    return 0;
}

中国剩余定理

Acwing204表达整数的奇怪方式

题目描述：

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足∀i∈[1,n]

（1）对于一个线性同余方程组，中国剩余定理要求余数mi必须两两互质，但是题目并没有限制，那么考虑对算法本身进行变形。

(2)先来看两个式子：

对于两个式子将其合并：

x ≡ m1( % a1) + x ≡ m2 ( % a2 )
则有：

x = k1 ∗ a1 + m1 ， x = k2 ∗ a2 + m2

得：

k1 ∗ a1 + m1 = k2 ∗ a2 + m2
移项可得：

k1 ∗ a1 − k2 ∗ a2 = m2 − m1
也就是：

① k1 ∗ a1 + k2 ∗ ( −a2 ) = m2 − m1
也就是我们需要找到一个最小的k1,k2使得等式成立（因为要求x最小，而a和m都是正数）。

(3) 用扩展欧几里得算法找出一组解
我们已知a1,m1,a2,m2可以用扩展欧几里得算法算出一个k1,k2使得：k′1∗a1+k′2∗(−a1)=gcd(a1,−a2)

有特例： 若gcd(a1,−a2) ∤ m2−m1则无解。

那么整理出来后：

设d=GCD(a1,−a2) , y=( m2 − m1 ) / d
只需让k1,k2分别扩大y倍，则可以找到一个k1,k2满足①式：

k1=k′1∗y , k2=k′2∗y , 再找到其最小正整数解即可.

(4)
每次考虑合并两个式子，将这n个式子合并n−1次后变为最后的式子

细节：

Lcm(a1,a2)和% a2 / d，需要取绝对值。又因为d = gcd( a1 , −a2 )，我们不知道a1的正负性（可能是上一步推过来的）。

这里需要abs（% a2 / d ）（因为负余数是取不到正整数解的）；

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


int main()
{
    int n;
    cin >> n;

    LL x = 0, m1, a1;
    cin >> m1 >> a1;
    for (int i = 0; i < n - 1; i ++ )
    {
        LL m2, a2;
        cin >> m2 >> a2;
        LL k1, k2;
        LL d = exgcd(m1, -m2, k1, k2);
        if ((a2 - a1) % d)
        {
            x = -1;
            break;
        }

        k1 *= (a2 - a1) / d;
        k1 = (k1 % (m2/d) + m2/d) % (m2/d);

        x = k1 * m1 + a1;

        LL m = abs(m1 / d * m2);
        a1 = k1 * m1 + a1;
        m1 = m;
    }

    if (x != -1) x = (x % m1 + m1) % m1;

    cout << x << endl;

    return 0;
}

Acwing1303斐波那契前 n 项和

题目描述：

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2 。现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Sn mod m。

求解：

（1）朴素算法是O(n)，但数据范围已经超过1e9 ，会T。

(2) 我们可以构造一个矩阵来优化。我们知道一个n * m的矩阵只能与一个m * r的矩阵相乘（即待乘矩阵的第一个矩阵的行与第二个矩阵的列数必须相同），即C[i ， j] = A[i ，1~m] * B[1~m ， j]，两两相乘然后在相加，以此类推得出一个n * r的矩阵。

由Fn的递推可得：

Fn = 1 * Fn-1 + 1 * Fn-2 + 0 * Sn-1 
Fn-1 = 1 * Fn-1 + 0 * Fn-2 + 0 * Sn-1
Sn = 1 * Fn-1 + 1 * Fn-2 + 1 * Sn-1 = Fn + Sn-1

我们每次与构造出来的矩阵A相乘即可得到数列下一项，即矩阵A ^ n-1 * B 等于数列的第n+1项。
（3）问题就转化为矩阵如何快速乘法了，自然而然想到矩阵快速幂。

代码：

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

typedef long long LL;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);
}

int main()
{
    cin >> n >> m;

    int f1[N] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n -- ;
    while (n)
    {
        if (n & 1) mul(f1, f1, a);  // res = res * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}

Acwing 1304佳佳的斐波那契

题目描述：

用 T(n)=(F1+2 * F2+3 * F3+…+n * Fn) mod m 表示 Fibonacci 数列前 n 项变形后的和 mod m 的值。现在佳佳告诉你了一个 n 和 m，请求出 T(n) 的值。

求解：（1）这题的区别在于，正常的递推式Fn =（fn , fn+1） * [0,1;1,1] = Fn+1 = (fn+1 , fn+2)

在我们展开计算的时候是不能有未知数的，（思维跳跃，难想难想）

Fn = F1 * A ^ n - 1
题目中的Tn = 1 * F1 + 2 * F2 + ... + n * Fn显然存在n这个系数未知量

（2）题目中提示可以找找Tn与Sn之间的关系，下面对Sn与Tn的等式推导一番：

Tn是N方级别 ，Sn为On级别 ，尝试给Sn * n得
n * Sn - Tn = (n - 1) * F1 + (n - 2) * F2 + ... + F(n - 1)...1式
(n + 1) * Sn+1 - Tn+1 = n * F1 + (n - 1) * F2 + ... + F(n)...2式

1式 - 2式 = Sn

新开函数Pn = 1式 ，Pn+1 = 2式

观察到Pn = n * Sn - Tn
移项得 Tn = n * Sn - Pn

整理下已知式子可得：
Pn = Pn-1 + Sn-1
Sn = Sn-1 + fn
fn = fn-1 + fn-2

至此可以观察到未知量已经都没有了

（3）根据式子来构造矩阵

Fn = (fn ,fn+1 ,Sn ,Pn) * [               ] = Fn+1 
                            0 , 1 , 0 , 0
                            1 , 1 , 1 , 0
                            0 , 0 , 1 , 1
                            0 , 0 , 0 , 1

已知Fn+1 = Fn * A , Fn = F1 * A ^ n - 1
F1 = [1 , 1 , 1 , 0];

细节：

注意负数取模的问题。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 4;

int n, m;

void mul(int c[][N], int a[][N], int b[][N])  // c = a * b
{
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

int main()
{
    cin >> n >> m;

    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = {1, 1, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
    };

    int k = n - 1;

    // 快速幂
    while (k)
    {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }

    cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}

组合计数

1 乘法原理

2 加法原理

3 组合数

4 排列计数

1：递推法

递推的思想与DP十分类似，做法基本按DP的集合划分来。

Acwing1307牡牛和牝牛

题目描述：

约翰要带 N 只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。

牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 K只牝牛。

请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 5000011 取模。

求解：

（1）公牛看成1 ，母牛看成0 ，问题转化为求01字符串的排列方案数。

含义：f[i] 表示最后一个1 在第i个位置的字符串的集合

属性：方案数

DP分析：

集合划分：

1 0 0 0 1 0 ........ 0  1

因为题目限制了两个1之间至少有k个0 ，那么上一个转移过来的状态至少是

1 0 0 0 1 0 .........0  1
           -----k个0--   i
        (i - k - 1)

 根据i - k 的位置可以把f[i] 划分为不重不漏的子集,于是
 求方案数的递推式为：f[i] = f[0] + f[1] + f[2] + ... + f[i - k - 1];


那么最终答案就是最后一个1在 0到n 位置上的方案数的总和 ， 即
ans = f[0] + f[1] + f[2] + ... + f[n];

细节：

N的范围是1e5 , 朴素写法二重循环的话最坏情况为n方，会超时，可以观察到我们每次都是循环求和，想到用前缀和来优化。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 , mod = 5000011;

int f[N] , s[N];

int main(){

    int n , k;
    cin >> n >> k;

    f[0] = s[0] = 1;
    for(int i = 0; i <= n; i ++){
        f[i] = s[ max(i - k - 1 , 0) ];
        s[i] = ( s[i - 1] + f[i] ) % mod;
    }

    cout << s[n] << endl;

    return 0;
}

2.排列组合的角度

Acwing1308方程的解

题目描述：

对于不定方程 a1+a2+⋯+ak−1+ak=g(x)，其中 k≥1 且 k∈N∗，x 是正整数，g(x)=x ^ x mod1000（即 x ^ x 除以 1000 的余数），x,k 是给定的数。

我们要求的是这个不定方程的正整数解组数。

求解：

（1）从题面来看，这个x的x次mod1000的值肯定是可以求出来的，使用快速幂，我们令求出来的答案为n。

（2）给定k-1个未知量，求这个方程等于n的正整数解，其实非常契合排列组合中的隔板法 ，下面来模拟一下样例

当k = 3 ， n = 2 时
方程为 a1 + a2 + a3 = 4
隔板法 ：
    等于几就相当于存在几个小球 ，往他们中间插   未知数个数 - 1  块木板（小球为0 ，木板为1）
    0  1   0   1   0 0
    a1     a2      a3

    0   1  0 0  1   0
    a1      a2     a3

    0 0  1 0   1    0
    a1     a2    a3


    显然可以看到正整数的解的组数等于3个空任选两个放木板的组合数 ，等于
     2      1
    C  =  C   = 3
     3      3

（3）至此题目转化为求 n - 1 个空里面选 k - 1 个插木板的组合数。

（3.5）本题推荐采用求组合数的公式

 m       m - 1     m - 1
C   =  C       + C
 n       n - 1     n

（4）这题没有取模要求，说明需要自己手写高精度加法

细节：

求组合数有多种方法，如果需要写高精度可以尝试采用递推加法（仍需复习）

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 150;

int k, x;
int f[1000][100][N];

int qmi(int a, int b, int p){
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void add(int c[], int a[], int b[]){

    for (int i = 0, t = 0; i < N; i ++ )
    {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
}

int main(){
    cin >> k >> x;

    int n = qmi(x % 1000, x, 1000);

    // C(n - 1, k - 1)
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j <= i && j < k; j ++ )
            if (!j) f[i][j][0] = 1;
            else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);  // f[i][j] = f[i - 1][j] + f[i - 1][j - 1];

    int *g = f[n - 1][k - 1];
    int i = N - 1;
    while (!g[i]) i -- ;
    while (i >= 0) cout << g[i -- ];

    return 0;
}

Acwing1309车的放置

题目描述：

给定一个棋盘的四个参数，在这个棋盘上放 k 个相互不攻击的车，也就是这 kk个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。只需要输出答案 mod100003 后的结果。

求解：

（1）这道题考察的也是排列组合的角度，乘法原理和加法原理。

（2）先从题面来看

假设我们现在有一个3 * 4 的矩形
0 , 0 , 0 , 0
0 , 0 , 0 , 0
0 , 0 , 0 , 0

由于车的性质 ，两个车不能在同一行或同一列 
如果我们要放两个车 ，那么在行数的选择上就等价于 ，三行里面选两行 即C[2 , 3]
再来看列 ，如在列数的选择上 ，第一个车没有限制 ，随便选 ，第二个车不能与第一个同列 ，以此类推。
可以看出在列数的选择上等价于 A[2 , 3]

(3)刚刚考虑的是四四方方的矩形，但是题目给的是类似梯形，无法直接求，于是想到根据加法原理来分割，可以分成两个四四方方的矩形，就可以计算了

题目里给的图形
0 0
0 0
0 0 0 0
0 0 0 0

参数为a , b , c , d

可以横向一刀切 ，上面的部分是
0 0 
0 0
长为a , 宽为b

下面的部分为
0 0 0 0
0 0 0 0
长为a + c ， 宽为d

根据（2）的计算方法来放车：
上半部分放i个车的话 ，下面就要放k - i个车 ，
方案数为C[i , b] * A[i , a] * C[k - i] * A[k - i ,a + c - i]
i从1到k枚举求和（y总视频中的P就是排列数A）

细节：

爆int要多加注意转换为（long long ）计算

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2010, mod = 100003;

int fact[N], infact[N];

int qmi(int a, int k){
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int C(int a, int b){
    if (a < b) return 0;
    return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;
}

int P(int a, int b){
    if (a < b) return 0;
    return (LL)fact[a] * infact[a - b] % mod;
}

int main(){
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ){
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2) % mod;
    }

    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;

    int res = 0;
    for (int i = 0; i <= k; i ++ ){
        res = (res + (LL)C(b, i) * P(a, i) % mod * C(d, k - i) % mod * P(a + c - i, k - i)) % mod;
    }

    cout << res << endl;

    return 0;
}

Acwing1312数三角形

题目描述：

给定一个 n × m 的网格，请计算三点都在格点上的三角形共有多少个。

求解：

（1）看到题面求顶点都在格点上的三角形，可以想到又是类似排列组合来选格点构成三角形

（2）

因为给的是边长，我们需要先n, m 将其转化为格点数，从 n × m 个格点中选出 3 个合法格点构成三角形，方案数为 C[3 , n * m] ，仔细想想，不是每三个点都可以成立，如果三点共线的话就无法构成三角形，发现这题还有容斥原理在里面，答案 = 总数 - 不符合条件的情况。

（3）下面来枚举一下三点共线的情况：

1: 斜率不存在（竖直）：n * C[3 , m]

2:斜率为 0（水平）：m * C[3 , n]
3:斜率存在且不为 0，斜率为正，与斜率为负是对称的，只考虑一半就可以。
首先n - 1, m - 1; 还原为边的长度。在 n × m 的矩形中，枚举底为 i，高为 j 的直角三角形，共有 (n − i + 1) * ( m − j + 1 ) 种，像这样的直角三角形，它斜边上的两个端点一定在格点上，那么就只需要统计斜边上除了端点，还存在的整数格点的数量。

可以算出有 gcd( i , j ) − 1 个。那么这个三角形的斜边对三点共线的情况为：( gcd( i , j ) − 1)
不合法的情况为 2 * (n − i + 1 ) * ( m − j + 1) * ( gcd ( i , j ) − 1)

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

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

LL C(int n){
    return (LL)n * (n - 1) * (n - 2) / 6;
}

int main(){
    int n, m;
    cin >> n >> m;

    n ++, m ++ ;

    LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);

    cout << res << endl;

    return 0;
}

Acwing1312序列统计

题目描述：

给定三个正整数 N,L,R，统计长度在 1 到 N 之间，元素大小都在 L 到 R 之间的单调不降序列的数量。

输出答案对 1e6+3 取模的结果。

求解：

（1）初看题面，数据范围1e9 ，数组下标开不下，再深入思考，由于数据之间的关系都是单一相对的那么可以将L 到 R的区间整体向左平移L个单位，变为0到R - L ，这样方便操作了。

（2）我们设序列长度为 k，题目要求a1 ， a2 ， .... ，ak ，在0到r - l这个区间内的序列个数

构造开始：

令 x1=a1,x2=a2−a1,⋯,xk= ak −a(k−1)，可知0 ≤ x1 + x2 + ⋯ + xk ≤ R − L。

转化为了求上述满足条件的 {xk} 数列的个数，等价于用不超过 R−L 个小球放入 k 个盒子，盒子允许为空的方案数。

但是正面求其实并不好操作，如果解决盒子不空的情况会好做一些，那么可以这么转化：先给每一个盒子放入一个小球，那么就变成了盒子不空的情况，此时我们需要令小球的总数 +k，即用不超过 R−L+k 个小球放入 k 个盒子，且盒子不空的方案数。

排列组合经典方法隔板法：有一点需要注意的是，这里的条件是不等式，对于等式而言，我们用 k−1 个隔板将所有小球分为 k 部分；对于不等式，则是用 k 个木板，将所有小球分为 k+1 部分，其中最后一部分被舍弃（即不选用），当然最后一部分的个数在本题可以为零。（0代表小球，1代表木板）

第一部分：0 ... 0 1 0 ... 0 1 ... 1 0 ... 0 


0 ... 0 1 0 ... 0 1 ... 1    无

开始计算：运行排列组合的知识， n 个球，有 n−1 个空，加上最右边的一个“无”，共 n 个空，插入 k 个木板。答案：C[k , R − L+ k] , k需要循环枚举从1到N求和。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int p = 1000003;

int qmi(int a, int k){
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(int a, int b){
    if (a < b) return 0;

    int down = 1, up = 1;
    for (int i = a, j = 1; j <= b; i --, j ++ )
    {
        up = (LL)up * i % p;
        down = (LL)down * j % p;
    }

    return (LL)up * qmi(down, p - 2) % p;
}

int Lucas(int a, int b){
    if (a < p && b < p) return C(a, b);
    return (LL)Lucas(a / p, b / p) * C(a % p, b % p) % p;
}

int main(){
    int T;
    cin >> T;
    while (T -- )
    {
        int n, l, r;
        cin >> n >> l >> r;
        cout << (Lucas(r - l + n + 1, r - l + 1) + p - 1) % p << endl;
    }

    return 0;
}

卡特兰数的推导方式

Acwing1315网格

题目描述：

某城市的街道呈网格状，左下角坐标为 A(0,0)，右上角坐标为 B(n,m)，其中 n≥m。

现在从 A(0,0) 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 (x,y) 都要满足 x≥y，请问在这些前提下，到达 B(n,m) 有多少种走法。

求解：

卡特兰数，斯特林数 ，.... （详细后补）

（1）将 (n,m) 沿着 y=x+1 直线对称点为 (m−1,n+1)

不合法方案第一次接触 y=x+1y=x+1 的点之后的部分沿着这条直线翻折，一一对应着一条从原点到 (m−1,n+1) 的路径
答案为：C(n + m , m) − C( n + m , n + 1)

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int primes[N], cnt;
bool st[N];
int a[N], b[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p)
{
    int s = 0;
    while (n) s += n / p, n /= p;
    return s;
}

void mul(int r[], int &len, int x)
{
    int t = 0;
    for (int i = 0; i < len; i ++ )
    {
        t += r[i] * x;
        r[i] = t % 10;
        t /= 10;
    }
    while (t)
    {
        r[len ++ ] = t % 10;
        t /= 10;
    }
}

void sub(int a[], int al, int b[], int bl)
{
    for (int i = 0, t = 0; i < al; i ++ )
    {
        a[i] -= t + b[i];
        if (a[i] < 0) a[i] += 10, t = 1;
        else t = 0;
    }
}

int C(int x, int y, int r[N])
{
    int len = 1;
    r[0] = 1;

    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        int s = get(x, p) - get(y, p) - get(x - y, p);
        while (s -- ) mul(r, len, p);
    }

    return len;
}

int main()
{
    init(N - 1);

    int n, m;
    cin >> n >> m;
    int al = C(n + m, m, a);
    int bl = C(n + m, n + 1, b);

    sub(a, al, b, bl);

    int k = al - 1;
    while (!a[k] && k > 0) k -- ;
    while (k >= 0) printf("%d", a[k -- ]);

    return 0;
}

Acwing1316有趣的数列

题目描述：

我们称一个长度为 2n 的数列是有趣的，当且仅当该数列满足以下三个条件：

它是从 1 到 2n 共 2n 个整数的一个排列 {ai}；
所有的奇数项满足 a1<a3<⋯<a(2n−1) ，所有的偶数项满足 a2<a4<⋯<a2n；
任意相邻的两项 a2i−1 与 a2ii (1≤i≤n) 满足奇数项小于偶数项，即：a2i−1<a2i。

任务是：对于给定的 n，请求出有多少个不同的长度为 2n 的有趣的数列。

因为最后的答案可能很大，所以只要求输出答案 mod P 的值。

求解：

（1）(屑题目也是卡特兰数，刚看题面很难联想到)

（2）

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n, p;
int primes[N], cnt;
bool st[N];

void init(int n){
    for (int i = 2; i <= n; i ++ )
    {
        if  (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int qmi(int a, int k){
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int get(int n, int p){
    int s = 0;
    while (n)
    {
        s += n / p;
        n /= p;
    }
    return s;
}

int C(int a, int b){
    int res = 1;
    for (int i = 0; i < cnt; i ++ )
    {
        int prime = primes[i];
        int s = get(a, prime) - get(b, prime) - get(a - b, prime);

        res = (LL)res * qmi(prime, s) % p;
    }

    return res;
}

int main(){

    scanf("%d%d", &n, &p);
    init(n * 2);

    cout << (C(n * 2, n) - C(n * 2, n - 1) + p) % p << endl;

    return 0;
}

容斥原理

Acwing214Devu和鲜花

题目描述：

Devu有N个盒子，第i个盒子中有Ai枝花。同一个盒子内的花颜色相同，不同盒子内的花颜色不同。

Devu要从这些盒子中选出M枝花组成一束，求共有多少种方案。若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案。结果需对1e9+7取模之后方可输出。

求解：

（1）题面来看，是一个多重集合的组合数问题，那么首先来思考一下简单的不带限制的多重集合

（2）多重集合中有k种元素，每种元素无限，如果要从里面选r个元素，那么答案等价于有r个0和（k - 1）个1的排列数

答案为C[r + k - 1 , k - 1]

(3）仔细思考，这道题目是带有限制的多重集合排列数，限制为第i种元素选出的数量不能大于Ai ，很显然正面入手非常困难，考虑下先来计算不符合的条件，对于第i种元素，我们可以先选出Ai + 1 个，这样直接不符合，然后剩下的就可以随便选了

根据上面 ， 不满足条件的数量就是
求和（1——N）C[N + M - Ai - 2 , N - 1] - 求和（1——N）C[N + M - Ai - Aj - 3 , N - 1]+...+

(-1)^ (N + 1)C[N + M - 求和（1——N）Ai - （N+1) , N - 1]

(4) 答案为总的 - 不满足

细节：

由于式子里分子可能很大，所以记得用卢卡斯定理取模，防止爆longlong

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 20, mod = 1e9 + 7;

LL A[N];
int down = 1;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;

    return (LL)up * down % mod; // 费马小定理
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> A[i];

    for (int j = 1; j <= n - 1; j ++ ) down = (LL)j * down % mod;
    down = qmi(down, mod - 2, mod);

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
            {
                sign *= -1;
                a -= A[j] + 1;
            }
        res = (res + C(a, b) * sign) % mod;
    }

    cout << (res + mod) % mod << endl;

    return 0;
}

Acwing215破译密码

题目描述：

对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。

求解：

（1）看题面，暴力枚举肯定是行不通的，脑中搜索思考gcd相关的知识

（2）（用到线性筛法求莫比乌斯函数。。。详细后补）

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 50010;

int primes[N], cnt;
bool st[N];
int mobius[N], sum[N];

// 线性筛法，求莫比乌斯函数
void init(int n)
{
    mobius[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            mobius[i] = -1;
        }
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                mobius[t] = 0;
                break;
            }
            mobius[t] = mobius[i] * -1;
        }
    }

    for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + mobius[i];
}

int main()
{
    init(N - 1);

    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        a /= d, b /= d;
        int n = min(a, b);
        LL res = 0;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = min(n, min(a / (a / l), b / (b / l)));
            res += (sum[r] - sum[l - 1]) * (LL)(a / l) * (b / l);
        }

        printf("%lld\n", res);
    }

    return 0;
}

Acwing217绿豆蛙的归宿

题目描述：

给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。

数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。

现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

求解：

（1）观察题面，确定是求期望，一：走向每条路的概率为1/K

（2）因为走向每一条边是的等可能的，那么剩下的就是计算每一条边对于总的答案的贡献

（3）每条边的贡献：就是自己的这条边的边权+到达这条边之前的值，对于这些求和即可。

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dout[N];
double f[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

double dp(int u)
{
    if (f[u] >= 0) return f[u];
    f[u] = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        f[u] += (w[i] + dp(j)) / dout[u];
    }
    return f[u];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        dout[a] ++ ;
    }

    memset(f, -1, sizeof f);

    printf("%.2lf\n", dp(1));

    return 0;
}

```

3 评论

秦淮岸灯火阑珊 2020-02-27 18:01

tql

左手影视 2020-02-29 14:50

谢谢秦大佬hhhhh

秦淮岸灯火阑珊 2020-02-29 15:49 回复了左手影视的评论

加油！

App 内打开

算法提高课第五章笔记2

Acwing1290越狱

Acwing1291 轻拍牛头

Acwing1294 樱花

Acwing 198反素数

Acwing200Hankson的趣味题

题目描述：

算法模型：

求解：

细节 ：

代码：

Acwing201可见的点

题目描述：

算法模型：

求解：

细节：

代码：

Acwing220最大公约数

题目描述：

算法模型：

求解：

细节：

代码：

Acwing203同余方程

题目描述：

算法模型：

求解：

细节：

代码：

AcWing 222. 青蛙的约会

题目描述：

算法模型：

求解：

细节：

代码：

Acwing202最幸运的数字

题目描述：

算法模型：

求解：

细节：

代码：

欧拉函数与中国剩余定理补

Acwing873 欧拉函数

题目描述：

欧拉函数的定义 ：1 ~N中 与N互质的数的个数被称为欧拉函数

当我们在求1到N中和N互质的数的个数的时候（容斥原理）：

Acwing874筛法求欧拉函数

题目描述：

线性筛复习：

代码：

中国剩余定理

Acwing204表达整数的奇怪方式

题目描述：

细节：

代码

Acwing1303斐波那契前 n 项和

题目描述：

求解：

代码：

细节：

代码：

组合计数

1：递推法

题目描述：

求解：

DP分析：

细节：

代码：

2.排列组合的角度

Acwing1308方程的解

题目描述：

求解：

细节：

代码：

Acwing1309车的放置

题目描述：

求解：

细节：

代码：

Acwing1312数三角形

细节：

欧拉函数的定义：1 ~N中与N互质的数的个数被称为欧拉函数