結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 2024-03-01 20:46:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 473 ms / 2,000 ms |
コード長 | 1,079 bytes |
コンパイル時間 | 140 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 77,076 KB |
最終ジャッジ日時 | 2024-09-29 13:15:52 |
合計ジャッジ時間 | 7,143 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
# これは難しい、1次元dp、dp[m]のパターン数# dp[1]=1, dp[2]=2, dp[3]=3のときdp[4]を考える# dp[4]となる集合は1111, 112, 13, 22, 4# 最初の数は4の約数であり、その最初の数で全要素を割ると、1111, 112, 13, 11, 1となる# 最初の数を引いた残りは3, 3, 3, 1, 0となる、これらは約数d-1# つまり最初の数が終わると約数d-1となるのでdp[d-1]を加算する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]M = int(input())dp = [0]*(max(M, 5)+1)mod = 10**9+7dp[0] = 0dp[1] = 1dp[2] = 2dp[3] = 3for i in range(4, max(M, 5)+1):divs = divisors(i)# dp[i]を作るときに{iそのもの}もできるのでcalc = 1for d in divs:calc += dp[d-1]calc %= moddp[i] = calc#print(dp[:10])ans = dp[M]%modprint(ans)