目录

发现这个题库，很有意思，趁着还没有学习微积分，看不了书，赶快从头开始刷，所以都是一些简单的题目，即时简单，有一些结论还是很有意思的。

网上资料很少，有的找不到答案，所以只有硬着头皮做了。

PE 15

一个网格图,只能向下，或者向右走,问从\((0,0)\)到\((n,m)\)到路径有多少条.

这里的结论是有\(C_{n+m}^n\).

证明：从0,0到n,m会往下走n步,往右走m步，把路径看成一个长度为n+m的序列，往下走为0,往右走为1

有n个0,m个1,转化为有多少个不同的序列。

我们考虑从序列中选择0的方案数.就是\(C_{n+m}^n\).

PE 76

这是一道很有意思的题目。

里面详细的讲解了如何使用数学的方法来解，不过全是英文，我没有看懂。

也可以使用\(f[i][j]\)表示以i结尾最后一段的和式j数的方案数.

然后发现可以使用前缀和优化，复杂度\(O(n^2)\)

由于是DP,所以放一下代码仅供参考.

int main() {    f[0][0] = sum[0][0] = 1;    for(int i = 1;i <= 100;++ i) sum[0][i] = sum[0][i - 1];    int n = 100;    for(int i = 1;i <= n;++ i) {        for(int j = 1;j <= i;++ j) {            f[i][j] = sum[i - j][j];            sum[i][j] = f[i][j];        }        for(int j = 2;j <= 100;++ j) sum[i][j] += sum[i][j - 1];    }    ll Ans = 0;    Ans = sum[100][99];    std::cout << Ans;    return 0;}

从上面的链接中得知,有生成函数的解法。

PE 90

一个trick , 显然可以用对数函数来比较大小

\(log(a^b) = b*log(a)\)

PE 577

恩，调这道题做了一下午。

\(f(i)\)表示以i行为底的六边形造成的共线，然后就可以计算了

\[f(n) = f(n-1) + \sum_{s=1}^{\lfloor n/3\rfloor}s(n-3s+1)\]

PE 97

一个trick ， mod，

乘法和加法满足

\((a*b) \% mod = ((a \% mod) * (b \% mod))\%mod\)

\((a+b)\%mod = ((a\% mod) + (b\% mod) )\%mod\)

PE 364（坑）

第三道计数题，感觉还是get不到计数的点。

只推了一个性质：

第一步结束之后，不存在长度>=3的空格子。

---

根据这个性质。

第一步结束之后，局面会变成每两个人间隔只有1与2.

有一特殊情况是两端有人或者没人。

存在特殊情况，我们先枚举左右端点。

然后枚举长度为2的空格子的个数。

枚举之后，我们发现可以计算出长度为1的空格子的个数.

考虑第二步，每个人必须加入长度为二的空格子，所以方案数是2.

之后就是难以忍受的细节问题了。

还没有完成代码的任务

待做

PE 601

PE 613

PE 493

PE 102

PE 618