結果

問題 No.3182 recurrence relation’s intersection sum
ユーザー sgfc
提出日時 2025-06-13 23:02:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,889 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 95,812 KB
最終ジャッジ日時 2025-06-13 23:02:41
合計ジャッジ時間 34,048 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 35 TLE * 2 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def modinv(a):
    return pow(a, MOD - 2, MOD)

def setup(max_n):
    fac = [1] * (max_n + 1)
    finv = [1] * (max_n + 1)
    inv = [1] * (max_n + 1)
    for i in range(2, max_n + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
    return fac, finv

def binom(n, r, fac, finv):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * finv[r] % MOD * finv[n - r] % MOD

def mat_mul(a, b):
    h, w, l = len(a), len(b[0]), len(b)
    res = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            for k in range(l):
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD
    return res

def mat_pow(mat, power):
    size = len(mat)
    res = [[int(i == j) for j in range(size)] for i in range(size)]
    while power:
        if power % 2:
            res = mat_mul(res, mat)
        mat = mat_mul(mat, mat)
        power //= 2
    return res

def main():
    k, l, r = map(int, input().split())
    fac, finv = setup(k + 1)

    size = k + 4
    m = [[0] * size for _ in range(size)]

    for i in range(size):
        if i == 0:
            m[i][0] = k
            m[i][1] = 1
            for j in range(2 + k):
                m[i][j] = m[i][j]  # do nothing
            m[i][2 + k] = 1
        elif i < k + 2:
            top = k - (i - 1)
            for j in range(i, 2 + k):
                m[i][j] = binom(top, k + 1 - j, fac, finv)
        elif i == k + 2:
            m[i][k + 2] = k
        elif i == k + 3:
            m[i][0] = 1
            m[i][i] = 1

    ml = mat_pow(m, l)
    mr = mat_pow(m, r + 1)

    def get_value(mat):
        return (mat[k + 3][0] + mat[k + 3][k + 1] + mat[k + 3][k + 2]) % MOD

    ans = (get_value(mr) - get_value(ml)) % MOD
    print(ans)

if __name__ == "__main__":
    main()
0