组合数

https://www.zybuluo.com/ArrowLLL/note/713749

Pascal 公式打表组合数取模

const int maxn = 1e3 + 5;
const int mod = 1e5 + 3;
int tC[maxn][maxn];

inline int C(int n, int k)
{
    if (k > n) return 0;
    return tC[n][k];
}

void calcC(int n)
{
    for (int i = 0; i < n; i++) {
        tC[i][0] = 1;
        for (int j = 1; j < i; j++) {
            tC[i][j] = (C(i - 1, j - 1) + C(i - 1, j)) % mod;
        }
        tC[i][i] = 1;
    }
}

const int maxn = 1e3 + 5;
const int mod = 1e5 + 3;
int tC[maxn * maxn];

inline int loc(int n, int k)
{
    int pos = (1 + (n >> 1)) * (n >> 1);
    pos += k;
    pos += (n & 1) ? (n + 1) >> 1 : 0;
    return pos;
}

inline int C(int n, int k)
{
    if (k > n) return 0;
    k = min(n - k, k);
    return tC[loc(n, k)];
}

void calcC(int n)
{
    for (int i = 0; i < n; i++) {
        tC[loc(i, 0)] = 1;
        for (int j = 1, e = i >> 1; j <= e; j++) {
            tC[loc(i, j)] = C(i - 1, j) + C(i - 1, j - 1);
        }
    }
}

逆元求组合数取模