結果

問題 No.2996 Floor Sum
ユーザー 👑 testestest
提出日時 2024-12-20 15:31:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,604 ms / 5,000 ms
コード長 2,001 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 81,736 KB
最終ジャッジ日時 2024-12-21 18:07:09
合計ジャッジ時間 11,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 通らん　なぜ

MOD=998244353
from math import factorial as fact
from collections import defaultdict

def eval(f,x):
  ret=0
  for c in f[::-1]:
    ret=(ret*x+c)%MOD
  return ret

def newton_interpolation(x,y):
  ret=[]
  f=[1]
  for xx,yy in zip(x,y):
    e=eval(f,xx)
    c=eval(ret,xx)
    coef = (yy-c)*pow(e,-1,MOD)%MOD
    ret.append(0)
    for i in range(len(f)): ret[i]=(ret[i]+coef*f[i])%MOD
    for i in range(len(f)-1,0,-1): f[i]=(f[i]*-xx+f[i-1])%MOD
    f[0]=f[0]*-xx%MOD
    f.append(1)
  while ret[-1]==0: ret.pop()
  return ret

S=[
	newton_interpolation(list(range(k+2)),[sum(i**k for i in range(N)) for N in range(k+2)])
	for k in range(23)
]

choose=[[[fact(n)//fact(r)//fact(s)//fact(n-r-s)%MOD for s in range(n-r+1)] for r in range(n+1)] for n in range(23)]

def scary_sum(p,q,N,M,A,B):
  pq=p+q
  ans=0
  memo_main=defaultdict(int)
  memo_main[p,q]=1
  while N>0 and memo_main:
    A1,A=A//M,A%M
    B1,B=B//M,B%M
    memo_sub=defaultdict(int)
    A1pow=[1]
    for i in range(pq):A1pow.append(A1pow[-1]*A1%MOD)
    B1pow=[1]
    for i in range(pq):B1pow.append(B1pow[-1]*B1%MOD)
    for (p,q),coef_main in memo_main.items():
      for r in range(q+1):
        for s in range(q-r+1):
          coef = choose[q][r][s] * A1pow[s] * B1pow[q-r-s]%MOD
          if coef!=0: memo_sub[p+s,r]+=coef*coef_main%MOD
    memo_main=defaultdict(int)
    SpN=[eval(S[p],N) for p in range(pq+1)]
    K=(A*(N-1)+B)//M
    Kpow=[1]
    for i in range(pq):Kpow.append(Kpow[-1]*K%MOD)
    for (p,q),coef_sub in memo_sub.items():
      if q==0:
        ans+=SpN[p]*coef_sub%MOD
        continue
      if K==0: continue
      ans += Kpow[q] * SpN[p] *coef_sub %MOD
      for i in range(q):
        for j in range(p+2):
          coef=choose[q][i][0]*S[p][j]%MOD
          if coef!=0:
            memo_main[i,j]-=coef*coef_sub%MOD
    N,M,A,B=K,A,M,M-B+A-1
  return ans%MOD


T=int(input())
for _ in range(T):
	temp=list(map(int,input().split()))
	temp[2]+=1
	print(scary_sum(*temp)%998244353)
0