結果

問題 No.802 だいたい等差数列
ユーザー koi_kotya
提出日時 2019-03-19 01:21:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,509 bytes
コンパイル時間 1,355 ms
コンパイル使用メモリ 167,760 KB
実行使用メモリ 33,920 KB
最終ジャッジ日時 2024-07-19 19:31:42
合計ジャッジ時間 3,022 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll const mod = 1e9+7;

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

const int MAX_N = 1300010;
ll fact[MAX_N],fact_inv[MAX_N],inv[MAX_N];

ll pow(ll a,ll b) {
    ll ret;
    if (b == 0) ret = 1;
    else if (b == 1) ret = a;
    else {
        ll c = pow(a,b/2);
        if (b%2) ret = (c*c)%mod*a%mod;
        else ret = c*c%mod;
    }
    return ret;
}

void create_table(int n) {
    fact[0] = 1;fact[1] = 1;
    for (int i = 2;i <= n;++i) fact[i] = fact[i-1]*i%mod;
    fact_inv[n] = pow(fact[n],mod-2);
    for (int i = n;i > 0;--i) fact_inv[i-1] = fact_inv[i]*i%mod;
    for (int i = 1;i <= n;++i) inv[i] = fact_inv[i]*fact[i-1]%mod;
}

ll combi(ll a, ll b) {
    return fact[a]*fact_inv[b]%mod*fact_inv[a-b]%mod;
}

int main() {
    ll n,m,c,d;
    cin >> n >> m >> c >> d;
    if (c*(n-1)+1 > m) {
        cout << 0 << endl;
        exit(0);
    }
    create_table(n+m);
    ll ans = 0;
    m -= c*(n-1)+1;
    d -= c-1;
    for (int i = 0;i <= min(n-1,m/d);++i) {
        ll s = combi(m+n-d*i,n)*combi(n-1,i)%mod;
        if (i%2) ans -= s;
        else ans += s;
        ans %= mod;
    }
    cout << (ans+mod)%mod << endl;
}
0