結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-27 13:50:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,967 ms / 3,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 79,616 KB |
最終ジャッジ日時 | 2024-12-25 23:13:46 |
合計ジャッジ時間 | 20,962 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
# Nの約数にしか止まらないから約数頂点上でのdp# しかしうまく実装できず人のを見る# https://yukicoder.me/submissions/872922N = int(input())def divisors(n):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]def factorization_dic(n): #辞書形式に改造arr = {}temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr[i] = cntif temp!=1:arr[temp] = 1if arr==[]:arr[n] = 1return arrN_divs = divisors(N)L = len(N_divs)all_factors = []for d in N_divs:all_factors.append(factorization_dic(d))#print(all_factors)mod = 998244353# Nの約数を大きい方から1まで並べるのはうまくいかないので小さい方からやる# dp[i]パターン数dp = [0]*Ldp[0] = 1for i in range(L):for j in range(i+1, L):if N_divs[j]%N_divs[i] != 0:continuetemp = dp[i]for p in all_factors[i]:if p == 1:continuep_count_current = all_factors[i][p]p_count_new = all_factors[j][p]if p_count_current == p_count_new:# 公式解説に説明あるけどよくわかんないね#print('i', i, 'j', j, 'p', p, p_count_current, p_count_new)temp *= p_count_new+1temp %= moddp[j] += tempdp[j] %= modans = dp[L-1]%modprint(ans)