NOIp 数学 (小学奥数)

Basic knowledge

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

快速幂

// Pure Quickpow

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;

}

/* Matrix Quickpow

 * Au: H15teve

 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod 1000000007

ll 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 Link .

组合数

/* 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 <bits/stdc++.h>

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: Link

/* 判断是否闰年 */

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];

}

中国剩余定理