oj.uz

답안 #891950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891950 2023-12-24T13:47:01 Z josanneo22 캥거루 (CEOI16_kangaroo) C++17
100 / 100
 29 ms 39516 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int mod = 1E9 + 7;
const int _N = 2500;
i64 dp[_N][_N];
/*
    dp[i][j] = 已经排了i个数,连通块=j
    放入某个块: dp[i][j]=dp[i-1][j]*j
    新加一个块: dp[i][j]=dp[i-1][j-1]*j
    合并两个块: dp[i][j]=dp[i-1][j+1]*j
    若i==A || i==B, 我们不可以用来合并而且也不能随便加入块:
        dp[i][j] = dp[i-1][j]只能加入最后一个块/最前一个块
        dp[i][j] = dp[i-1][j-1]放上最后一个块/最前一个块
*/
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N, A, B; cin >> N >> A >> B;
    dp[1][1] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == A || i == B) {
                dp[i][j] += dp[i - 1][j];
                dp[i][j] += dp[i - 1][j - 1];
                dp[i][j] %= mod;
                continue;
            }
            int cnt = (i > A) + (i > B);
            dp[i][j] += dp[i - 1][j - 1] * (j - cnt);//不能放头，不能放尾
            dp[i][j] %= mod;
            dp[i][j] += dp[i - 1][j + 1] * j;
            dp[i][j] %= mod;
        }
    }
    cout << dp[N][1] << '\n';
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1392 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1488 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1368 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1392 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1488 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1368 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 4 ms 6236 KB Output is correct
22 Correct 5 ms 7004 KB Output is correct
23 Correct 5 ms 7768 KB Output is correct
24 Correct 29 ms 39392 KB Output is correct
25 Correct 28 ms 39516 KB Output is correct
26 Correct 28 ms 39512 KB Output is correct
27 Correct 29 ms 39132 KB Output is correct
28 Correct 20 ms 23900 KB Output is correct