結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー FromBooska
提出日時 2023-05-27 10:31:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,562 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 81,728 KB
実行使用メモリ 141,040 KB
最終ジャッジ日時 2024-12-25 20:25:54
合計ジャッジ時間 51,371 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 6 WA * 28 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Nを素因数分解
# たとえば2**3が入っていれば、最後は2**3項が必要
# それまでは2**1, 2**2という2つのチョイスがあるので2**2で4通りある
# 逆から考えられないか
# Nを1以外の約数で割って、1までもっていく方法の数
# メモ化dfsなら実装できるが間に合わないか
# dpでできれば間に合うだろう
# 10**12でも素因数の数は忘れたけど少ない、たしか数十個ぐらい
# まずメモ化dfsでやってみるか
# いや、Nの約数にしか止まらないからそこでのdpとしたらどうだ

N = int(input())

def divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N_divs = divisors(N)
N_divs_set = set(N_divs)
L = len(N_divs)
dic = {}
for i in range(L):
    dic[N_divs[i]] = i


mod = 998244353

# Nの約数を大きい方から1まで並べるのはうまくいかないので小さい方からやる
# dp[i]パターン数

dp = [0]*L
dp[0] = 1 

for i in range(L-1):
    num = N_divs[i]
    #print(num)
    for d in N_divs[1:L-1]:
        #print('i', i, 'num', num, 'd', d, 'num*d', num*d, num*d in N_divs)
        if num%d != 0 and num*d in N_divs:
            dp[dic[num*d]] += dp[i]
            dp[dic[num*d]] %= mod
    dp[L-1] += dp[i]
    dp[L-1] %= mod
    #print(num, dp)

ans = dp[L-1]%mod
print(ans)
0