BZOJ1485

本文主要是介绍BZOJ1485，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

BZOJ1485

• 题目

  BZOJ1485

• 分析

  可以找规律发现是 $Catlan$ 数列。。

  还是证明一下：

  性质2：$a_1<a_3<..<a_{2i-1}$ , $a_2<a_4<...<a_{2i}$

  ​
  $$\begin{array}{rl}& a_1<a_3<...a_{2i-1}<a_{2i}\\ & 可以得出在偶数位上的数比它左边所有数都要大，换句话说偶数位上的数大于等于这个偶数位的下标。\\ & 由性质2从小到大放数字的时候要尽量靠左放\\ & 假设已经放了1\sim x个数，x_1个放在奇数位上，x_2个放在偶数位上，则x_2<x_1.\\ & 证明一下：\\ & 假设x_2>x_1,x_2>\frac{x}{2},由偶数位上的数大于等于这个偶数位的下标,最后一个偶数位下标应该是2\times x_2\\ & 2\times x_2>x,而只有x个数，所以假设不成立。\end{array}$$
  所以得出结论：按从小到大的顺序放到任意一个数 $x$ ，都满足放在偶数位上的数字个数小于等于放在奇数位上的数字个数 .

  这很明显是 $Catlan$ 数。。。

  本题实现还是有点意思。。

  $Java$ 大数超时可能太卡了吧。。。$Java$ 不知道开了多少时间。。

  $Catlan$ 数列通项公式用： $\frac{C_{2n}^n}{(n+1)!}$ 化简：$\frac{{\prod }_{i=n+2}^{2n}i}{n!}$

  模数居然不是质数。。。不好求逆元

  运用智慧

  对分子用唯一分解，分成$p_1^{c_1}{p}_2^{c_2}...p_m^{c_m}$ ,分母：$p_1^{b_1}{p}_2^{b_2}....p_m^{b_m}$

  除的话就是：$p_1^{c_1-b_1}{p}_2^{c_2-b_2}...p_m^{c_m-b_m}$ ,$ksm$ 一下，就可以了。。注意分解的时候要预处理出 $1\sim 2n$ 的质数会快很多。。别傻乎乎的直接算。。说的就是我

• 代码

  const int N = 2e6 + 6;
  int v[N], prime[N];
  int m;
  int c[N];
  void primes(int n) {memset(v, 0, sizeof(v));m = 0;for (int i = 2; i <= n; i++) {if (v[i] == 0) {v[i] = i;prime[++m] = i;}for (int j = 1; j <= m; j++) {if (prime[j] > v[i] || prime[j] > n / i) break;v[i * prime[j]] = prime[j];}}
  }
  void divid(int x, int d)
  {for (int i = 1; i <= m && prime[i] * prime[i] <= x; i++){if (x % prime[i] == 0){while (x % prime[i] == 0){c[prime[i]] += d;x /= prime[i];}}}if (x > 1) c[x] += d;
  }
  ll ksm(ll a, ll b, ll mod)
  {ll ans = 1 % mod;while (b > 0){if (b & 1) ans = ans * a % mod;b >>= 1;a = a * a % mod;}return ans % mod;
  }
  int main()
  {int n, p;read(n);read(p);primes(n << 1);for (int i = n + 2; i <= (n << 1); i++) divid(i, 1); // 处理分子for (int i = 1; i <= n; i++) divid(i, -1); // 处理分母ll ans = 1;for (int i = 1; i <= m; i++){if (c[prime[i]]) { ans = ans * ksm(prime[i], c[prime[i]], p); //累乘ans %= p;}}cout << ans << endl;return 0 ;
  }
  

• 题型

  $Catlan$数

这篇关于BZOJ1485的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---