我学会了什么
- 利用预处理的前缀积与逆元在 $O(\log M)$ 的时间内求 $C_n^m \bmod M$ （ $M$ 为质数）
- 怎么求卡特兰数
还搞不懂什么
- 容斥原理
本日题解
已知 $an=2^{a{n-1}}$ ，求 $a_n \bmod p$。
根据欧拉定理推论可知，由于 $n$ 趋近于无穷大，所以 $a{n-1}$ 也趋近于无穷大，所以满足 $a{n-1}\geq\varphi(p)$
因此 $2^{2^{2^\cdots}}\equiv 2^{2^{2^\cdots} \bmod \varphi(p)+\varphi(p)} \pmod p$
根据这个式子我们可以不断地降幂，直到 $p$ 的值变为 $1$
用一个较大的数初始化 $N$ 后递归求解即可。
数论全家桶（
求 $G^{\sum_{i\mid n}\binom ni }\bmod 999911659$
$n\leq10^9,999911659=2\times3\times4679\times35617+1$是质数
为了方便打公式，设 $a=G,b=\sum_{i\mid n}\binom ni,p=999911659$
因为模数为质数，所以可以用欧拉定理 $a^b \equiv a^{b\bmod\varphi(p)} \pmod p$。
还是因为 $p$ 是质数，所以 $\varphi(p)=p-1$
那么 $b \bmod \varphi(p)=\sum_{i\mid n}\binom ni\bmod (2\times3\times4679\times35617)$
根据同余式的性质（如果同余式对于模 $p$ 成立，那么它对于 $p$ 的任意约数相等的模 $d$ 也成立）可得，
$\left{\begin{matrix}
x \equiv \sum{d\mid n}\binom{n}{d} \pmod {2} \
x \equiv \sum{d\mid n}\binom{n}{d} \pmod {3} \
x \equiv \sum{d\mid n}\binom{n}{d} \pmod {4679} \
x \equiv \sum{d\mid n}\binom{n}{d} \pmod {35617}
\end{matrix}\right.$
根据 $\text{Lucas}$ 定理，$\displaystyle\binom {n}{k} \equiv \binom {\frac{n}{p}}{\frac{k}p{}} \binom {n \bmod p}{k \bmod p} \pmod p$，可以加快求组合数的速度并随时取模
根据中国剩余定理，可解出最小非负整数解 $x$ ，最后快速幂求 $G^x$ 即可。
首先，在 $m$ 个元素中选 $n-1$ 个作为序列元素（因为有且仅有一对相同元素），共 $C_m^{n-1}$ 种方案。
最大的元素是确定的。如果两个相同的元素也确定了，那么剩下的 $n-3$ 个元素就可以选择放在最大值左侧或右侧，共 $2^{n-3}$ 种方案。
相同的元素的选取有 $n-2$ 种方案（$n-1$ 个元素，去掉一个最大值）。
所以最终答案为 $C_m^{n-1}\times(n-2)\times2^{n-3}$ 种方案，注意特判 $n=2$ 无解。
这个问题可以转化为将 $1\sim2n$ 放入序列中，每次只能放在最前的奇数位或偶数位。
由于偶数位上的数一定大于等于其下标，所以在任意时刻偶数位上的数一定少于等于奇数位上的数。
又因为奇数位于偶数位总个数相同。
所以可以用卡特兰数求解。
由于 $p$ 不是质数，可以将$2n,n$ 质因数分解后求解。