結果

問題 No.802 だいたい等差数列
ユーザー koi_kotyakoi_kotya
提出日時 2019-03-19 00:30:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,510 bytes
コンパイル時間 1,748 ms
コンパイル使用メモリ 167,816 KB
実行使用メモリ 33,920 KB
最終ジャッジ日時 2024-07-19 09:19:08
合計ジャッジ時間 4,142 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 26 ms
27,136 KB
testcase_11 AC 32 ms
33,280 KB
testcase_12 AC 34 ms
30,592 KB
testcase_13 AC 37 ms
32,640 KB
testcase_14 AC 37 ms
31,488 KB
testcase_15 AC 33 ms
29,184 KB
testcase_16 AC 37 ms
32,384 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 38 ms
33,920 KB
testcase_20 AC 42 ms
33,920 KB
testcase_21 AC 41 ms
33,920 KB
testcase_22 AC 38 ms
33,792 KB
testcase_23 AC 39 ms
33,792 KB
testcase_24 RE -
testcase_25 AC 30 ms
26,880 KB
testcase_26 AC 10 ms
10,368 KB
testcase_27 AC 37 ms
32,768 KB
testcase_28 AC 20 ms
17,408 KB
testcase_29 AC 41 ms
33,920 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 19 ms
17,408 KB
権限があれば一括ダウンロードができます

ソースコード

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() {
    int 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