結果

問題 No.802 だいたい等差数列
コンテスト
ユーザー 👑 SPD_9X2
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

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)
0