結果

問題 No.2181 LRM Question 2
ユーザー katonyonkokatonyonko
提出日時 2023-01-07 01:37:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,016 ms / 2,000 ms
コード長 3,478 bytes
コンパイル時間 660 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 87,400 KB
最終ジャッジ日時 2024-05-08 01:12:27
合計ジャッジ時間 7,481 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,480 KB
testcase_01 AC 36 ms
52,864 KB
testcase_02 AC 624 ms
76,948 KB
testcase_03 AC 36 ms
52,864 KB
testcase_04 AC 42 ms
60,416 KB
testcase_05 AC 35 ms
52,992 KB
testcase_06 AC 42 ms
59,904 KB
testcase_07 AC 35 ms
52,736 KB
testcase_08 AC 757 ms
76,288 KB
testcase_09 AC 397 ms
77,668 KB
testcase_10 AC 954 ms
76,288 KB
testcase_11 AC 989 ms
76,544 KB
testcase_12 AC 1,016 ms
76,652 KB
testcase_13 AC 51 ms
64,640 KB
testcase_14 AC 108 ms
78,592 KB
testcase_15 AC 45 ms
60,544 KB
testcase_16 AC 121 ms
87,400 KB
testcase_17 AC 80 ms
75,904 KB
testcase_18 AC 91 ms
76,408 KB
testcase_19 AC 67 ms
71,808 KB
testcase_20 AC 84 ms
73,984 KB
testcase_21 AC 149 ms
77,028 KB
testcase_22 AC 87 ms
76,544 KB
testcase_23 AC 38 ms
53,120 KB
testcase_24 AC 36 ms
52,864 KB
testcase_25 AC 38 ms
52,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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, rm):
        r0 = 0
        m0 = 1
        for a, b in rm:
            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] % 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
        rm = [(self.lucas(n, k, p, c, i), pow(p, c)) for i, (p, c) in enumerate(self.prime)]
        ret, _ = self.crt(rm)
        return ret

L,R,M=map(int,input().split())
ans=0
BC=BinomialCoefficient(M)
for i in range(L,R+1):
  ans+=BC(2*i,i)-2
  ans%=M
print(ans)
0