結果
| 問題 | No.2181 LRM Question 2 |
| ユーザー |
 MasKoaTS
|
| 提出日時 | 2024-12-03 18:31:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 787 ms / 2,000 ms |
| コード長 | 5,168 bytes |
| コンパイル時間 | 2,477 ms |
| コンパイル使用メモリ | 207,672 KB |
| 最終ジャッジ日時 | 2025-02-26 10:48:21 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;struct BinomialCoefficient {ll mod = 2;vector<pair<ll, ll> > prime = {};vector<vector<ll> > facs = {};vector<vector<ll> > invs = {};vector<vector<ll> > pows = {};vector<ll> factinvs = {};static void swap(ll& a, ll& b) {ll tmp = a;a = b;b = tmp;}static ll pow(ll a, ll n) {ll ret = 1;while (n) {if (n & 1) {ret *= a;}a *= a;n >>= 1;}return ret;}static vector<pair<ll, ll> > primeFactorize(ll n) {vector<pair<ll, ll> > ret = {};ll cnt = 0;for (cnt; (n & 1) == 0; ++cnt) {n >>= 1;}if (cnt > 0) {ret.push_back({ 2,cnt });}for (ll f = 3; f * f <= n; f += 2) {cnt = 0;for (cnt; n % f == 0; ++cnt) {n /= f;}if (cnt > 0) {ret.push_back({ f,cnt });}}if (n > 1) {ret.push_back({ n,1 });}return ret;}BinomialCoefficient(ll mod) {this->mod = mod;prime = primeFactorize(mod);for (pair<ll, ll>& pa : prime) {ll p = pa.first, c = pa.second;ll pc = pow(p, c);vector<ll> fac(pc, 1);vector<ll> inv(pc, 1);for (ll i = 1; i < pc; ++i) {ll k = (i % p) ? i : 1;fac[i] = fac[i - 1] * k % pc;}inv[inv.size() - 1] = fac[inv.size() - 1];for (ll i = pc - 1; i > 0; --i) {ll k = (i % p) ? i : 1;inv[i - 1] = inv[i] * k % pc;}facs.push_back(fac);invs.push_back(inv);vector<ll> pw = { 1 };while (pw[pw.size() - 1] * p != pc) {pw.push_back(pw[pw.size() - 1] * p);}pows.push_back(pw);}}pair<ll, ll> crt(vector<ll>& r, vector<ll>& m) {ll n = r.size();ll r0 = 0, m0 = 1;for (int i = 0; i < r.size(); ++i) {ll a = r[i], b = m[i];ll r1 = a % b, m1 = b;if (m0 < m1) {swap(r0, r1);swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) {return { 0, 0 };}continue;}pair<ll, ll> pa = inv_gcd(m0, m1);ll g = pa.first, im = pa.second;ll u1 = m1 / g;if ((r1 - r0) % g) {return { 0,0 };}ll x = (r1 - r0) / g * im % u1;r0 += x * m0;m0 *= u1;if (r0 < 0) {r0 += m0;}}return { r0,m0 };}pair<ll, ll> inv_gcd(ll n, ll m) {n %= m;if (n == 0) {return { m, 0 };}ll s = m, t = n, m0 = 0, m1 = 1;while (t) {ll u = s / t;s -= t * u;m0 -= m1 * u;swap(m0, m1);swap(s, t);}if (m0 < 0) {m0 += m / s;}return { s, m0 };}ll inv_mod(ll n, ll m) {pair<ll, ll> pa = inv_gcd(n, m);return pa.second;}ll calc_e(ll n, ll k, ll r, ll p) {ll e = 0;while (n) {n /= p;e += n;}while (k) {k /= p;e -= k;}while (r) {r /= p;e -= r;}return e;}ll lucas(ll n, ll k, ll p, ll c, ll i) {vector<ll>& pw = pows[i];vector<ll>& fac = facs[i];vector<ll>& inv = invs[i];ll r = n - k, pc = pow(p, c);ll e = calc_e(n, k, r, p);if (e >= pw.size()) {return 0;}ll ret = pw[e];if ((p != 2 or c < 3) and (calc_e(n / pw[pw.size() - 1], k / pw[pw.size() - 1], r / pw[pw.size() - 1], p) & 1)) {ret = -ret;}while (n) {ret *= fac[n % pc] * inv[k % pc] % pc * inv[r % pc] % pc;ret %= pc;n /= p;k /= p;r /= p;}return ret;}ll calc(ll n, ll k) {if (k < 0 or k > n) {return 0;}if (k == 0 or k == n) {return 1;}vector<ll> r = {}, m = {};for (int i = 0; i < prime.size(); ++i) {pair<ll, ll> pa = prime[i];ll p = pa.first, c = pa.second;r.push_back(lucas(n, k, p, c, i));m.push_back(pow(p, c));}pair<ll, ll> pa = crt(r, m);return pa.first;}};int main(){ll l, r, m; cin >> l >> r >> m;BinomialCoefficient nCk(m);ll ans = 0;for(ll i = l; i < r + 1; ++i){ans += nCk.calc(i << 1, i) + m - 2;}ans %= m;cout << ans << endl;return 0;}