Submission #1091697

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091697	2024-09-21T20:02:41 Z	4QT0R	Tents (JOI18_tents)	C++17	100 / 100	146 ms	70740 KB

tents

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

ll mod=1e9+7;

ll mult(ll a, ll b){
	return (a*b)%mod;
}
ll chose(ll x){
	return ((x*(x-1))/2)%mod;
}

ll dp[3003][3003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll n,m;
	cin >> n >> m;
	dp[0][0]=1;
	for (ll i = 1; i<=n; i++)dp[i][0]=1;
	for (ll i = 1; i<=m; i++)dp[0][i]=1;
	for (ll i = 1; i<=n; i++){
		for (ll j = 1; j<=m; j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]+=mult(4*j,dp[i-1][j-1]);
			if (j>=2)dp[i][j]+=mult(chose(j),dp[i-1][j-2]);
			if (i>=2)dp[i][j]+=mult(mult(i-1,j),dp[i-2][j-1]);
			dp[i][j]=dp[i][j]%mod;
		}
	}
	cout << (dp[n][m]+mod-1)%mod << '\n';
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	0 ms	604 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	860 KB	Output is correct
8	Correct	1 ms	1484 KB	Output is correct
9	Correct	0 ms	860 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	2 ms	2140 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	0 ms	604 KB	Output is correct
6	Correct	1 ms	1372 KB	Output is correct
7	Correct	1 ms	860 KB	Output is correct
8	Correct	1 ms	1484 KB	Output is correct
9	Correct	0 ms	860 KB	Output is correct
10	Correct	1 ms	1884 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	2 ms	2140 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	3 ms	9820 KB	Output is correct
15	Correct	97 ms	55148 KB	Output is correct
16	Correct	6 ms	4184 KB	Output is correct
17	Correct	22 ms	12884 KB	Output is correct
18	Correct	28 ms	16980 KB	Output is correct
19	Correct	111 ms	63032 KB	Output is correct
20	Correct	91 ms	51028 KB	Output is correct
21	Correct	59 ms	33872 KB	Output is correct
22	Correct	59 ms	35408 KB	Output is correct
23	Correct	35 ms	26960 KB	Output is correct
24	Correct	146 ms	70740 KB	Output is correct
25	Correct	116 ms	61108 KB	Output is correct
26	Correct	127 ms	66640 KB	Output is correct
27	Correct	145 ms	68944 KB	Output is correct