Basic knowledge

\[ C_n^m=\frac{n!}{m!(n - m)!} \]

快速幂

// Pure Quickpowinline int qpow(int n, int m, int mod) {    ll tot = 1;    for (ll k = n; m; k = k * k % mod, m >>= 1)        if (m & 1) tot = tot * k % mod;    return tot;}

/* Matrix Quickpow * Au: H15teve */#include 
    
     using namespace std;typedef long long ll;const int mod 1000000007ll n, p;struct matrix {    ll m[100][100];    matrix operator * (matrix &a) {        matrix b;        for (int i = 0; i < n; i++)            for (int j = 0; j < n; j++) {                b.m[i][j] = 0;                for (int k = 0; k < n; k++)                    b.m[i][j] = (b.m[i][j] + m[i][k] * a.m[k][j]) \% mod;            }        return b;    }} start;matrix mpow(matrix a, ll k) {    if (k == 1) return a;    a = mpow(a, k / 2);    if (k \% 2) return (a * a) * start;    else return a * a;}int main() {    n = readll(), p = readll();    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++)            start.m[i][j] = readll();    matrix a = mpow(start, p);        for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++)            writellb(a.m[i][j]);        writeln();    }    return 0;}
    

乘法逆元

/* 费马小定理求乘法逆元 * Au: Menci */inline int qpow(int n, int m, int mod) {    ll tot = 1;    for (ll k = n; m; k = k * k % mod, m >>= 1)        if (m & 1) tot = tot * k % mod;    return tot;}inline int inv(int x, int mod) {    return qpow(x, mod - 2);}/* 扩展欧几里得求乘法逆元 * Au: Menci */void exgcd(const int a, const int b, int &g, int &x, int &y) {    if (!b) g = a, x = 1, y = 0;    else exgcd(b, a % b, g, y, x), y -= x * (a / b);}inline int inv(const int num) {    int g, x, y;    exgcd(num, MOD, g, x, y);    return ((x % MOD) + MOD) % MOD;}

For more specific explanation, see .

组合数

/* Luogu 2822 组合数问题 * Au: GG * C_n^m=\frac{n!}{m!(n - m)!} * 预处理 DP O(n^2) + 统计 O(n) */const int N = 2000 + 3, Nx = 2001;int n, m, t, k, ans, c[N][N], d[N][N];int main() {    scanf("%d%d", &t, &k);    for (int i = 1; i <= Nx; i++) {        c[i][1] = i % k; c[i][i] = 1;    }    for (int i = 2; i <= Nx; i++)         for (int j = 2; j <= i - 1; j++)             c[i][j] = (c[i - 1][j] % k + c[i - 1][j - 1] % k) % k;    for (int i = 1; i <= Nx; i++)        for (int j = 1; j <= i; j++) {            if (c[i][j]) d[i][j] = d[i][j - 1];            else d[i][j] = d[i][j - 1] + 1;        }    while (t--) {        scanf("%d%d", &n, &m);        ans = 0;        for (int i = 1; i <= n; i++) {            if (i > m) ans += d[i][m]; else ans += d[i][i];        }        printf("%d\n", ans);    }        return 0;}

同余方程

\[ ax \equiv 1 \pmod b \]

\[ ax + by = 1 \]

void exgcd(const int a, const int b, int &g, int &x, int &y) {    if (!b) g = a, x = 1, y = 0;    else exgcd(b, a % b, g, y, x), y -= x * (a / b);}int main() {    int a, b, g, x, y;    scanf("%d%d", &a, &b);    exgcd(a, b, g, x, y);    printf("%d\n", (x + b) % b);    return 0;}

素数筛法

Eratosthenes 筛法：

/* Sieve of Eratosthenes * Au: GG */#include 
    
     using namespace std;const int N = 100000002;int n, prime[N], tot;bool check[N];inline void Sieve_of_Eratosthenes() {    for (register int i = 2; i <= n; i++) {        if (!check[i]) prime[tot++] = i;        for (register int j = 0; j < tot; j++) {            if (i * prime[j] > n) break;            check[i * prime[j]] = true;            if (i % prime[j] == 0) break;        }    }}int main() {    scanf("%d", &n);    Sieve_of_Eratosthenes();    printf("%d\n", tot);    return 0;}
    

GCD

ll gcd(ll x, ll y) {    if (x == y) return x;    return !y ? x : gcd(y, x % y);}

GCD 欧几里得算法

$ a,b $ 为正整数，设集合 \(A=\{xa+yb | x, y\) 是整数 \(\}\)，则 $ A $ 中最小正元素是 $ \gcd(a,b) $

long kgcd(long a, long b) {    if (a == 0) return b;    if (b == 0) return a;    if (!(a & 1) && !(b & 1)) return kgcd(a >> 1, b >> 1) << 1;    else if (!(b & 1)) return kgcd(a, b >> 1);    else if (!(a & 1)) return kgcd(a >> 1, b);    else return kgcd(abs(a - b), min(a, b));}

LCM

\[ \text{lcm} ( a, b ) = a \times b \div \gcd ( a, b ) \]

实际上最好写成 $ a \div \text{lcm} (a,b) \times b $.

long lcm(long a, long b) {    long c, d, sw;    c = (a >= b) ? a : b;    d = (a <= b) ? a : b;    while (c % d != 0) {        sw = c % d;        c = d;        d = sw;    }    return (a / d) * b;}

求多个数的 \(\textrm{LCM}\)，需要将 \(res\) 初始化为 \(1\)

数的各位之和

int sum(int number) {    int sum = 0;    while (number != 0) {        sum += number % 10;        number /= 10;    }    return sum;} // 不知道数有几位,但是可以每次都取个位

年份、日期

Reference:

/* 判断是否闰年 */bool isleap(int& year) {    if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) return true;    else return false;}/* 返回一年的最大天数 */int maxday(int& year) {    if (isleap(year)) return 366;    else return 365;}// Days 是指距离某个日期是多少天, 应该均可以的, 只是最终结果可能有所变化的.string getweek(int& days) {    return week[days % 7];}

中国剩余定理

For more specific explanation, see .