結果
問題 | No.535 自然数の収納方法 |
ユーザー |
![]() |
提出日時 | 2020-04-10 12:04:19 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 791 ms / 2,000 ms |
コード長 | 780 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 79,140 KB |
最終ジャッジ日時 | 2024-09-14 21:22:39 |
合計ジャッジ時間 | 19,046 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesimport numpy as npMOD = 10 ** 9 + 7N = int(read())def update_dp(dp, x):""" a の分布が与えられる。a < b+x となる b の分布を返す """newdp = np.zeros_like(dp)newdp[0] = dp[:x].sum() % MODnewdp[1: N - x + 1] += dp[x:N]dp = newdpnp.cumsum(dp, out=dp)dp %= MODreturn dpnums = list(range(N-1))nums[0] = 1# A_N の分布から始めるdp = np.ones(N, np.int64)for x in nums:dp = update_dp(dp, x)answer = dp.sum()# 除外パターン:A_N=0 からはじめて N-1 に到達dp = np.zeros(N, np.int64)dp[0] = 1for x in nums:dp = update_dp(dp, x)answer -= dp[-1]print(answer % MOD)