combination.cpp

#include <algorithm>
#include <iostream>

using namespace std;

typedef long long Int;

Int MOD = 998244353;

// a ^ b % MOD
// O(log b)
// MODは素数でなくてもよい
Int power(Int a, Int b)
{
    if (b == 0)
        return 1;
    else if (b % 2 == 1)
        return b * power(a, b - 1) % MOD;
    else {
        Int half = power(a, b / 2);
        return half * half % MOD;
    }
}

// a ^ -1 % MOD
// O(log MOD)
//フェルマーの小定理をつかうのでMODは素数でないといけない
//そもそもMODが素数でないと逆元がないことがある
Int inv(Int a)
{
    return power(a, MOD - 2);
}

// O(k + log MOD)
// invを使うのでMODは素数でないといけない
Int nCk(Int n, Int k)
{
    Int bumbo = 1;
    Int bunsi = 1;
    for (int i = 1; i <= k; i++) {
        bumbo = (bumbo * (n + 1 - i)) % MOD;
        bunsi = (bunsi * i) % MOD;
    }
    return bumbo * inv(bunsi) % MOD;
}

// O(nk)で全部もとめる
//パスカルの三角形
// MODが素数でなくてもいけるのがエモい
void all_nCk(Int n, Int k)
{
    Int dp[n + 1][k + 1]; // dp[i][j] = iCj
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0)
                dp[i][j] = 1;
            else
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
        }
    }
}

// O(n)でn以下の逆元を全部求める
//これはエモい
// 0以外の全ての要素に逆元が存在しないといけないので，MODが素数でないといけない
//そもそもMODが素数でないと逆元がないことがある
void all_inverse(Int n)
{
    Int inv[n + 1];
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        // (MOD / i) * i + (MOD % i) == MOD == 0 (mod MOD) を考えて式変形
        inv[i] = -inv[MOD % i] * (MOD / i) % MOD;
        if (inv[i] < 0)
            inv[i] += MOD;
    }
}

// O(n + logM)でn以下の階乗とその逆元を全部求める
//うえのエモいやつ使わなくてもいけてエモい
// inverseを使うのでMODは素数でないといけない
//そもそもMODが素数でないと逆元がないことがある
void all_factorial_and_inverse(Int n)
{
    Int fact[n + 1], inv_fact[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[n] = inv(fact[n]);
    for (int i = n - 1; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

int main()
{
    cout << "Hello World" << endl;
}

Int array[n];

みたいなのは本当は良くない．(vectorを使おう！)