54942023-06-30 16:07:21111Játék (50 pont)cpp14Elfogadva 50/5068ms7836 KiB
/*

5 10
    1     0     0     0     0     0     0     0     0     0
    1     1     0     0     0     0     0     0     0     0
    2     2     1     0     0     0     0     0     0     0
    5     5     3     1     0     0     0     0     0     0
   14    14     9     4     1     0     0     0     0     0
   42    42    28    14     5     1     0     0     0     0
  132   132    90    48    20     6     1     0     0     0
  429   429   297   165    75    27     7     1     0     0
 1430  1430  1001   572   275   110    35     8     1     0
 4862  4862  3432  2002  1001   429   154    44     9     1
1001

1001 = 572 * 1 + 275 * 1 + 110 * 1   + 35 * 1  + 8 * 1  + 1 * 1

1001 = 297 * 1 + 165 * 2 + 75  * 3   + 27 * 4  + 7 * 5  + 1 * 6

1001 = 132 * 1 + 90  * 3 + 48  * 6   + 20 * 10 + 6 * 15 + 1 * 21

1001 = 42  * 1 + 42  * 4 + 28  * 10  + 14 * 20 + 5 * 35 + 1 * 56

1001 =           14  * 5 + 14  * 15  +  9 * 35 + 4 * 70 + 1 * 126

1001 =                      5  * 20  +  5 * 55 + 3 * 125 + 1 *251

1001 =                                  2 * 75 + 2 * 200 + 1 * 451

1001 =                                           1 * 275 + 1 * 726

1001 =                                                     1 * 1001

X[B][C] = X[B - 1][C - 1] + X[B + 1][C]

X[B][C] = X[B - 1][C - 1] + X[B][C - 1] + X[B + 1][C - 1] + ... + (X[C - 1][C - 1] = 1)  // hockey stick

X[B][C] = bin(0, C - B - 1) + bin(1, C - B) + ... + bin(B, C - B + B - 1) - bin(0, C - B + B - 1) + bin(B + 1, C - B + B) - bin(1, C - B + B) + bin(B + 2, C + 1) - bin(2, C + 1)

*/

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

#define int long long

#define MOD 1000000007

int fac_mod(int x, int m = MOD) {
    static vector<int> v = {1};
    while (v.size() - 1 < x) {
        v.push_back(v.back() * v.size() % m);
    }
    return v[x];
}

int pow_mod(int x, int p, int m = MOD) {
    int r = 1;
    while (p > 0) {
        if (p % 2 == 1) {
            r *= x;
            r %= m;
        }
        p /= 2;
        x *= x;
        x %= m;
    }
    return r;
}

int inv_mod(int x, int m = MOD) {
    return pow_mod(x, m - 2);
}

int bin_mod(int n, int k, int m = MOD) {
    return fac_mod(n) * inv_mod(fac_mod(n - k)) % m * inv_mod(fac_mod(k)) % m;
}

signed main() {
	int B, C;
	cin >> B >> C;
	int ans = 0;
	for (int i = 0; i < B; i++) {
		ans += bin_mod(C - B - 1 + i, i);
		ans %= MOD;
	}
	for (int i = 0; i < C - B - 1; i++) {
		ans += bin_mod(C - 1 + i, B + i) - bin_mod(C - 1 + i, i) + MOD;
		ans %= MOD;
	}
	cout << ans << endl;
    return 0;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/03ms2036 KiB
3Elfogadva2/23ms2224 KiB
4Elfogadva3/32ms2344 KiB
5Elfogadva3/33ms2472 KiB
6Elfogadva3/33ms2728 KiB
7Elfogadva3/33ms2928 KiB
8Elfogadva3/34ms3292 KiB
9Elfogadva3/34ms3488 KiB
10Elfogadva3/34ms3448 KiB
11Elfogadva3/34ms3640 KiB
12Elfogadva3/38ms3820 KiB
13Elfogadva3/310ms4276 KiB
14Elfogadva3/368ms7836 KiB
15Elfogadva3/328ms5000 KiB
16Elfogadva3/352ms5880 KiB
17Elfogadva3/346ms6100 KiB
18Elfogadva3/348ms6384 KiB
19Elfogadva3/354ms6544 KiB