Submission #529056

#	Time	Username	Problem	Language	Result	Execution time	Memory
529056		Haruto810198	Tents (JOI18_tents)	C++17	100 / 100	133 ms	71300 KiB

tents

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 3010;

int n, m;
int dp[MAX][MAX];
int C2[MAX];

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	FOR(i, 0, MAX-1, 1){
		C2[i] = i * (i-1) / 2;
	}

	FOR(i, 0, MAX-1, 1){
		dp[i][0] = dp[0][i] = 1;
		dp[i][1] = dp[1][i] = C2[i] + 4*i + 1;
	}
	
	FOR(ij, 4, 2*MAX-2, 1){
		FOR(i, 2, ij-2, 1){
			int j = ij - i;
			if(i >= MAX or j >= MAX) continue;
			dp[i][j] = C2[i] * dp[i-2][j-1] + i * (j-1) * dp[i-1][j-2] + 4 * i * dp[i-1][j-1] + dp[i][j-1];
			//if(i <= 4 and j <= 4) cerr<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
			dp[i][j] %= MOD;
		}
	}
	
	cin>>n>>m;
	int res = dp[n][m] - 1;
	if(res < 0) res += MOD;
	cout<<res<<'\n';
	/*	
	cerr<<"dp : "<<endl;
	FOR(i, 0, 4, 1){
		FOR(j, 0, 4, 1){
			cerr<<dp[i][j]<<"\t";
		}
		cerr<<endl;
	}
	cerr<<endl;
	*/
	return 0;

}

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