結果

問題 No.2181 LRM Question 2
ユーザー MasKoaTSMasKoaTS
提出日時 2022-11-30 18:28:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,067 ms / 2,000 ms
コード長 3,295 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 102,364 KB
最終ジャッジ日時 2024-10-07 13:15:18
合計ジャッジ時間 9,367 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
86,352 KB
testcase_01 AC 120 ms
86,124 KB
testcase_02 AC 665 ms
90,048 KB
testcase_03 AC 116 ms
86,228 KB
testcase_04 AC 125 ms
89,136 KB
testcase_05 AC 117 ms
86,212 KB
testcase_06 AC 127 ms
88,272 KB
testcase_07 AC 121 ms
85,688 KB
testcase_08 AC 827 ms
89,664 KB
testcase_09 AC 444 ms
90,452 KB
testcase_10 AC 1,056 ms
89,792 KB
testcase_11 AC 1,064 ms
90,480 KB
testcase_12 AC 1,067 ms
89,820 KB
testcase_13 AC 129 ms
88,868 KB
testcase_14 AC 185 ms
102,364 KB
testcase_15 AC 128 ms
89,032 KB
testcase_16 AC 203 ms
100,320 KB
testcase_17 AC 153 ms
89,152 KB
testcase_18 AC 162 ms
90,084 KB
testcase_19 AC 148 ms
89,944 KB
testcase_20 AC 153 ms
93,040 KB
testcase_21 AC 219 ms
89,468 KB
testcase_22 AC 157 ms
89,936 KB
testcase_23 AC 115 ms
86,364 KB
testcase_24 AC 112 ms
86,020 KB
testcase_25 AC 116 ms
86,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools as iter
import collections as coll
import heapq as hq
import bisect as bis
from decimal import Decimal as dec
from functools import cmp_to_key
import math
import sys
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10 ** 6)
inp = sys.stdin.readline
input = lambda : inp().rstrip()
getN = lambda : int(inp())
getNs = lambda : map(int, inp().split())
getList = lambda :list(map(int, inp().split()))
getStrs = lambda n : [input() for _ in [0] * n]
def yexit(): print("Yes"); exit(0)
def nexit(): print("No"); exit(0)
pi = 3.141592653589793
mod = 1000000007
MOD = 998244353
INF = 4611686018427387903
dx = [1, 0, -1, 0];	dy = [0, 1, 0, -1]
#di = coll.defaultdict(int)

class BinomialCoefficient:
	def __init__(self, mod):
		self.mod = mod
		self.prime = self.prime_factorize(mod)
		self.facs = []
		self.invs = []
		self.pows = []
		self.factinvs = []
		for p, c in self.prime:
			pc = pow(p, c)
			fac = [1] * pc
			inv = [1] * pc
			for i in range(1, pc):
				k = i
				if(i % p == 0):
					k = 1
				fac[i] = fac[i - 1] * k % pc
			inv[-1] = fac[-1]
			for i in range(1, pc)[::-1]:
				k = i
				if(i % p == 0):
					k = 1
				inv[i - 1] = inv[i] * k % pc
			self.facs.append(fac)
			self.invs.append(inv)
			pw = [1]
			while(pw[-1] * p != pc):
				pw.append(pw[-1] * p)
			self.pows.append(pw)

	def prime_factorize(self, n):
		prime = []
		f = 2
		while(f * f <= n):
			if(n % f == 0):
				n //= f
				cnt = 1
				while(n % f == 0):
					n //= f
					cnt += 1
				prime.append((f, cnt))
			f += 1
		if(n != 1):
			prime.append((n, 1))
		return prime

	def crt(self, r, m):
		n = len(r)
		r0 = 0
		m0 = 1
		for a, b in zip(r, m):
			r1 = a % b
			m1 = b
			if(m0 < m1):
				r0, r1, m0, m1 = r1, r0, m1, m0
			if(m0 % m1 == 0):
				if(r0 % m1 != r1):
					return 0, 0
				continue
			g, im = self.inv_gcd(m0, m1)
			u1 = m1 // g
			if((r1 - r0) % g):
				return 0, 0
			x = (r1 - r0) // g * im % u1
			r0 += x * m0
			m0 *= u1
			if(r0 < 0):
				r0 += m0
		return r0, m0

	def inv_gcd(self, n, m):
		n %= m
		if(n == 0):
			return m, 0
		s, t, m0, m1 = m, n, 0, 1
		while(t):
			u = s // t
			s -= t * u
			m0 -= m1 * u
			m0, m1, s, t = m1, m0, t, s
		if m0 < 0: m0 += m // s
		return s, m0

	def inv_mod(self, n, m):
		g, im = self.inv_gcd(n, m)
		return im

	def calc_e(self, n, k, r, p):
		e = 0
		while(n):
			n //= p
			e += n
		while(k):
			k //= p
			e -= k
		while(r):
			r //= p
			e -= r
		return e

	def lucas(self, n, k, p, c, i):
		pw = self.pows[i]
		fac = self.facs[i]
		inv = self.invs[i]
		r = n - k
		pc = pow(p, c)
		e = self.calc_e(n, k, r, p)
		if(e >= len(pw)):
			return 0
		ret = pw[e]
		if((p != 2 or c < 3) and (self.calc_e(n // pw[-1], k // pw[-1], r // pw[-1], p) & 1)):
			ret *= -1
		while(n):
			ret *= fac[n % pc] * inv[k % pc] * inv[r % pc]
			ret %= pc
			n //= p
			k //= p
			r //= p
		return ret

	def __call__(self, n, k):
		if(k < 0 or k > n):
			return 0
		if(k == 0 or k == n):
			return 1
		r = []
		m = []
		for i, (p, c) in enumerate(self.prime):
			r.append(self.lucas(n, k, p, c, i))
			m.append(pow(p, c))
		ret, _ = self.crt(r, m)
		return ret


"""
Main Code
"""

L, R, M = getNs()

nCk = BinomialCoefficient(M)
ans = 0
for i in range(L, R + 1):
	ans += nCk(i << 1, i) - 2
	ans %= M
print(ans)
0