답안 #110096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110096	2019-05-09T12:41:30 Z	Saboon	Tents (JOI18_tents)	C++14	100 / 100	197 ms	35728 KB

tents

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 3000 + 10;
const int mod = 1e9 + 7;
int dp[maxn][maxn];

int power(int a, int b){
	if (b == 0)
		return 1;
	int ret = power(a, b / 2);
	ret = 1ll * ret * ret % mod;
	if (b & 1)
		return 1ll * ret * a % mod;
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= max(n, m); i++)
		dp[i][0] = dp[0][i] = 1;
	int pw = power(2, mod - 2);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (i == 1){
				dp[i][j] = 4 * j + 1ll * j * (j - 1) % mod * pw % mod + 1;
				dp[i][j] %= mod;
				continue;
			}
			if (j == 1){
				dp[i][j] = 4 * i + 1ll * i * (i - 1) % mod * pw % mod + 1;
				dp[i][j] %= mod;
				continue;
			}
			dp[i][j] = dp[i - 1][j];
			dp[i][j] = (dp[i][j] + 4ll * dp[i - 1][j - 1] * j) % mod;
			dp[i][j] = (dp[i][j] + 1ll * dp[i - 1][j - 2] * j % mod * (j - 1) % mod * pw % mod) % mod;
			dp[i][j] = (dp[i][j] + 1ll * dp[i - 2][j - 1] * j % mod * (i - 1) % mod) % mod;
		}
	}
	cout << (dp[n][m] - 1 + mod) % mod << endl;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	1152 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	4 ms	1408 KB	Output is correct
6	Correct	4 ms	1280 KB	Output is correct
7	Correct	4 ms	1280 KB	Output is correct
8	Correct	4 ms	1408 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	4 ms	1664 KB	Output is correct
11	Correct	3 ms	1536 KB	Output is correct
12	Correct	9 ms	1920 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	1152 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	4 ms	1408 KB	Output is correct
6	Correct	4 ms	1280 KB	Output is correct
7	Correct	4 ms	1280 KB	Output is correct
8	Correct	4 ms	1408 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	4 ms	1664 KB	Output is correct
11	Correct	3 ms	1536 KB	Output is correct
12	Correct	9 ms	1920 KB	Output is correct
13	Correct	9 ms	7808 KB	Output is correct
14	Correct	3 ms	9600 KB	Output is correct
15	Correct	134 ms	32952 KB	Output is correct
16	Correct	14 ms	7936 KB	Output is correct
17	Correct	37 ms	12464 KB	Output is correct
18	Correct	39 ms	11768 KB	Output is correct
19	Correct	152 ms	34692 KB	Output is correct
20	Correct	124 ms	29156 KB	Output is correct
21	Correct	98 ms	21448 KB	Output is correct
22	Correct	84 ms	22164 KB	Output is correct
23	Correct	50 ms	19704 KB	Output is correct
24	Correct	197 ms	35728 KB	Output is correct
25	Correct	133 ms	30968 KB	Output is correct
26	Correct	151 ms	33772 KB	Output is correct
27	Correct	177 ms	35168 KB	Output is correct