oj.uz

Submission #414912

# Submission time Handle Problem Language Result Execution time Memory
414912 2021-05-31T10:35:22 Z Pro_ktmr Tents (JOI18_tents) C++17
100 / 100
 444 ms 88500 KB 
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

template<typename T>
T power(T x, long long n, const T &m){
    if(n == 0) return 1;
    if(n == 1) return x;
    T tmp = power(x, n/2, m);
    if(n%2 == 0) return tmp * tmp % m;
    else return tmp * tmp % m * x % m;
}

template<typename T>
T inverse(T x, const T &m){
    return power(x, m-2, m);
}

struct Combination{

    int N;
    long long M;
    vector<long long> f, i;
public:
    void init(int n, long long m){
        N = n; M = m;
        f.resize(N+1); f[0] = 1;
        i.resize(N+1); i[0] = 1;
        for(long long j=1; j<=N; j++){
            f[j] = f[j-1]*j%M;
            i[j] = inverse(f[j], M);
        }
    }
    long long fact(int n){
        return f[n];
    }
    long long C(int n, int r){
        return f[n] * i[r] % M * i[n-r] % M;
    }
    long long P(int n, int r){
        return f[n] * i[n-r] % M;
    }
};

ll H, W;
Combination comb;

ll memo[3001][3001] ={};
ll calc(ll w, ll n){
    if(n == 0) return 1;
    if(memo[w][n] != 0) return memo[w][n];
    return memo[w][n] = comb.C(w, 2) * calc(w-2, n-1) % MOD;
}

ll dp[3001][3001] ={};
ll solve(ll w, ll h){
    if(w == 0 || h == 0) return 1;
    if(dp[w][h] != 0) return dp[w][h];
    return dp[w][h] = (solve(w-1, h) + solve(w-1,h-1)*h*4) % MOD;
}

ll ans = 0;

signed main(){
    cin >> H >> W;
    comb.init(3000, MOD);
    for(ll ew=0; ew*2<=W && ew<=H; ew++){
        for(ll ns=0; ew*2+ns<=W && ew+ns*2<=H; ns++){
            ll tmp = comb.C(H, ew);
            tmp *= calc(H-ew, ns);
            tmp %= MOD;
            tmp *= comb.i[ns];
            tmp %= MOD;
            tmp *= comb.P(W, ns);
            tmp %= MOD;
            tmp *= calc(W-ns, ew);
            tmp %= MOD;
            tmp *= solve(W-ew*2-ns, H-ew-ns*2);
            tmp %= MOD;
            ans += tmp;
            //cout << tmp << endl;
        }
    }
    cout << (ans-1+MOD) % MOD << endl;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 2224 KB Output is correct
6 Correct 4 ms 1740 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 1228 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 5 ms 2380 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 7 ms 3444 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 2224 KB Output is correct
6 Correct 4 ms 1740 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 1228 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 5 ms 2380 KB Output is correct
11 Correct 3 ms 1612 KB Output is correct
12 Correct 7 ms 3444 KB Output is correct
13 Correct 7 ms 7852 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 247 ms 61856 KB Output is correct
16 Correct 18 ms 12620 KB Output is correct
17 Correct 64 ms 28268 KB Output is correct
18 Correct 65 ms 24124 KB Output is correct
19 Correct 296 ms 69204 KB Output is correct
20 Correct 240 ms 59712 KB Output is correct
21 Correct 162 ms 46884 KB Output is correct
22 Correct 150 ms 41744 KB Output is correct
23 Correct 41 ms 17232 KB Output is correct
24 Correct 444 ms 88500 KB Output is correct
25 Correct 305 ms 72304 KB Output is correct
26 Correct 352 ms 79160 KB Output is correct
27 Correct 401 ms 86916 KB Output is correct