oj.uz

Submission #964083

# Submission time Handle Problem Language Result Execution time Memory
964083 2024-04-16T09:55:34 Z LucaIlie Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 120 ms 63056 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;
const int MOD = 1e9 + 7;

struct ZP {
    int x;

    ZP operator + ( ZP a ) {
        return { (x + a.x) % MOD };
    }

    void operator += ( ZP a ) {
        x = (x + a.x) % MOD;
    }

    ZP operator * ( ZP a ) {
        return { (int)((long long)x * a.x % MOD) };
    }

    ZP operator * ( int a ) {
        return { (int)((long long)x * a % MOD) };
    }

    void operator = ( int a ) {
        x = a;
    }

    void out() {
        cout << x << "\n";
    }
};


ZP dp[MAX_N + 1][MAX_N + 1][2][2];

int main() {
    int n, s, f;

    cin >> n >> s >> f;
    if ( s > f )
        swap( s, f );

    if ( s == 1 ) {
        if ( f == 2 )
            dp[3][1][1][1] = 1;
        dp[2][0][1][0] = 1;
    } else
        dp[1][0][0][0] = 1;

    int p = 2;
    for ( int i = 0; i < s - 1; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * (mx * 2 + 2);
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
        }
        if ( i == 0 && s > 1 )
            p--;
        p++;
    }
    for ( int mx = 0; mx <= n; mx++ ) {
        dp[s][mx][0][0] = dp[s - 1][mx][0][0];
        dp[s][mx][0][1] = dp[s - 1][mx][0][1];
        dp[s][mx][1][0] = dp[s - 1][mx][1][0];
        dp[s][mx][1][1] = dp[s - 1][mx][1][1];
    }

    for ( int i = s; i < f - 1; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * (mx * 2 + 1);
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][0][0];

            dp[i + 1][mx][1][0] += dp[i][mx][1][0] * (mx * 2 + 1);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][1][0] * (p - 1 - mx * 2);
        }
        if ( s == 1 && i == s )
            p--;
        p++;
    }
    for ( int mx = 0; mx <= n; mx++ ) {
        dp[f][mx][0][0] = dp[f - 1][mx][0][0];
        dp[f][mx][0][1] = dp[f - 1][mx][0][1];
        dp[f][mx][1][0] = dp[f - 1][mx][1][0];
        dp[f][mx][1][1] = dp[f - 1][mx][1][1];
    }

    for ( int i = f; i < n; i++ ) {
        for ( int mx = 0; mx <= n; mx++ ) {
            dp[i + 1][mx][0][0] += dp[i][mx][0][0] * mx * 2;
            dp[i + 1][mx + 1][0][0] += dp[i][mx][0][0] * (p - 2 - mx * 2);
            dp[i + 1][mx + 1][1][0] += dp[i][mx][0][0];
            dp[i + 1][mx + 1][0][1] += dp[i][mx][0][0];

            dp[i + 1][mx][1][0] += dp[i][mx][1][0] * mx * 2;
            dp[i + 1][mx + 1][1][0] += dp[i][mx][1][0] * (p - 1 - mx * 2);
            dp[i + 1][mx + 1][1][1] += dp[i][mx][1][0];

            dp[i + 1][mx][0][1] += dp[i][mx][0][1] * mx * 2;
            dp[i + 1][mx + 1][0][1] += dp[i][mx][0][1] * (p - 1 - mx * 2);
            dp[i + 1][mx + 1][1][1] += dp[i][mx][0][1];

            dp[i + 1][mx][1][1] += dp[i][mx][1][1] * mx * 2;
            dp[i + 1][mx + 1][1][1] += dp[i][mx][1][1] * (p - mx * 2);
        }
        if ( f == 2 && i == f )
            p--;
        p++;
    }


    ZP ans;
    if ( n % 2 == 0 )
        ans = dp[n][(n - 2) / 2][0][1] + dp[n][(n - 2) / 2][1][0];
    else
        ans = dp[n][n - 2 - (n - 2) / 2][1][1] + dp[n][(n - 2) / 2][0][0];

    ans.out();

    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 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 1 ms 632 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 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 1 ms 632 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct
13 Correct 3 ms 1628 KB Output is correct
14 Correct 1 ms 1720 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 2 ms 1724 KB Output is correct
17 Correct 2 ms 1628 KB Output is correct
18 Correct 1 ms 1464 KB Output is correct
19 Correct 2 ms 1628 KB Output is correct
20 Correct 2 ms 1884 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 2484 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 1 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 1 ms 632 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct
13 Correct 3 ms 1628 KB Output is correct
14 Correct 1 ms 1720 KB Output is correct
15 Correct 2 ms 2136 KB Output is correct
16 Correct 2 ms 1724 KB Output is correct
17 Correct 2 ms 1628 KB Output is correct
18 Correct 1 ms 1464 KB Output is correct
19 Correct 2 ms 1628 KB Output is correct
20 Correct 2 ms 1884 KB Output is correct
21 Correct 12 ms 9716 KB Output is correct
22 Correct 14 ms 10792 KB Output is correct
23 Correct 14 ms 12376 KB Output is correct
24 Correct 84 ms 62888 KB Output is correct
25 Correct 92 ms 63056 KB Output is correct
26 Correct 84 ms 62844 KB Output is correct
27 Correct 120 ms 62620 KB Output is correct
28 Correct 68 ms 41440 KB Output is correct