#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200;
const int MOD = 1e9 + 7;
struct ZP {
int x;
};
int 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];
printf( "%d %d %d %d\n", i, mn, mx, dp[3][1][1][1][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++;
}
int 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 - (n - 2) / 2][i][j] + dp[n][n - (n - 2) / 2][(n - 2) / 2][i][j];
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4944 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
