第 7 章 数学与计数

const int MOD = 1000000007;                     // 写成常量，数值从题面复制
long long a, b, c;                              // 参与运算的量一律 long long，并且始终保持在 [0, MOD) 里

long long sum     = (a + b) % MOD;              // 加
long long diff    = (a - b + MOD) % MOD;        // 减：a - b 可能是负数，先加上 MOD
long long product = a * b % MOD;                // 乘：两个小于 MOD 的数相乘不到 1e18，long long 装得下
long long triple  = a * b % MOD * c % MOD;      // 连乘：每乘一次就模一次
long long ratio   = a * power(b, MOD - 2) % MOD;// 除：乘以 b 的逆元（7.5 节），不能写 a / b

// 快速幂：O(log b) 求 a^b mod p。洛谷 P1226。
// 把 b 写成二进制，a^b 就是若干个 a^(2^k) 相乘；a^(2^k) 靠不断平方得到。
#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long p) {
    long long result = 1 % p;  // 写 1 % p 而不是 1：p = 1 时答案应该是 0
    a %= p;                    // 先取模，保证下面两个数相乘不超过 p*p
    while (b > 0) {
        if (b & 1) result = result * a % p;  // b 的这一个二进制位是 1：把当前的 a 乘进答案
        a = a * a % p;                       // a 平方，对应 b 的下一个二进制位
        b >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b, p;
    cin >> a >> b >> p;
    cout << a << '^' << b << " mod " << p << '=' << power(a, b, p) << '\n';
    return 0;
}

// 最大公约数、最小公倍数、扩展欧几里得。
// 输入 T，然后 T 行 a b（都是正整数）；每行输出 gcd(a,b)、lcm(a,b)、a 在模 b 意义下的逆元（不存在输出 -1）。
#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {  // 辗转相除：gcd(a, b) = gcd(b, a % b)，直到 b = 0
    return b == 0 ? a : gcd(b, a % b);
}

// 求一组整数 x、y 使 a*x + b*y = gcd(a, b)，返回值是 gcd(a, b)
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;  // a*1 + 0*0 = a
        return a;
    }
    long long g = exgcd(b, a % b, y, x);  // 注意这里 x、y 交换了位置
    y -= a / b * x;
    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long a, b, x, y;
        cin >> a >> b;
        long long g = exgcd(a, b, x, y);
        // a*x + b*y = 1 两边对 b 取模就是 a*x ≡ 1，所以 x 就是逆元；gcd 不是 1 时没有逆元
        long long inverse = g == 1 ? (x % b + b) % b : -1;          // x 可能是负数，调整到 [0, b)
        cout << gcd(a, b) << ' ' << a / g * b << ' ' << inverse << '\n';  // lcm 先除后乘，防止溢出
    }
    return 0;
}

bool is_prime(long long n) {
    if (n < 2) return false;                        // 0 和 1 不是质数
    for (long long d = 2; d * d <= n; d++)          // 只需试到根号 n
        if (n % d == 0) return false;
    return true;
}

// 埃氏筛：从小到大，遇到质数就把它的倍数全部划掉。O(n log log n)，n 到 1e7 没问题
for (int i = 2; i <= n; i++) {
    if (is_composite[i]) continue;                  // 被划掉过，是合数
    for (long long j = 1LL * i * i; j <= n; j += i) is_composite[j] = true;
}

// 线性筛（欧拉筛）：O(n) 求出 n 以内的全部质数。洛谷 P3383：q 次询问第 k 小的质数。
// 每个合数只被它最小的质因子筛掉一次，所以是线性的。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<bool> is_composite(n + 1, false);  // true 表示是合数；vector<bool> 每个元素只占 1 位，n = 1e8 也只要 12.5MB
    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes.push_back(i);  // 没被筛掉，是质数
        for (size_t j = 0; j < primes.size() && 1LL * i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;  // 筛掉 i * primes[j]，它的最小质因子是 primes[j]
            if (i % primes[j] == 0) break;       // primes[j] 已经是 i 的最小质因子，再往后筛就不是“最小质因子”了
        }
    }
    while (q--) {
        int k;
        cin >> k;
        cout << primes[k - 1] << '\n';  // primes 从下标 0 开始存
    }
    return 0;
}

// 质因数分解：从 2 开始试除，只需试到 sqrt(n)。
// 输入 T，然后 T 行每行一个 n（n >= 2）；每行输出“质因子 指数 质因子 指数 …”，质因子从小到大。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        for (long long d = 2; d * d <= n; d++) {  // d 用 long long：d*d 会超过 int
            if (n % d != 0) continue;
            int exponent = 0;
            while (n % d == 0) {  // 把 d 除干净，所以之后能整除 n 的 d 一定是质数
                n /= d;
                exponent++;
            }
            cout << d << ' ' << exponent << ' ';
        }
        if (n > 1) cout << n << " 1";  // 剩下的 n 是一个大于 sqrt 的质因子，最多只有一个
        cout << '\n';
    }
    return 0;
}

