結果
問題 |
No.802 だいたい等差数列
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-17 01:06:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 279 ms / 2,000 ms |
コード長 | 1,524 bytes |
コンパイル時間 | 394 ms |
コンパイル使用メモリ | 82,608 KB |
実行使用メモリ | 250,516 KB |
最終ジャッジ日時 | 2025-07-17 01:06:29 |
合計ジャッジ時間 | 9,360 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
""" https://yukicoder.me/problems/no/802 M-1個の隙間を、N+1個に分ける。 内、N-1個のバケットは、D1以上D2以下しか入れられない まず、全部D1入れてしまう. rem = M-1 - D1 * (N-1) 個を分けていく D2-D1 個を超える違反をするバケットがx個あるとすると... を包除原理 """ import sys from sys import stdin #modのn!と、n!の逆元を格納したリストを返す(拾いもの) #factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている #invsには↑の逆元が入っている def modfac(n, MOD): f = 1 factorials = [1] for m in range(1, n + 1): f *= m f %= MOD factorials.append(f) inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return factorials, invs def modnCr(n,r): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる) if r == 0: return 1 return fac[n] * inv[n-r] * inv[r] % mod mod = 10**9+7 fac,inv = modfac(2*10**6,mod) N,M,D1,D2 = map(int,input().split()) rem = M-1 rem -= D1 * (N-1) if rem < 0: print (0) sys.exit() ans = 0 morp = 1 for x in range(N): rem2 = rem - (D2-D1+1) * x if rem2 < 0: break now = modnCr(N-1,x) * modnCr(rem2+N,N) * morp % mod ans += now ans %= mod morp *= -1 # print (x, now) print (ans % mod)