Submission #1349711

#TimeUsernameProblemLanguageResultExecution timeMemory
1349711jumpTents (JOI18_tents)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int long long
int dp[3010][3010];
int pref[3010][3010];
int pref2[3010][3010];
int n,m;
int MOD=1e9+7;
signed main() {
	std::cin >> n >> m;
	int sum=0;
	for(int i=0;i<=n+1;i++)pref[i][0]=1,pref[i][1]=1;
	for(int j=0;j<=m+1;j++)pref[0][j]=1,pref[1][j]=1;
	pref[0][0]=1;
	pref[0][1]=1;
	pref[1][0]=1;
	pref[1][1]=1;
	for(int i=2;i<=n+1;i++){
		for(int j=2;j<=m+1;j++){
			dp[i][j]=(4*pref[i-1][j-1])+((i-2)*pref[i-2][j-1])+((j-2)*pref[i-1][j-2]);
			dp[i][j]%=MOD;
			pref[i][j]=dp[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
			sum+=dp[i][j];
			//std::cout << dp[i][j] << ',' << pref[i][j] << ' ' << (4*pref[i-1][j-1]) << ' ' <<((i-2)*pref[i-2][j-1])<< ' ' <<((j-2)*pref[i-1][j-2])<< ' ' <<'|';
		}
		//std::cout << '\n';
	}
	std::cout << pref[n+1][m+1]-1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...