이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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++ ) {
for ( int k = 0; i - k - 1 >= 1; k++ ) {
//B<--B
countB[i] = (countB[i] + (long long)countB[i - k - 2] * comb( k + 2, 2 ) % mod * prodCons( 2 * (i - k - 2) - 2, k ) % mod) % mod * 2 % mod;
//B<--BU
countB[i] = (countB[i] + (long long)countBU[i - k - 2] * (k + 1) % mod * prodCons( 2 * (i - k - 2) - 1, k ) % mod) % mod;
if ( i - k - 2 >= 1 ) {
//BU<--B
countBU[i] = (countBU[i] + (long long)countB[i - k - 1] * (k + 1) % mod * prodCons( 2 * (i - k - 1) - 2, k ) % mod) % mod;
//BU<--BU
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;
for ( int i = 1; i <= n; i++ ) {
int k = n - i;
tot = (tot - (long long)countB[i] * (k + 1) % mod * prodCons( 2 * i - 2, k ) % mod + mod) % mod;
tot = (tot - (long long)countBU[i] * prodCons( 2 * i - 1, k ) % mod + mod) % mod;
}
cout << tot;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |