結果
問題 |
No.802 だいたい等差数列
|
ユーザー |
![]() |
提出日時 | 2025-04-09 20:58:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,771 bytes |
コンパイル時間 | 143 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 81,140 KB |
最終ジャッジ日時 | 2025-04-09 21:00:45 |
合計ジャッジ時間 | 3,190 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
MOD = 10**9 + 7 def main(): import sys input = sys.stdin.read N, M, D1, D2 = map(int, input().split()) n = N - 1 if n == 0: print(M % MOD) return s_min = n * D1 if 1 + s_min > M: print(0) return s_max = min(n * D2, M - 1) if s_min > s_max: print(0) return L = D2 - D1 s_max_prim = s_max - s_min C = M - s_min max_n = s_max_prim + n fact_size = max(n + s_max_prim + 2, 10**6) # Precompute factorial and inverse factorial modulo MOD fact = [1] * (fact_size + 1) for i in range(1, fact_size + 1): fact[i] = fact[i-1] * i % MOD inv_fact = [1] * (fact_size + 1) inv_fact[fact_size] = pow(fact[fact_size], MOD-2, MOD) for i in range(fact_size-1, -1, -1): inv_fact[i] = inv_fact[i+1] * (i+1) % MOD def comb(a, b): if a < 0 or b < 0 or a < b: return 0 return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD ans = 0 L_plus_1 = L + 1 k_max = s_max_prim // L_plus_1 if L_plus_1 != 0 else s_max_prim for k in range(0, k_max + 1): T_k = s_max_prim - k * L_plus_1 if T_k < 0: break c_n_k = comb(n, k) if c_n_k == 0: continue current_Ck = C - k * L_plus_1 total_len = n + T_k c1 = comb(total_len, n) c2 = comb(total_len, n + 1) sum_terms = (current_Ck * c1) % MOD sum_terms = (sum_terms - (n * c2) % MOD) % MOD sign = (-1)**k term = sign * c_n_k * sum_terms term %= MOD ans = (ans + term) % MOD print(ans % MOD) if __name__ == "__main__": main()