結果
問題 | No.2318 Phys Bone Maker |
ユーザー | navel_tos |
提出日時 | 2023-05-26 22:21:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 770 ms / 3,000 ms |
コード長 | 2,873 bytes |
コンパイル時間 | 742 ms |
コンパイル使用メモリ | 87,012 KB |
実行使用メモリ | 79,116 KB |
最終ジャッジ日時 | 2023-08-26 12:09:57 |
合計ジャッジ時間 | 12,286 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 65 ms
71,260 KB |
testcase_01 | AC | 63 ms
71,260 KB |
testcase_02 | AC | 679 ms
78,512 KB |
testcase_03 | AC | 71 ms
75,468 KB |
testcase_04 | AC | 70 ms
75,552 KB |
testcase_05 | AC | 69 ms
75,420 KB |
testcase_06 | AC | 67 ms
75,516 KB |
testcase_07 | AC | 84 ms
76,660 KB |
testcase_08 | AC | 82 ms
76,988 KB |
testcase_09 | AC | 69 ms
75,612 KB |
testcase_10 | AC | 69 ms
75,576 KB |
testcase_11 | AC | 72 ms
75,416 KB |
testcase_12 | AC | 76 ms
76,344 KB |
testcase_13 | AC | 116 ms
77,752 KB |
testcase_14 | AC | 70 ms
75,580 KB |
testcase_15 | AC | 69 ms
75,524 KB |
testcase_16 | AC | 71 ms
75,572 KB |
testcase_17 | AC | 70 ms
75,308 KB |
testcase_18 | AC | 86 ms
76,904 KB |
testcase_19 | AC | 66 ms
75,416 KB |
testcase_20 | AC | 69 ms
75,616 KB |
testcase_21 | AC | 68 ms
75,688 KB |
testcase_22 | AC | 69 ms
74,968 KB |
testcase_23 | AC | 71 ms
75,500 KB |
testcase_24 | AC | 67 ms
75,460 KB |
testcase_25 | AC | 72 ms
75,616 KB |
testcase_26 | AC | 83 ms
76,916 KB |
testcase_27 | AC | 69 ms
75,484 KB |
testcase_28 | AC | 67 ms
75,532 KB |
testcase_29 | AC | 68 ms
75,520 KB |
testcase_30 | AC | 70 ms
75,652 KB |
testcase_31 | AC | 70 ms
75,608 KB |
testcase_32 | AC | 77 ms
75,576 KB |
testcase_33 | AC | 67 ms
71,440 KB |
testcase_34 | AC | 69 ms
71,292 KB |
testcase_35 | AC | 280 ms
77,904 KB |
testcase_36 | AC | 526 ms
79,116 KB |
testcase_37 | AC | 469 ms
79,092 KB |
testcase_38 | AC | 403 ms
78,788 KB |
testcase_39 | AC | 770 ms
79,096 KB |
testcase_40 | AC | 657 ms
78,356 KB |
testcase_41 | AC | 761 ms
78,948 KB |
testcase_42 | AC | 628 ms
78,980 KB |
testcase_43 | AC | 81 ms
76,932 KB |
testcase_44 | AC | 160 ms
78,252 KB |
testcase_45 | AC | 155 ms
78,364 KB |
testcase_46 | AC | 535 ms
78,644 KB |
testcase_47 | AC | 85 ms
75,520 KB |
ソースコード
#yukicoder390E ''' 正整数Nが与えられる。Mは自由に選んで良い。 1から初めて、単調増加し、最終的にNになる。 隣接項はA[i]との最小公倍数になる。うーん、むずかしいぞ。 入力例を読もう。 なるほど。単に素因数を配列すればよい、という問題ではないわけだ。 それはそれとして素因数分解は必要だな。 上位の約数に遷移する、と考えればよさそうだ。 元々持っていた素因数は減らせないから、 1. もともと持っていた素因数ぶんは自由に使ってよい。 2. 増やすと決めた素因数は値が固定される。 増やさない範囲で他のものをいじってよい。 大小関係は常に単調増加することが保証されるから大丈夫でしょう。 963761198400=2^6*3^4*5^2*7^1*11^1*13^1*17^1*19^1*23^1 約数は最大6720個。ま、DPでしょうかね。 ''' #素因数分解し、(素因数,次数)の順に格納したリストを返す def Soinsu(CheckNumber): SoinsuList=[] for Soinsu in range(2,CheckNumber): if Soinsu*Soinsu>CheckNumber:break if CheckNumber%Soinsu!=0:continue SoinsuCount=0 while CheckNumber%Soinsu==0:SoinsuCount+=1;CheckNumber//=Soinsu SoinsuList.append((Soinsu,SoinsuCount)) if CheckNumber!=1:SoinsuList.append((CheckNumber,1)) return SoinsuList #xの約数を全列挙する。0以下の値の場合、[]を返す。 def divisor(x): Ldiv,Udiv=[],[] for i in range(1,x+1): if i**2>x:break if x%i==0: Ldiv.append(i) if i**2!=x:Udiv.append(x//i) return Ldiv+Udiv[::-1] from itertools import combinations as cb gcd=lambda x,y: gcd(y,x%y) if x%y else y N=int(input()); MOD=998244353; P=Soinsu(N); E=[P[i][1] for i in range(len(P))] base=[1] for i in range(len(P)-1): base.append(base[-1]*(E[i]+1)) hash=lambda T: sum(T[i]*base[i] for i in range(len(T))) rev =lambda H: tuple([H%base[i]//base[i-1] for i in range(1,len(base))]+[H//base[-1]]) DP=[1]+[0]*hash(E) for num in range(len(DP)): H=rev(num); choice=set() #choice[i]: まだ上昇余地がある因子 for i in range(len(H)): if H[i]<E[i]: choice.add(i) for time in range(1,len(choice)+1): #上げる因子 for P in cb(choice,time): X=set(); X.add(num) #遷移先決定 for index in P: Y=set() for x in X: for c in range(E[index]-H[index]): Y.add(x+(c+1)*base[index]) X=Y X.discard(num); cnt=1 nochange=set([i for i in range(len(E))]) for index in P: nochange.discard(index) for index in nochange: cnt*=H[index]+1; cnt%=MOD for next in X: DP[next]+=DP[num]*cnt; DP[next]%=MOD print(DP[-1])