結果

問題 No.2181 LRM Question 2
ユーザー MasKoaTSMasKoaTS
提出日時 2022-12-03 11:24:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 781 ms / 2,000 ms
コード長 3,888 bytes
コンパイル時間 2,669 ms
コンパイル使用メモリ 214,560 KB
実行使用メモリ 31,232 KB
最終ジャッジ日時 2024-10-10 13:41:21
合計ジャッジ時間 7,064 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 434 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 567 ms
5,248 KB
testcase_09 AC 230 ms
5,248 KB
testcase_10 AC 768 ms
5,248 KB
testcase_11 AC 780 ms
5,248 KB
testcase_12 AC 781 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 53 ms
31,232 KB
testcase_15 AC 4 ms
5,248 KB
testcase_16 AC 46 ms
24,832 KB
testcase_17 AC 10 ms
5,248 KB
testcase_18 AC 5 ms
5,248 KB
testcase_19 AC 4 ms
5,248 KB
testcase_20 AC 17 ms
10,240 KB
testcase_21 AC 58 ms
5,248 KB
testcase_22 AC 6 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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() {

	}

	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;
	}
};


/*
* Main Code
*/

int main(void) {
	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;
}
0