結果
問題 | No.2996 Floor Sum |
ユーザー | 👑 testestest |
提出日時 | 2024-12-15 12:27:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,580 bytes |
コンパイル時間 | 370 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 207,388 KB |
最終ジャッジ日時 | 2024-12-20 23:30:45 |
合計ジャッジ時間 | 34,781 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 322 ms
97,580 KB |
testcase_01 | TLE | - |
testcase_02 | AC | 511 ms
207,388 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 2,539 ms
101,836 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 1,084 ms
96,336 KB |
testcase_08 | AC | 1,933 ms
103,116 KB |
testcase_09 | AC | 878 ms
95,044 KB |
testcase_10 | AC | 853 ms
94,408 KB |
testcase_11 | AC | 327 ms
91,292 KB |
testcase_12 | AC | 915 ms
203,804 KB |
ソースコード
from fractions import Fraction as F from functools import cache from math import factorial as fact def scary_sum_naive(p,q,N,M,A,B): return sum(i**p*((A*i+B)//M)**q for i in range(N)) def eval(f,x): ret=0 for c in f[::-1]: ret=ret*x+c 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)*F(1,e) ret.append(0) for i in range(len(f)): ret[i]+=coef*f[i] for i in range(len(f)-1,0,-1): f[i]=f[i]*-xx+f[i-1] f[0]=f[0]*-xx 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) ] @cache def choose(n,r,s): return fact(n)//fact(r)//fact(s)//fact(n-r-s) def scary_sum(p,q,N,M,A,B): A1,A2=A//M,A%M B1,B2=B//M,B%M ans=0 for r in range(q+1): for s in range(q-r+1): coef = choose(q,r,s) * A1**s * B1**(q-r-s) if coef!=0: ans+=coef*scary_sum_reduced(p+s,r,N,M,A2,B2) return ans @cache def scary_sum_reduced(p,q,N,M,A,B): # base case if N==0: return 0 if q==0: return int(eval(S[p],N)) K=(A*(N-1)+B)//M if K==0: return 0 # K==0 かつ q==0 のときは0でない ans = K**q * int(eval(S[p],N)) for i in range(q): for j in range(p+2): coef=choose(q,i,0)*S[p][j] if coef!=0: ans-=coef*scary_sum(i,j,K,A,M,M-B+A-1) return int(ans) T=int(input()) for _ in range(T): temp=list(map(int,input().split())) temp[2]+=1 print(scary_sum(*temp)%998244353) scary_sum_reduced.cache_clear()