답안 #824729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
824729 2023-08-14T09:13:56 Z Dec0Dedd Tents (JOI18_tents) C++14
100 / 100
192 ms 58972 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e3+10;
const int MOD = 1e9+7;

ll dp[N][N], n, m;

// From (N, M) we can:
// 1) do nothing and go to (N-1, M)
// 2) put random tent in N-th row in any direction 4*M * (N-1, M-1)
// 3) put 2 tents in N-th row in M*(M-1)/2 * (N-1, M-2)
// 4) put 2 tents in same column s.t. on is in N-th row in M*(N-1)*(N-2, M-1) ways

ll solve(ll n, ll m) {
    if (n <= 0 || m <= 0) return 1;
    if (dp[n][m] > 0) return dp[n][m];
    ll res=solve(n-1, m);
    (res+=4*m*solve(n-1, m-1))%=MOD;
    (res+=m*(m-1)/2*solve(n-1, m-2))%=MOD;
    (res+=m*(n-1)*solve(n-2, m-1))%=MOD;
    return dp[n][m]=res;
}

int main() {
    cin>>n>>m;
    cout<<solve(n, m)-1<<"\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 3 ms 2004 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 3 ms 2004 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 133 ms 47368 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 13 ms 6816 KB Output is correct
18 Correct 35 ms 13572 KB Output is correct
19 Correct 148 ms 53324 KB Output is correct
20 Correct 114 ms 42196 KB Output is correct
21 Correct 66 ms 25496 KB Output is correct
22 Correct 74 ms 30812 KB Output is correct
23 Correct 51 ms 26444 KB Output is correct
24 Correct 189 ms 58972 KB Output is correct
25 Correct 136 ms 49376 KB Output is correct
26 Correct 158 ms 54696 KB Output is correct
27 Correct 192 ms 57176 KB Output is correct