# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
964071 | 2024-04-16T09:23:27 Z | LucaIlie | 캥거루 (CEOI16_kangaroo) | C++17 | 4 ms | 26972 KB |
#include <bits/stdc++.h> using namespace std; const int MAX_N = 200; const int MOD = 1e9 + 7; struct ZP { int x; ZP operator + ( ZP a ) { return { x + a.x }; } void operator += ( ZP a ) { x += a.x; } 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][MAX_N + 1][2][2]; void afis( int n, int i ) { for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) printf( "%d: %d %d -- %d %d %d %d\n", i, mn, mx, dp[i][mn][mx][0][0], dp[i][mn][mx][0][1], dp[i][mn][mx][1][0], dp[i][mn][mx][1][1] ); } } int main() { int n, s, f; cin >> n >> s >> f; if ( s > f ) swap( s, f ); if ( s == 1 ) { if ( f == 2 ) dp[3][0][1][1][1] = 1; dp[2][0][0][1][0] = 1; } else dp[1][1][0][0][0] = 1; int p = 2; for ( int i = 0; i < s - 1; i++ ) { for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) { dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * (mx * 2 + 2); dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2); } } if ( i == 0 && s > 1 ) p--; p++; } for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) { dp[s][mn][mx][0][0] = dp[s - 1][mn][mx][0][0]; dp[s][mn][mx][0][1] = dp[s - 1][mn][mx][0][1]; dp[s][mn][mx][1][0] = dp[s - 1][mn][mx][1][0]; dp[s][mn][mx][1][1] = dp[s - 1][mn][mx][1][1]; } } for ( int i = s; i < f - 1; i++ ) { for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) { dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * (mx * 2 + 1); dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2); dp[i + 1][mn][mx + 1][1][0] += dp[i][mn][mx][0][0]; dp[i + 1][mn][mx][1][0] += dp[i][mn][mx][1][0] * (mx * 2 + 1); dp[i + 1][mn + 1][mx + 1][1][0] += dp[i][mn][mx][1][0] * (p - 1 - mx * 2); } } if ( s == 1 && i == s ) p--; p++; } for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) { dp[f][mn][mx][0][0] = dp[f - 1][mn][mx][0][0]; dp[f][mn][mx][0][1] = dp[f - 1][mn][mx][0][1]; dp[f][mn][mx][1][0] = dp[f - 1][mn][mx][1][0]; dp[f][mn][mx][1][1] = dp[f - 1][mn][mx][1][1]; } } for ( int i = f; i < n; i++ ) { for ( int mn = 0; mn <= n; mn++ ) { for ( int mx = 0; mx <= n; mx++ ) { dp[i + 1][mn][mx][0][0] += dp[i][mn][mx][0][0] * mx * 2; dp[i + 1][mn + 1][mx + 1][0][0] += dp[i][mn][mx][0][0] * (p - 2 - mx * 2); dp[i + 1][mn][mx + 1][1][0] += dp[i][mn][mx][0][0]; dp[i + 1][mn][mx + 1][0][1] += dp[i][mn][mx][0][0]; dp[i + 1][mn][mx][1][0] += dp[i][mn][mx][1][0] * mx * 2; dp[i + 1][mn + 1][mx + 1][1][0] += dp[i][mn][mx][1][0] * (p - 1 - mx * 2); dp[i + 1][mn][mx + 1][1][1] += dp[i][mn][mx][1][0]; dp[i + 1][mn][mx][0][1] += dp[i][mn][mx][0][1] * mx * 2; dp[i + 1][mn + 1][mx + 1][0][1] += dp[i][mn][mx][0][1] * (p - 1 - mx * 2); dp[i + 1][mn][mx + 1][1][1] += dp[i][mn][mx][0][1]; dp[i + 1][mn][mn][1][1] += dp[i][mn][mx][1][1] * mx * 2; dp[i + 1][mn + 1][mx + 1][1][1] += dp[i][mn][mx][1][1] * (p - mx * 2); } } if ( f == 2 && i == f ) p--; p++; } ZP ans; ans = 0; for ( int i = 0; i < 2; i++ ) { for ( int j = 0; j < 2; j++ ) { if ( n % 2 == 0 ) ans += dp[n][(n - 2) / 2][(n - 2) / 2][i][j]; else ans += dp[n][(n - 2) / 2][n - 2 - (n - 2) / 2][i][j] + dp[n][n - 2 - (n - 2) / 2][(n - 2) / 2][i][j]; } } ans.out(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4440 KB | Output is correct |
2 | Correct | 1 ms | 6488 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4440 KB | Output is correct |
2 | Correct | 1 ms | 6488 KB | Output is correct |
3 | Correct | 2 ms | 16732 KB | Output is correct |
4 | Incorrect | 4 ms | 26972 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4440 KB | Output is correct |
2 | Correct | 1 ms | 6488 KB | Output is correct |
3 | Correct | 2 ms | 16732 KB | Output is correct |
4 | Incorrect | 4 ms | 26972 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4440 KB | Output is correct |
2 | Correct | 1 ms | 6488 KB | Output is correct |
3 | Correct | 2 ms | 16732 KB | Output is correct |
4 | Incorrect | 4 ms | 26972 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |