結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-05 23:11:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 678 ms / 3,000 ms |
コード長 | 2,120 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 183,860 KB |
最終ジャッジ日時 | 2024-10-07 04:44:08 |
合計ジャッジ時間 | 8,847 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
s = str(input())n = len(s)#print(n)mod = 10**9+7dp = [[[0, 0] for _ in range(100)] for _ in range(n+1)]dp[0][0][0] = 1for i in range(n):for j in range(100):for k in range(2):nd = int(s[i])for d in range(10):ni = i+1if i == 0:nj = d%100else:nj = (j*d)%100nk = kif k == 0:if d > nd:continueelif d < nd:nk = 1else:passif d != 0:dp[ni][nj][nk] += dp[i][j][k]%mod#print(dp)#print((dp[n][0][0]+dp[n][0][1])%mod)ans = (dp[n][0][0]+dp[n][0][1])%modN = 10**6mod = 10**9+7fac = [1]*(N+1)finv = [1]*(N+1)for i in range(N):fac[i+1] = fac[i] * (i+1) % modfinv[-1] = pow(fac[-1], mod-2, mod)for i in reversed(range(N)):finv[i] = finv[i+1] * (i+1) % moddef cmb1(n, r, mod):if r <0 or r > n:return 0r = min(r, n-r)return fac[n] * finv[r] * finv[n-r] % moddef prm1(n, r, mod):if r <0 or r > n:return 0return fac[n] * finv[n-r] % modtable9 = [0]*(10**5+50)table9[0] = 1for i in range(1, 10**5+50):table9[i] = table9[i-1]*9table9[i] %= modtable4 = [0]*(10**5+50)table4[0] = 1for i in range(1, 10**5+50):table4[i] = table4[i-1]*4table4[i] %= modtable5 = [0]*(10**5+50)table5[0] = 1for i in range(1, 10**5+50):table5[i] = table5[i-1]*5table5[i] %= modtable8 = [0]*(10**5+50)table8[0] = 1for i in range(1, 10**5+50):table8[i] = table8[i-1]*8table8[i] %= modfor i in range(n):if i < 3:continuetemp = table9[i]# 5:0, 2, 6:0temp -= table4[i]# 5:0, 2, 6:1temp -= i*2*table4[i-1]# 5:1, 2, 6:0temp -= i*1*table4[i-1]# 5:1, 2, 6:1temp -= cmb1(i, 2, mod)*2*2*table4[i-2]#print(i, temp)a = table9[i]-table8[i]-i*table8[i-1]b = table9[i]-table5[i]-i*2*table5[i-1]ans += a+b-tempprint(ans%mod)