Submission #887736

#	Time	Username	Problem	Language	Result	Execution time	Memory
887736		vjudge1	Tents (JOI18_tents)	C++17	100 / 100	23 ms	504 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
const int mxn=3e3+2,M=1e9+7;
int n,m;
ll dp[3][mxn];
int main(){
	cin>>n>>m;
	for(int i=0;i<=m;i++){
		dp[0][i]=1;
	}
	dp[1][0]=dp[2][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ll x1=(j>1)?(j*(j-1))/2*dp[(i+2)%3][j-2]:0;
			ll x2=(i>1)?j*(i-1)*dp[(i+1)%3][j-1]:0;
			ll x3=j*4*dp[(i+2)%3][j-1];
			ll x4=dp[(i+2)%3][j];
			dp[i%3][j]=(x1+x2+x3+x4)%M;
			//cout<<dp[i%3][j]<<" ";
		}
		//cout<<endl;
	}
	cout<<dp[n%3][m]-1<<endl;
}

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