結果

問題 No.802 だいたい等差数列
ユーザー koi_kotyakoi_kotya
提出日時 2019-03-19 00:24:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,501 bytes
コンパイル時間 2,106 ms
コンパイル使用メモリ 167,292 KB
実行使用メモリ 34,056 KB
最終ジャッジ日時 2023-09-26 15:01:26
合計ジャッジ時間 5,566 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,548 KB
testcase_01 AC 2 ms
7,488 KB
testcase_02 AC 2 ms
7,660 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 3 ms
7,492 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
7,764 KB
testcase_07 AC 2 ms
7,472 KB
testcase_08 AC 2 ms
7,476 KB
testcase_09 AC 2 ms
7,500 KB
testcase_10 AC 21 ms
32,112 KB
testcase_11 AC 25 ms
33,672 KB
testcase_12 AC 23 ms
32,732 KB
testcase_13 AC 25 ms
33,464 KB
testcase_14 AC 25 ms
32,992 KB
testcase_15 AC 24 ms
32,316 KB
testcase_16 AC 26 ms
33,308 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 26 ms
33,820 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 26 ms
34,056 KB
testcase_23 AC 27 ms
33,844 KB
testcase_24 RE -
testcase_25 AC 21 ms
32,040 KB
testcase_26 AC 10 ms
19,776 KB
testcase_27 AC 26 ms
33,452 KB
testcase_28 AC 16 ms
26,156 KB
testcase_29 WA -
testcase_30 AC 3 ms
7,728 KB
testcase_31 AC 2 ms
7,524 KB
testcase_32 AC 1 ms
4,380 KB
testcase_33 AC 15 ms
25,856 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 <= 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