Submission #237394

#	Time	Username	Problem	Language	Result	Execution time	Memory
237394		clairvoyant	Tents (JOI18_tents)	C++14	100 / 100	386 ms	59000 KiB

tents

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define all int i=0; i<n; i++
#define INF LLONG_MAX
#define Nirvana ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define mod 1000000007
#define ll long long int
#define int ll
#define T int t;cin>>t;while(t--)

int dp[3001][3001];

int rec(int i, int j){
	if(i<0 || j<0)return 0;
	if(i==0 || j==0)return 1;
	
	if(dp[i][j])return dp[i][j];
	
	dp[i][j] += (4*j*rec(i-1, j-1))%mod;
	dp[i][j]%=mod;
	dp[i][j] += (rec(i-1, j));
	dp[i][j]%=mod;
	dp[i][j] += (((j*(j-1))/2) * (rec(i-1, j-2)))%mod;
	dp[i][j]%=mod;
	dp[i][j] += (j*(i-1) * rec(i-2, j-1));
	dp[i][j]%=mod;
	
	return dp[i][j];
}
signed main(){
	Nirvana;
	int n,m;
	cin>>n>>m;
	
	cout<<(rec(n, m)-1 + mod)%mod<<endl;
}

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