bzoj1485 有趣的数列

传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1485

【题解】

Catalan数，注意不能直接用逆元，需要分解质因数。

 # include <bits/stdc++.h>

 using namespace std;

 const int M = 5e5 + , N = 2e6 + ;

 int isp[N];

 int p[M], pn;

 int n, mod;

 int times[M];

 inline int pwr(int a, int b) {

     int ret = ;

     while(b) {

         if(b&) ret = 1ll * ret * a % mod;

         a = 1ll * a * a % mod;

         b >>= ;

     }

     return ret;

 }

 int main() {

     cin >> n >> mod;

     for (int i=; i<=n+n; ++i) isp[i] = ;

     for (int i=; i<=n+n; ++i) {

         if(isp[i]) {

             p[++pn] = i;

             isp[i] = pn;

             for (int j=i+i; j<=n+n; j+=i)

                 isp[j] = ;

         }

     }

     for (int i=n+; i<=n+n; ++i) {

         int t = i;

         for (int j=; j<=pn; ++j) {

             if(t % p[j] == )

                 while(t % p[j] == ) ++times[j], t /= p[j];

             if(t == ) break;

             if(isp[t]) {

                 ++ times[isp[t]];

                 break;

             }

         }

     }

 //    for (int i=1; i<=5; ++i)

 //        cout << p[i] << ' ' << times[i] << endl;

     for (int i=; i<=n+; ++i) {

         int t = i;

         for (int j=; j<=pn; ++j) {

             if(t % p[j] == )

                 while(t % p[j] == ) --times[j], t /= p[j];

             if(t == ) break;

             if(isp[t]) {

                 -- times[isp[t]];

                 break;

             }

         }

     }

     int ans = ;

     for (int i=; i<=pn; ++i)

         if(times[i]) ans = 1ll * ans * pwr(p[i], times[i]) % mod;

     cout << ans;

     return ;

 }