結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 2023-05-26 22:21:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 929 ms / 3,000 ms |
コード長 | 2,873 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 77,904 KB |
最終ジャッジ日時 | 2024-12-25 07:51:33 |
合計ジャッジ時間 | 11,327 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#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:breakif CheckNumber%Soinsu!=0:continueSoinsuCount=0while CheckNumber%Soinsu==0:SoinsuCount+=1;CheckNumber//=SoinsuSoinsuList.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:breakif x%i==0:Ldiv.append(i)if i**2!=x:Udiv.append(x//i)return Ldiv+Udiv[::-1]from itertools import combinations as cbgcd=lambda x,y: gcd(y,x%y) if x%y else yN=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=YX.discard(num); cnt=1nochange=set([i for i in range(len(E))])for index in P: nochange.discard(index)for index in nochange: cnt*=H[index]+1; cnt%=MODfor next in X: DP[next]+=DP[num]*cnt; DP[next]%=MODprint(DP[-1])