[省选模拟]6.12

未分类

---

迫害 DJ

广义Fib数列 $\{g_i\}$ 满足
$g_0=a$
$g_1=b$
$g_i=3*g_{i-1}-g_{i-2}(i>=2)$
求 $\underbrace{g_{...g_{g_n}}}_{k个g}\pmod p$
$T$ 组数据
$0<n,p \le 1e9,1\le k \le 100,1\le T \le 1000$

肯定找每层的循环节啊。
这玩意儿怎么找？
设 $F(n)$ 表示模 $n$ 意义下的循环节长度
设

$$n = \prod p_k^{a_k}$$
在本题这个递推关系中，有 $$f(p_i)= \begin{cases} 3& p_i=2\\ 8& p_i=3\\ 20& p_i=5\\ p_i-1& p_i\%5=4 \vee p_i\%5=1\\ 2·p_i+2& p_i\%5=2 \vee p_i\%5=3\\ \end{cases}$$
则 $$F(n) = LCM( f(p_i) · p_i^{k_i-1})$$
广义Fibonacci数列找循环节中有证明和一般的求 $f$ 的方法，不过看不懂不想看，所以以后碰到直接打表求 $f$ 吧。

夕张的改造

给你一棵 $n$ 个节点的树，你可以删除一条边并连上一条边 $k$ 次，问能生成多少种树。
$n \le 50$

Orz $\color{black}{\text{k}}$$\color{red}{\text{rydom}}$ 又一次被刷新了对矩阵树和插值的认知。
原问题等价于求选择不超过 $k$ 条非树边形成树方案数。
我们设一条非树边为 $x$ ，由于矩阵树定理求的是边权乘积之和，那么算出来的多项式的 $x^i$ 项系数就是恰好选择 $i$ 条非树边的方案数。
枚举 $x=[0,n-1]$ ，用矩阵树定理算出 $n$ 个点值，再用插值算法插出这个多项式，$x_0...x_k$ 项系数之和就是答案。

亚特兰大

给你一棵 $n$ 节点树，边有边权，求无序对 $(u,v)$ 的个数，满足 $u$ 到 $v$ 的简单路径的 $gcd$ 等于 $1$ 。有 $q$ 次修改，每次修改一条边的权值，你需要回答初始局面以及每次修改后的答案。
$n\le 1e5,w\le 1e6,q\le 100$

设 $f_i$ 表示 $gcd$ 为 $i$ 的倍数的路径条数，问题转化为求每个 $f_i$。对于一个 $f_i$ ，可以用并查集合并所有边权为 $i$ 的倍数的边来求得。
考虑修改，因为修改次数极少，所以先把不修改的边考虑了，设这时为时刻 $0$ 。然后对于时刻 $i$，回滚到时刻 $0$，再加边（指考虑了时刻 $0$ 到时刻 $i$ 的修改操作的边）到时刻 $i$ 就行了。回滚用可撤销并查集实现。