test/aoj/2335.test.cpp

Back to top page

• category: test/aoj
• View this file on GitHub
  • Last commit date: 2020-04-23 03:07:27+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335&lang=jp

Depends on

• math/Combination.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335&lang=jp"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

#define call_from_test
#include "../../math/Combination.cpp"
#undef call_from_test

int main() {
    init_combination(10000000);
    ll N, M, K;
    ll ans = 0;
    cin >> N >> M >> K;
    for(ll kn = 0; kn <= K; kn++) {
        ll km = K - kn;
        ll nowans = combination(N + M + 2 * K, N + 2 * kn);
        nowans *= combination(N + 2 * kn, kn) - combination(N + 2 * kn, kn - 1);
        nowans %= mod;
        nowans += mod;
        nowans %= mod;
        nowans *= combination(M + 2 * km, km) - combination(M + 2 * km, km - 1);
        nowans %= mod;
        nowans += mod;
        nowans %= mod;
        ans = (ans + nowans) % mod;
    }
    cout << ans << endl;
    return 0;
}

#line 1 "test/aoj/2335.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2335&lang=jp"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

#define call_from_test
#line 1 "math/Combination.cpp"

#line 3 "math/Combination.cpp"
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#endif
//BEGIN CUT HERE
vector<ll> inv, FactorialInv, Factorial;
ll beki(ll a, ll b){
    ll ret = 1 % mod;
    a %= mod;
    while(b) {
        if(b & 1LL) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void init_combination(ll MAX){
    Factorial.resize(MAX + 1);
    FactorialInv.resize(MAX + 1);
    inv.resize(MAX + 1);
    Factorial[0] = 1;
    inv[0] = 1;
    for(int i = 1; i <= MAX; i++){
        Factorial[i] = Factorial[i - 1] * i % mod;
    }
    FactorialInv[MAX] = beki(Factorial[MAX], mod - 2);
    for(ll i = MAX - 1; i >= 0; i--) {
        FactorialInv[i] = FactorialInv[i+1] * (i+1) % mod;
    }
    for(int i = 1; i <= MAX; i++) {
        inv[i] = FactorialInv[i] * Factorial[i-1] % mod;
    }
}
ll combination(ll a, ll b){
    if((a == b) || (b == 0)){
        return 1;
    }
    if(a < b) return 0;
    if(b < 0) return 0;
    ll ans = Factorial[a] * FactorialInv[b] % mod;
    ans = ans * FactorialInv[a - b] % mod;
    return ans;
}

//END CUT HERE
#ifndef call_from_test
int main() {
    return 0;
}
#endif
#line 9 "test/aoj/2335.test.cpp"
#undef call_from_test

int main() {
    init_combination(10000000);
    ll N, M, K;
    ll ans = 0;
    cin >> N >> M >> K;
    for(ll kn = 0; kn <= K; kn++) {
        ll km = K - kn;
        ll nowans = combination(N + M + 2 * K, N + 2 * kn);
        nowans *= combination(N + 2 * kn, kn) - combination(N + 2 * kn, kn - 1);
        nowans %= mod;
        nowans += mod;
        nowans %= mod;
        nowans *= combination(M + 2 * km, km) - combination(M + 2 * km, km - 1);
        nowans %= mod;
        nowans += mod;
        nowans %= mod;
        ans = (ans + nowans) % mod;
    }
    cout << ans << endl;
    return 0;
}

Back to top page