結果
問題 | No.802 だいたい等差数列 |
ユーザー |
![]() |
提出日時 | 2019-03-17 22:47:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 1,686 bytes |
コンパイル時間 | 1,461 ms |
コンパイル使用メモリ | 160,880 KB |
実行使用メモリ | 52,480 KB |
最終ジャッジ日時 | 2024-07-08 01:10:25 |
合計ジャッジ時間 | 6,710 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;typedef long long ll;typedef vector<int> vi;#define pb push_back#define eb emplace_back#define mp make_pair#define fi first#define se second#define rep(i,n) rep2(i,0,n)#define rep2(i,m,n) for(int i=m;i<(n);i++)#define ALL(c) (c).begin(),(c).end()#define dump(x) cout << #x << " = " << (x) << endlconstexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }template<class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {os<<"("<<p.first<<","<<p.second<<")";return os;}template<class T>ostream& operator<<(ostream& os, const vector<T>& v) {os<<"{";rep(i, v.size()) {if (i) os<<",";os<<v[i];}os<<"}";return os;}const ll MOD = 1000000007;const int MX = 2e6;ll inv[MX], fact[MX], ifact[MX];void init() {inv[1] = 1;for (int i = 2; i < MX; ++i) {inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;}fact[0] = ifact[0] = 1;for (int i = 1; i < MX; ++i) {fact[i] = fact[i-1] * i % MOD;ifact[i] = ifact[i-1] * inv[i] % MOD;}}ll comb(int n, int r) {if (n < 0 || r < 0 || r > n) return 0;return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;}int main() {int N, M; ll D1, D2;cin >> N >> M >> D1 >> D2;--M;if ((N - 1) * D1 > M) {puts("0");return 0;}init();M -= (N - 1) * D1;ll D = D2 - D1;vector<ll> way(N + 1);for (int i = N-1; i >= 0; --i) {if (i * (D + 1) > M) {continue;}int m = M - i * (D + 1);way[i] = comb(m + N, N) * comb(N-1, i) % MOD;way[i] -= way[i+1];if (way[i] < 0) way[i] += MOD;}cout << way[0] << endl;return 0;}