제출 #1033939

#제출 시각아이디문제언어결과실행 시간메모리
1033939coldbr3wTents (JOI18_tents)C++14
0 / 100
2076 ms2016 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 480;
ll gt[N];
ll n,m;
ll bpow(ll a, ll b){
    if(b == 0) return 1;
    ll res = bpow(a , b/2);
    if(b&1) return a * res % mod * res % mod;
    return res * res % mod;
}
ll C(ll k, ll n){
    if(k > n || min(n, k) < 0) return 0;
    ll a = gt[n], b = gt[n - k] * gt[k] % mod;
    return a * bpow(b, mod - 2) % mod;
}
void to_thic_cau(){
    cin >> n >> m;
    ll res = 0;
    for(int i = 0; i <= n;i++){ // fix i hang dung 2 con -> con m - 2 * i cot
        for(int j = 0; j <= m;j++){
            ll pi = 1, pj = 1;
            for(int k = 1; k <= i;k++) pi = (pi * C(2, m - 2 * (k - 1))) % mod;
            for(int k = 1; k <= j;k++) pj = (pj * C(2, n - i - 2 * (k - 1))) % mod;
            ll x = n - 2 * j - i, y = m - 2 * i - j;
            ll d = 0;
            for(int k = 0; k <= min(x, y);k++) d = (d + (C(k, x) * C(k, y) % mod) * (gt[k] * bpow(4 , k) % mod) % mod) % mod;
            res = (res + ((C(i, n) * pi % mod) * (C(j, m - 2 * i) * pj % mod) % mod) * d % mod) % mod;
        }
    }
    cout << (res + mod - 1) % mod << '\n';
}
 
signed main(){
    gt[0] = 1;
    for(int i = 1; i < N;i++) {
        gt[i] = (gt[i-1] * i) % mod;
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...