Submission #204194

#	Time	Username	Problem	Language	Result	Execution time	Memory
204194		theStaticMind	Tents (JOI18_tents)	C++14	100 / 100	384 ms	71160 KiB

tents

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int Q[3001][3001];

int dp(int x, int y){
	if(x < 0 || y < 0) return 0;
	if(x == 0 || y == 0) return Q[x][y] = 1;
	if(Q[x][y] != -1) return Q[x][y];
	int ret = 0;
	ret += dp(x - 1, y - 2) * ((y - 1) * y / 2) % modulo;
    ret += dp(x - 2, y - 1) * y * (x - 1) % modulo;
    ret %= modulo;
    ret += dp(x - 1, y - 1) * 4ll * y % modulo;
    ret += dp(x - 1, y) % modulo;

	return Q[x][y] = ret % modulo;

}

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n, m;
      cin >> n >> m;
      for(int i = 0; i <= n; i++){
      	for(int j = 0; j <= m; j++){
      		Q[i][j] = -1;
      	}
      }

      cout << (dp(n, m) - 1 + modulo) % modulo << endl;


}

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