BOJ 9343 - 랜덤 걷기

BOJ 9343 - 랜덤 걷기

또 무지성 카탈란 수 문제이다

$$ C(i)=\dfrac 1{n+1}\dbinom{2n}{n}=\dfrac {(2n)!}{n!(n+1)!} $$

를 이용하고 모듈러 역원을 이용해 $O(N \log N)$에 구해줄 수 있다.

const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
array<ll, 3> gcdx(ll A, ll B) {  
   ll x1 = 1, x2 = 0, y1 = 0, y2 = 1, r1 = A, r2 = B;  
   while (r2) {  
      ll q = r1 / r2 - ((r1 ^ r2) < 0 && r1 % r2);  
      tie(x1, x2) = mp(x2, x1 - x2 * q);  
      tie(y1, y2) = mp(y2, y1 - y2 * q);  
      tie(r1, r2) = mp(r2, r1 - r2 * q);  
   }  
   return {x1, y1, r1};  
}  
const int MAX = 1000000;  
int dp[MAX + 1];  
int fac[MAX * 2 + 1];  
void pre_calc() {  
   fac[0] = 1;  
   for (int i = 1; i <= MAX * 2; i++) fac[i] = md(fac[i - 1] * i);  
   for (int i = 1; i <= MAX; i++) {  
      dp[i] = md(md(fac[i * 2] * gcdx(fac[i], mod)[0]) * gcdx(fac[i + 1], mod)[0]);  
   }  
}  
void solve() {  
   int n;  
   cin >> n;  
   cout << dp[n] << endl;  
}  
  
signed main() {  
   pre_calc();  
   fastio  
   int t;  
   cin >> t;  
   while (t--)  
      solve();  
   return 0;  
}