Welcome to My Blog!

P4597 序列 sequence

idea：

贪心？大根堆， $DP$ 分析（不会）

解决方案：

首先，有一个显然的 $dp$ 方法：

P2748 [USACO16OPEN]Landscaping P

idea:

带悔贪心

解决方案

P3986 斐波那契数列

idea:

观察性质，应用扩展欧几里得算法。

解决方案：

欧拉定理和欧拉函数

欧拉函数：

定义式：

$$\varphi(x) = \sum_{i=1}^{x} [\gcd(i,x)=1]$$

根据定义可证欧拉函数是积性函数。

P4139 上帝与集合的正确用法

idea:

扩展欧拉定理（降幂公式）与递归。

解法：

题目可以简化为：求 $2^{2^{2^{...}}}\mod p$ 。

P2606 [ZJOI2010]排列计数

idea:

树形 $dp$ ，对于组合数的计算。

解决方案：

P2303 [SDOI2012] Longge 的问题

idea:

推式子。

解决方案：

P2155 [SDOI2008] 沙拉公主的困惑

idea:

推式子，转化为欧拉函数

P3223 [HNOI2012] 排队

idea:

比较简单的排列组合，比较不恶心但还是恶心的高精度。

解决方案：

P6146 [USACO20FEB]Help Yourself G

idea：

熟悉使用计数类问题的常用方法：设函数并通过分类讨论找到递推式，不需要多余的计算。

解决方案：

我们先按左端点给所有序号排序。