Submission #127860

#	Time	Username	Problem	Language	Result	Execution time	Memory
127860		doowey	Tents (JOI18_tents)	C++14	100 / 100	327 ms	35960 KiB

tents

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 3005;
const int MOD = (int)1e9 + 7;

int mult(int a, int b){
    return (a * 1ll * b) % MOD;
}

void add(int &a, int b){
    a = (a + b) % MOD;
}

int dp[N][N];

int solve(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    dp[i][j] = 0;
    if(i == 0 || j == 0){
        dp[i][j] = 1;
    }
    else{
        add(dp[i][j], solve(i - 1, j));
        add(dp[i][j], mult(4 * j, solve(i - 1, j - 1)));
        if(j > 1) add(dp[i][j], mult(j * (j - 1) / 2, solve(i - 1, j - 2)));
        if(i > 1) add(dp[i][j], mult(mult(j, (i - 1)), solve(i - 2, j - 1)));
    }
    return dp[i][j];
}

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    for(int i = 0 ; i <= n; i ++ ){
        for(int j = 0 ; j <= m ; j ++ ){
            dp[i][j] = -1;
        }
    }
    cout << (solve(n, m) - 1 + MOD) % MOD;
    return 0;
}

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