Submission #370922

#	Time	Username	Problem	Language	Result	Execution time	Memory
370922		79brue	Tents (JOI18_tents)	C++14	100 / 100	247 ms	71020 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y&1) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp*tmp%MOD;
}

int n, m;
ll fact[10002];
ll factInv[10002];
ll arr[10002];
ll DP[3002][3002];
ll ans;

ll comb(ll x, ll y){
    if(x<y) return 0;
    return fact[x] * factInv[y] % MOD * factInv[x-y] % MOD;
}

int main(){
    scanf("%d %d", &n, &m);

    fact[0] = 1;
    for(int i=1; i<=10000; i++) fact[i] = fact[i-1] * i % MOD;
    factInv[10000] = mpow(fact[10000], MOD-2);
    for(int i=9999; i>=0; i--) factInv[i] = factInv[i+1] * (i+1) % MOD;

    for(int i=0; i<=3000; i++){
        arr[i] = 1;
        for(int j=0; j<i; j++){
            arr[i] = arr[i] * comb(2*(i-j), 2) % MOD;
        }
    }

    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            if(i==0 || j==0){
                DP[i][j] = 1;
                continue;
            }
            DP[i][j] = DP[i-1][j];
            DP[i][j] += DP[i-1][j-1] * j * 4;
            DP[i][j] %= MOD;
        }
    }

    for(int i=0; i<=n; i++){
        for(int j=0; j<=m; j++){
            if(i+2*j > n || j+2*i > m) continue;
            ll c1 = comb(n, i) * comb(m, j) % MOD;
            ll c2 = comb(n-i, j+j) * comb(m-j, i+i) % MOD;
            ll c3 = arr[i] * arr[j] % MOD;
            ll c4 = DP[n-i-j-j][m-j-i-i];
            ans += c1 * c2 % MOD * c3 % MOD * c4 % MOD;
            ans %= MOD;
        }
    }
    printf("%lld", ans-1);
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52