結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:51:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 1,174 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 76,764 KB |
最終ジャッジ日時 | 2024-08-25 14:51:18 |
合計ジャッジ時間 | 5,014 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
'''行列累乗ライブラリ使用上の注意→ベクトルを入れる場合も二次元配列にする。'''def mat_mul(a, b, m) :I, J, K = len(a), len(b[0]), len(b)c = [[0] * J for _ in range(I)]for i in range(I) :for j in range(J) :for k in range(K) :c[i][j] += a[i][k] * b[k][j]c[i][j] %= mreturn cdef mat_pow(x, n, m):y = [[0] * len(x) for _ in range(len(x))]for i in range(len(x)):y[i][i] = 1while n > 0:if n & 1:y = mat_mul(x, y, m)x = mat_mul(x, x, m)n >>= 1return yfrom collections import defaultdictN,M,K=map(int,input().split())p=998244353dic=defaultdict(int)for i in range(1,M+1):dic[M//i]+=1memo=list(dic.keys())A=[[0 for _ in range(len(memo))] for _ in range(len(memo))]for i in range(len(memo)):for j in range(len(memo)):if i==j:continueif abs(memo[i]-memo[j])<=K:A[i][j]=dic[memo[j]]A[i][i]=dic[memo[i]]B=mat_pow(A,N-1,p)#print(dic,memo)#print(A)mul=mat_mul([[dic[memo[i]] for i in range(len(memo))]],B,p)print(sum(mul[0])%p)