#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20000;
const int MAX_FACT = 3 * MAX_N;
int mod;
int fact[MAX_FACT + 1], invFact[MAX_FACT + 1], countB[MAX_N + 1], countBU[MAX_N + 1];
int lgPut( int x, int n ) {
if ( n == 0 )
return 1;
int p = lgPut( x, n / 2 );
p = (long long)p * p % mod;
if ( n % 2 == 1 )
p = (long long)p * x % mod;
return p;
}
void initFact( int n ) {
fact[0] = 1;
for ( int i = 1; i <= n; i++ )
fact[i] = (long long)fact[i - 1] * i % mod;
invFact[n] = lgPut( fact[n], mod - 2 );
for ( int i = n - 1; i >= 0; i-- )
invFact[i] = (long long)invFact[i + 1] * (i + 1) % mod;
}
int comb( int n, int k ) {
return (long long)fact[n] * invFact[n - k] % mod * invFact[k] % mod;
}
int prodCons( int x, int k ) {
if ( x < 0 )
return 1;
if ( x == 0 )
return fact[x + k - 1];
return (long long)fact[x + k - 1] * invFact[x - 1] % mod;
}
int main() {
int n;
cin >> n >> mod;
initFact( MAX_FACT );
countB[1] = 0, countBU[1] = 1;
countB[2] = 1, countBU[2] = 1;
for ( int i = 3; i <= n; i++ ) {
//B<--B
for ( int k = 0; i - k - 2 >= 1; k++ )
countB[i] = (countB[i] + (long long)2 * countB[i - k - 2] * comb( k + 2, 2 ) % mod * prodCons( 2 * (i - k - 2) - 2, k ) % mod) % mod % mod;
//B<--BU
for ( int k = 0; i - k - 2 >= 1; k++ )
countB[i] = (countB[i] + (long long)countBU[i - k - 2] * (k + 1) % mod * prodCons( 2 * (i - k - 2) - 1, k ) % mod) % mod;
//BU<--B
for ( int k = 0; i - k - 1 >= 1; k++ )
countBU[i] = (countBU[i] + (long long)countB[i - k - 1] * (k + 1) % mod * prodCons( 2 * (i - k - 1) - 2, k ) % mod) % mod;
//BU<--BU
for ( int k = 0; i - k - 1 >= 1; k++ )
countBU[i] = (countBU[i] + (long long)countBU[i - k - 1] * prodCons( 2 * (i - k - 1) - 1, k ) % mod) % mod;
}
int tot = 1;
for ( int i = 3; i < 2 * n; i += 2 )
tot = (long long)tot * i % mod;
int correct = 0;
for ( int i = 1; i <= n; i++ ) {
int k = n - i;
correct = (correct + (long long)countB[i] * (k + 1) % mod * prodCons( 2 * i - 2, k ) % mod) % mod;
correct = (correct + (long long)countBU[i] * prodCons( 2 * i - 1, k ) % mod) % mod;
}
cout << (tot - correct + mod) % mod;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
2 ms |
860 KB |
Output is correct |
16 |
Correct |
2 ms |
860 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
2 ms |
860 KB |
Output is correct |
16 |
Correct |
2 ms |
860 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
19 |
Correct |
6 ms |
856 KB |
Output is correct |
20 |
Correct |
6 ms |
860 KB |
Output is correct |
21 |
Correct |
7 ms |
920 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
2 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
2 ms |
860 KB |
Output is correct |
16 |
Correct |
2 ms |
860 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
19 |
Correct |
6 ms |
856 KB |
Output is correct |
20 |
Correct |
6 ms |
860 KB |
Output is correct |
21 |
Correct |
7 ms |
920 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
2 ms |
860 KB |
Output is correct |
24 |
Correct |
524 ms |
1160 KB |
Output is correct |
25 |
Correct |
520 ms |
1116 KB |
Output is correct |
26 |
Correct |
521 ms |
916 KB |
Output is correct |
27 |
Correct |
7 ms |
856 KB |
Output is correct |
28 |
Correct |
90 ms |
860 KB |
Output is correct |
29 |
Correct |
72 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
856 KB |
Output is correct |
2 |
Correct |
1 ms |
860 KB |
Output is correct |
3 |
Correct |
1 ms |
704 KB |
Output is correct |
4 |
Correct |
2 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
856 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
2 ms |
860 KB |
Output is correct |
16 |
Correct |
2 ms |
860 KB |
Output is correct |
17 |
Correct |
2 ms |
860 KB |
Output is correct |
18 |
Correct |
1 ms |
860 KB |
Output is correct |
19 |
Correct |
6 ms |
856 KB |
Output is correct |
20 |
Correct |
6 ms |
860 KB |
Output is correct |
21 |
Correct |
7 ms |
920 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
2 ms |
860 KB |
Output is correct |
24 |
Correct |
524 ms |
1160 KB |
Output is correct |
25 |
Correct |
520 ms |
1116 KB |
Output is correct |
26 |
Correct |
521 ms |
916 KB |
Output is correct |
27 |
Correct |
7 ms |
856 KB |
Output is correct |
28 |
Correct |
90 ms |
860 KB |
Output is correct |
29 |
Correct |
72 ms |
856 KB |
Output is correct |
30 |
Execution timed out |
9008 ms |
1216 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |