Submission #46775

#	Time	Username	Problem	Language	Result	Execution time	Memory
46775		kyleliu	Tents (JOI18_tents)	C++14	100 / 100	238 ms	71460 KiB

tents

#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 3005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
ll mmul(ll a, ll b) { return (a*b)%MOD; }
ll madd(ll a, ll b) { return (a+b)%MOD; }
void up(ll &a, ll b) { a = madd(a, b); }
	
int N, M;
ll dp[MAXN][MAXN];
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> M >> N;
	
	for(int i=0; i<=M; i++) dp[i][0] = 1;
	for(int i=0; i<=N; i++) dp[0][i] = 1;
	for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) {
		up(dp[i][j], dp[i-1][j]);
		up(dp[i][j], mmul(mmul(4LL, j), dp[i-1][j-1]));
		if(i > 1) up(dp[i][j], mmul(mmul(i-1, j), dp[i-2][j-1]));
		if(j > 1) up(dp[i][j], mmul((((j-1LL)*j)/2LL)%MOD, dp[i-1][j-2]));
	}
	cout << madd(dp[M][N], MOD-1) << endl;

}

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