[关闭]
@Holmesee 2020-06-12T15:07:30.000000Z 字数 941 阅读 592

[省选模拟]6.12

未分类


迫害 DJ

广义Fib数列 满足




组数据

肯定找每层的循环节啊。
这玩意儿怎么找?
表示模 意义下的循环节长度


在本题这个递推关系中,有


广义Fibonacci数列找循环节中有证明和一般的求 的方法,不过看不懂不想看,所以以后碰到直接打表求 吧。

夕张的改造

给你一棵 个节点的树,你可以删除一条边并连上一条边 次,问能生成多少种树。

Orz 又一次被刷新了对矩阵树和插值的认知。
原问题等价于求选择不超过 条非树边形成树方案数。
我们设一条非树边为 ,由于矩阵树定理求的是边权乘积之和,那么算出来的多项式的 项系数就是恰好选择 条非树边的方案数。
枚举 ,用矩阵树定理算出 个点值,再用插值算法插出这个多项式, 项系数之和就是答案。

亚特兰大

给你一棵 节点树,边有边权,求无序对 的个数,满足 的简单路径的 等于 。有 次修改,每次修改一条边的权值,你需要回答初始局面以及每次修改后的答案。

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注