// 组合数取模：预处理阶乘和阶乘的逆元，之后 O(1) 回答 C(n, m) mod 1e9+7。
// 输入 T，然后 T 行 n m；每行输出 C(n, m)。m < 0 或 m > n 时答案是 0。
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;              // 必须是质数，才能用费马小定理求逆元
const int N = 1000000;                   // 式子里会出现的最大的 n
long long fact[N + 1], inv_fact[N + 1];  // fact[i] = i!，inv_fact[i] = i! 的逆元

long long power(long long a, long long b) {
    long long result = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) result = result * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return result;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
    inv_fact[N] = power(fact[N], MOD - 2);  // 费马小定理：a 的逆元是 a^(MOD-2)。只做这一次快速幂
    for (int i = N; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i % MOD;  // 1/(i-1)! = 1/i! * i
}

long long C(int n, int m) {
    if (m < 0 || m > n) return 0;  // 不合法的先挡掉，否则下标越界
    return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;  // n! / (m! * (n-m)!)
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();  // 别忘了调用
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        cout << C(n, m) << '\n';
    }
    return 0;
}

// 杨辉三角递推组合数：C(n, m) = C(n-1, m-1) + C(n-1, m)。只用加法，模数不是质数也能用。
// 输入第一行 q p（1 <= p <= 1e9+7），然后 q 行 n m（0 <= n, m <= 2000）；每行输出 C(n, m) mod p。
#include <bits/stdc++.h>
using namespace std;

const int N = 2000;
int c[N + 1][N + 1];  // (N+1)^2 个 int：N = 2000 约 16MB；N = 5000 约 100MB，开之前先算

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q, p;
    cin >> q >> p;
    for (int i = 0; i <= N; i++) {
        c[i][0] = 1 % p;  // 从 i 个里一个都不选：1 种
        for (int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % p;  // 第 i 个选 + 第 i 个不选；两个小于 p 的数相加不超过 int
    }
    while (q--) {
        int n, m;
        cin >> n >> m;
        cout << c[n][m] << '\n';  // m > n 的格子从没被赋值，全局数组默认是 0，正好是正确答案
    }
    return 0;
}

// 计数题的暴力：DFS 枚举所有方案，逐个检查是否合法，数一数。
// 例题：长度为 n 的序列，每个位置填 1..k，相邻两个数不能相等，有多少种填法？（n <= 10，k <= 5）
// 正解是公式 k * (k-1)^(n-1)。暴力的用处：拿小数据的分、打表找规律、给正解对拍。
#include <bits/stdc++.h>
using namespace std;

int n, k, seq[15];
long long total;

bool valid() {  // 检查一个填好的方案是否合法：照着题面的要求逐条写
    for (int i = 2; i <= n; i++)
        if (seq[i] == seq[i - 1]) return false;
    return true;
}

void dfs(int pos) {  // 正在决定第 pos 个位置填什么
    if (pos > n) {   // 全部填完：检查，合法就计数
        if (valid()) total++;
        return;
    }
    for (int value = 1; value <= k; value++) {
        seq[pos] = value;
        dfs(pos + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    dfs(1);
    cout << total << '\n';
    return 0;
}

// 矩阵快速幂：求 n×n 矩阵 A 的 k 次方，每个元素对 1e9+7 取模。洛谷 P3390。
// 和整数快速幂逐行对应：乘法换成矩阵乘法，1 换成单位矩阵。
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007, N = 105;
int n;

struct Matrix {
    long long v[N][N];
    Matrix() { memset(v, 0, sizeof v); }  // 新建的矩阵全是 0
};

Matrix multiply(const Matrix &x, const Matrix &y) {
    Matrix z;
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= n; k++)
            for (int j = 1; j <= n; j++)
                z.v[i][j] = (z.v[i][j] + x.v[i][k] * y.v[k][j]) % MOD;  // 第 i 行乘第 j 列
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long k;
    cin >> n >> k;
    Matrix a, result;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> a.v[i][j];
            a.v[i][j] = (a.v[i][j] % MOD + MOD) % MOD;  // 输入可能是负数，先变成非负
        }
    for (int i = 1; i <= n; i++) result.v[i][i] = 1;  // 单位矩阵：相当于整数里的 1
    while (k > 0) {
        if (k & 1) result = multiply(result, a);
        a = multiply(a, a);
        k >>= 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << result.v[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}