Submission #888180

#	Time	Username	Problem	Language	Result	Execution time	Memory
888180		Shayan86	Tents (JOI18_tents)	C++14	100 / 100	64 ms	72536 KiB

tents

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 3e3 + 50;
const ll Mod = 1e9 + 7;

ll n, m, dp[N][N], inv2;

ll power(ll a, ll b, ll md = Mod){
    ll ans = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) ans = ans * a % md;
    }
    return ans;
}

ll c2(ll x){
    return x * (x-1) % Mod * inv2 % Mod;
}

int main(){
    fast_io;

    inv2 = power(2, Mod-2);

    cin >> n >> m;

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) dp[i][0] = 1;
    for(int j = 1; j <= m; j++) dp[0][j] = 1;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = (dp[i-1][j] + 4 * dp[i-1][j-1] * j) % Mod;
            if(i > 1) dp[i][j] = (dp[i][j] + dp[i-2][j-1] * j * (i-1)) % Mod;
            if(j > 1) dp[i][j] = (dp[i][j] + dp[i-1][j-2] * c2(j)) % Mod;
        }
    }

    cout << (dp[n][m] - 1 + Mod) % Mod;

}

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