Submission #198344

#	Time	Username	Problem	Language	Result	Execution time	Memory
198344		Malomalomalomalo	Tents (JOI18_tents)	C++14	100 / 100	743 ms	41064 KiB

tents

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int MOD = 1e9+7;

int mul(int x,int y){
	return (1LL * x * y) % MOD;
}

int add(int x,int y){
	int res = x + y;
	while(res >= MOD)res-=MOD;
	return res;
}

const int N = 3e3 + 5;
int dp[N][N];
bool vis[N][N];
int inv = (MOD+1)/2;

int gdp(int n, int m){
	if(n < 0 || m < 0)return 0;
	if(n == 0 || m == 0)return 1;
	if(!vis[n][m]){
		vis[n][m] = 1;	
		gadd(dp[n][m], mul(mul(m,add(m,MOD-1)),mul(gdp(n-1,m-2),inv)));
		gadd(dp[n][m], mul(mul(4,m),gdp(n-1,m-1)));
		gadd(dp[n][m], mul(mul(m, add(n,MOD-1)), gdp(n-2,m-1)));
		gadd(dp[n][m], gdp(n-1,m));
	}
	return dp[n][m];
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	cout << add(gdp(n,m),MOD-1) << '\n';
}

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