結果

問題 No.3182 recurrence relation’s intersection sum
ユーザー timi
提出日時 2025-06-17 16:28:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 208 ms / 2,000 ms
コード長 2,388 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 77,316 KB
最終ジャッジ日時 2025-06-17 16:28:36
合計ジャッジ時間 7,616 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353 # a Random BIG Prime number

def ipow(base:int, power:int):
    ret, piv = 1, base
    while power:
        if (power & 1):
            ret = ret * piv % mod
        piv = piv * piv % mod
        power >>= 1
    return ret

def berlekamp_massey(x:list):
    ls, cur = [], []
    lf, ld = 0, 0
    for i in range(len(x)):
        t = 0
        for j in range(len(cur)):
            t = (t + x[i-j-1] * cur[j]) % mod
        if (t-x[i]) % mod == 0:
            continue
        if not cur:
            cur = [0] * (i+1)
            lf = i
            ld = (t-x[i]) % mod
            continue
        k = -(x[i]-t) * ipow(ld, mod-2) % mod
        c = [0] * (i-lf-1)
        c.append(k)
        for j in ls:
            c.append(-j * k % mod)
        if len(c) < len(cur):
            c += [0] * (len(cur)-len(c))
        for j in range(len(cur)):
            c[j] = (c[j]+cur[j]) % mod
        if (i-lf+len(ls)) >= len(cur):
            ls, lf, ld = cur, i, (t-x[i])%mod
        cur = c
    for i in cur:
        i = (i % mod + mod) % mod
    return cur

def get_nth(rec:list, dp:list, n:int):
    m = len(rec)
    s, t = [0]*m, [0]*m
    s[0] = 1
    if m != 1:
        t[1] = 1
    else:
        t[0] = rec[0]
    def mul(v:list, w:list):
        m = len(v)
        t = [0]*(2*m)
        for j in range(m):
            for k in range(m):
                t[j+k] += v[j] * w[k] % mod
                if t[j+k] >= mod:
                    t[j+k] -= mod
        for j in range(2*m-1, m-1, -1):
            for k in range(1, m+1):
                t[j-k] += t[j] * rec[k-1] % mod
                if t[j-k] >= mod:
                    t[j-k] -= mod
        # Resize idk if this is required
        if len(t) < m:
            t += [0]*(m-len(t))
        else:
            t = t[:m]
        return t
    while n:
        if n & 1:
            s = mul(s, t)
        t = mul(t, t)
        n >>= 1
    ret = 0
    for i in range(m):
        ret += s[i] * dp[i] % mod
    return ret % mod

def guess_nth_term(x:list, n:int):
    if n < len(x):
        return x[n]
    v = berlekamp_massey(x)
    if not v:
        return 0
    return get_nth(v, x, n)

K,L,R=map(int, input().split())
S=[1]
A=[1]
for i in range(0,10000):
  s=A[-1]*K+pow(i,K,mod)+pow(K,i,mod)
  s%=mod 
  A.append(s)
  S.append((S[-1]+s)%mod)
l=0
if L!=0:
  l=guess_nth_term(S,L-1)
r=guess_nth_term(S,R)
print((r-l)%mod)
0