Подсчёт и перечисление комбинаторных объектов: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
Строка 1: Строка 1:
== Факториал ==
{| width="100%"
| width=50% |
const long long MOD = 1e9 + 7;
long long factorial(int n) {
    static vector<long long> memo(1e5);
    long long &res = memo[n];
    if (res)
        return res;
    if (n <= 1)
        return res = 1;
    return res = factorial(n - 1) * n % MOD;
}
| width="10px" | &nbsp;
| width=50% |
const long long MOD = 1e9 + 7;
vector<long long> precalcFactorials() {
    vector<long long> memo(1e5);
    memo[0] = 1;
    for (int i = 1; i < memo.size(); i++)
        memo[i] = memo[i - 1] * i % MOD;
    return memo;
}
long long factorial(int n) {
    static vector<long long> memo = precalcFactorials();
    return memo[n];
}
|}
== Число сочетаний из n по k ==
{| width="100%"
| width=50% |
const long long MOD = 1e9 + 7;
long long c(int n, int k) {
    static vector<vector<long long>> memo(1000, vector<long long>(1000, -1));
    long long &res = memo[n][k];
    if (res != -1)
        return res;
    if (k == 0 || k == n)
        return res = 1;
    return res = (c(n - 1, k) + c(n - 1, k - 1)) % MOD;
}
| width="10px" | &nbsp;
| width=50% |
const long long MOD = 1e9 + 7;
 
long long binPow(long long x, long long p, long long mod) {
    if (!p)
        return 1;
    if (p % 2)
        return binPow(x, p - 1, mod) * x % mod;
    long long r = binPow(x, p / 2, mod);
    return r * r % mod;
}
long long inv(long long x) {
    return binPow(x, MOD - 2, MOD);
}
long long c(int n, int k) {
    return factorial(n) * inv(factorial(k)) % MOD * inv(factorial(n - k)) % MOD;
}
|}
== Ссылки на задачи ==
== Ссылки на задачи ==



Текущая версия от 11:54, 20 ноября 2022

Факториал

const long long MOD = 1e9 + 7;

long long factorial(int n) {
    static vector<long long> memo(1e5);
    long long &res = memo[n];
    if (res)
        return res;

    if (n <= 1)
        return res = 1;

    return res = factorial(n - 1) * n % MOD;
}

 
const long long MOD = 1e9 + 7;

vector<long long> precalcFactorials() {
    vector<long long> memo(1e5);
    memo[0] = 1;
    for (int i = 1; i < memo.size(); i++)
        memo[i] = memo[i - 1] * i % MOD;
    return memo;
}

long long factorial(int n) {
    static vector<long long> memo = precalcFactorials();
    return memo[n];
}

Число сочетаний из n по k

const long long MOD = 1e9 + 7;

long long c(int n, int k) {
    static vector<vector<long long>> memo(1000, vector<long long>(1000, -1));
    long long &res = memo[n][k];
    if (res != -1)
        return res;

    if (k == 0 || k == n)
        return res = 1;

    return res = (c(n - 1, k) + c(n - 1, k - 1)) % MOD;
}





 
const long long MOD = 1e9 + 7;
 
long long binPow(long long x, long long p, long long mod) {
    if (!p)
        return 1;
    if (p % 2)
        return binPow(x, p - 1, mod) * x % mod;
    long long r = binPow(x, p / 2, mod);
    return r * r % mod;
}

long long inv(long long x) {
    return binPow(x, MOD - 2, MOD);
}

long long c(int n, int k) {
    return factorial(n) * inv(factorial(k)) % MOD * inv(factorial(n - k)) % MOD;
}

Ссылки на задачи

Ссылки