写像12相ライブラリ
ただし写像12相以外の組み合わせ計算も含む
- Pow(x, n): 繰り返し二乗法
- P(n, r):
順列
- C(n, r):
組み合わせ
- H(n, r):
重複組み合わせ
- IEP(n, r): 包除原理
- Stirling(n, r): 第二種スターリング数
- Catalan(n): カタラン数
#include <bits/stdc++.h> namespace NyaaLIB { /** * 写像12相ライブラリ * ただし写像12相以外の組み合わせも含む * オーバーフローするときはテンプレート引数をmodintか多倍長整数にする **/ template <class T = long long> struct NT_TwelvefoldWay { // 引数にModライブラリを渡すことも可能 using ll = long long; T Pow(ll x, ll n) { // 繰り返し二乗法 T res = 1; if (0 < n) { res = Pow(x, n / 2); res = res * res; if (n % 2 != 0) res *= x; } return res; } T P(ll n, ll r) { // 順列 permutation if (r < 0 || n < r) return 0; T res = 1; for (ll i = n; n - r < i; i--) res *= i; return res; } T C(ll n, ll r) { // 組合わせ combination if (r < 0 || n < r) return 0; if (n - r < r) return C(n, n - r); T res = 1; for (ll i = n; n - r < i; i--) res *= i; for (ll i = r; 0 < i; i--) res /= i; return res; } /** * @brief 重複組合わせ combination with repetition * @note * n種類の無限の玉からr個を選ぶ * 例: 4H6 = A..AB..BC..CD..D→ACCCDD * または r個の玉をn種類の箱に入れる * 例: 4H6 = [○][ ][○○○][○○] * r個の○とn-1本の｜を並べる組み合わせと同値 **/ T H(ll n, ll r) { if (n < 0 || r < 0) return 0; return (r == 0) ? 1 : C(n + r - 1, r); } /** * @brief 包除原理 inclusion–exclusion principle * @note 区別可能なn人を区別可能なr個の部屋に分配する（空き部屋はNG） **/ T IEP(ll n, ll r) { T res = Pow(r, n); for (auto i = 1; i < r; i++) { if (i % 2 != 0) res -= C(r, i) * Pow(r - i, n); else res += C(r, i) * Pow(r - i, n); } return res; } /** * @brief 第二種スターリング数 stirling numbers of the second kind * @note 区別可能なn人を区別不可なr個の部屋に分配する（空き部屋はNG） **/ T Stirling(ll n, ll r) { return IEP(n, r) / P(r, r); } /** * @brief カタラン数 catalan number * @note n個のAとBについてk番目までに現れる個数が常にB<=Aとなる組合わせ **/ T Catalan(ll n) { return C(2 * n, n) - C(2 * n, n - 1); } }; }
