发表于 | 更新于
字数统计 32 | 阅读时长 0

这是我的第一篇post

问题详细

Markdown支持存在问题：

  • 不支持数学公式！
  • 不支持任务列表
  • 脚注支持不好
  • ……
阅读全文 »

发表于 | 更新于
字数统计 763 | 阅读时长 3

洛谷上很多省选题都没有题解，不得不找bzoj的题解

概述

50%

使用递推，在$\mathcal O(n^2)$的时间内得到答案，不过我没写对。

正解

通过暴力或者上述方法，打印出较小的答案，可能会发现规律。实际上这题就是求Catalan数(n-2)，有很多理解方式，常见的求法有三种（参见百度百科 ）：

  1. $f_n=\sum\limits_{i=0}^{n-1}f_i*f_{n-i-1}$ ，不能使用这个公式，因为也需要$\mathcal O(n^2)$
  2. $f_n=f_{n-1}*\frac{4n-2}{n+1}$ ，我本来以为可以用的，但是由于$p$不一定是一个质数，因此无法计算逆元以进行除法运算
  3. $f_n=\frac{\mathcal C_{2n}^{n}}{n+1}$ ，这是可用的公式

如果不熟悉组合数的求法，可以做一下计算系数 ，总结中给出代码。

其中$\frac{\mathcal C_{2n}^{n}}{n+1}=\frac{\prod\limits_{i=n+2}^{2n}i}{\prod\limits_{i=1}^ni}$，我们需要把所有$2n$之内的质数筛出来，同时得到每个数最小的质因数（欧拉线性筛法），进行约分再使用快速幂1得出结果。

  1. 使用分治法在$\mathcal O(\log n)$的时间内计算出$a^b\mod p$ ↩

阅读全文 »

发表于 | 更新于
字数统计 897 | 阅读时长 4

题目概览

名称

项目名称 数列 斐波那契数的长度 区间质数 新挑战
英文名称 list fiblen prime newchal
可执行文件名称 list.exe fiblen.exe prime.exe newchal.exe
输入文件 list.in fiblen.in prime.in newchal.in
输出文件 list.out fiblen.out prime.out newchal.out
每个测试点时限 3s 1s 1s 1s
内存限制 512MiB1 512MiB 16MiB 512MiB
测试点数量 10 10 10 10
每个测试点分值 10 10 10 10

时限仅供参考，请以标程运行时间计算

  1. 1MiB=1024KiB,1KiB=1024B;1MB=1000KB,1KB=1000B ↩

阅读全文 »