P3306 [SDOI2013]随机数生成器

BSGS 模版题

axi+bzxi+1(modp)a(xi+λ)(xi+1+λ)(modp)λaλb(modp)λba1(modp)fi=xi+λfxax1f1(modp)\begin{aligned}ax_i+bz&\equiv x_{i+1} \pmod p\\a(x_i+\lambda) &\equiv (x_{i+1}+\lambda) \pmod p\\\lambda a-\lambda &\equiv b \pmod p\\\lambda& \equiv \frac b {a-1} \pmod p\\f_i &= x_i + \lambda\\f_x &\equiv a^{x-1}f_1\pmod p\end{aligned}

直接 bsgs 即可。

阅读全文 »

清华集训 2017 生成树计数

给定一张 ss 个点的图,存在 sns-n 个边,使得图中形成了 nn 个联通块,第 ii 个联通块内部有 aia_i 个点。

我们现在要再连 n1n-1 个边,使得该图成为一个树。对于某一种连边方式,我们设原题第 ii 个联通块连出了 did_i 条边,那么当前树的权值为

val(T)=(i=1ndim)(i=1ndim)val(T) = \left(\prod_{i=1}^n d_i^m\right) \left(\sum_{i=1}^n d_i^m\right)

求所有生成树的权值和。

n3×104,m30n \le 3\times 10^4 , m\le 30


我们可以考虑把开始就连通的点缩起来,枚举一个联通块的生成树 TT ,那么

ans=Ti=1ndimj=1ndjmajdjans = \sum_{T} \sum_{i=1}^n d_i^m \prod_{j=1}^n d_j^m a_j^{d_j}

我们考虑一个联通块向外连,可能是这个联通块的任何一个点往外连,并且一个点可以连多个边出去。

阅读全文 »

斯特林数,斯特林反演初探

基础定义

斯特林树分成两类,

  • 第一类:将 nn 个元素划分成 mm 个圆排列的方案数量。计做 [nm]\left[\begin{array}{l} n \\ m \end{array}\right]

    [nm]=[n1m1]+(n1)[n1m]\left[\begin{array}{l} n \\ m \end{array}\right]=\left[\begin{array}{l} n-1 \\ m-1 \end{array}\right]+(n-1)\left[\begin{array}{c} n-1 \\ m \end{array}\right]

    递推式是由于,考虑我们加入第 nn 个元素的时候,可以新开一个圆排列,也可以加入到之前任何一个数的后面的位置。

  • 第二类:将 nn 个元素划分成为 mm 个集合的方案数量。计做 {nm}\left\{\begin{array}{l}n \\m\end{array}\right\}

    {nm}={n1m1}+m{n1m}\left\{\begin{array}{l} n \\ m \end{array}\right\}=\left\{\begin{array}{l} n-1 \\ m-1 \end{array}\right\}+m\left\{\begin{array}{c} n-1 \\ m \end{array}\right\}

    递推式是由于,考虑我们加入第 nn 个元素的时候,可以新开一个集合,也可以加入到之前任何一个集合。

    同时它可以写成展开式:

    {nm}=1m!k=0m(1)k(mk)(mk)n\left\{\begin{array}{l}n \\m\end{array}\right\}=\frac{1}{m !} \sum_{k=0}^{m}(-1)^{k}\left(\begin{array}{l}m \\k\end{array}\right)(m-k)^{n}

    我们考虑一个容斥,由于最终目标是让 nn 个集合划分成 mm 个集合,显然不能有空的。我们可以枚举一下假设有 kk 个集合是空的,那么方案数量就是 (mk)n(m-k)^n ,我们想要选择集合的方案数量是 (mk)m \choose k ,容斥系数是 (1)k(-1)^k ,当然,这个是具有顺序的,实际上是没有顺序的方案个数,所以还需要去个顺序。

阅读全文 »

青春猪头少年不会梦到兔女郎学姐

好的现在开始番剧介绍(bushi

我们先来考虑一个前置问题。假设有 nn 种球,第 ii 种球有 aia_i 个,你需要放在序列上,满足相邻的两个位置球不能相同,问方案数量。这是一个经典容斥题,我们考虑假设第 ii 种球出现了 jj 组相邻,那么就把这些球缩在一起。现在就变成了有 iji-j 个球进行排列,乘上容斥系数 (1)j(i1j)(-1)^{j}{i-1 \choose j}

阅读全文 »

CF840C On the bench

我们考虑当 aiaj,ajaka_ia_j,a_ja_k 均为完全平方数的时候,aiakaj2a_ia_ka_j^2 也一定是一个完全平方数,于是 aiaka_ia_k 也是完全平方数了。也就是说我们可以把所有数划分成很多类,每一类里面任意两个数乘起来都是完全平方,并且不同类的数乘起来一定不是完全平方。

阅读全文 »

4.8模拟赛 C

A 没啥意思 B 不会 nim 积 就不写题解了。

我们考虑什么时候先手必赢。我们分直径的奇偶来讨论。

如果直径长度是奇,那么一定存在一个直径中点。假设开始的时候棋子在直径中点,那么先手不管怎么跳,后手都可以跳到直径上与终点对称的那个方向,于是先手就 GG 了。否则,假设开始不再直径中点,先手显然可以一次让棋子到直径中点,后手就 GG 了。

阅读全文 »

长链剖分

长链剖分是一种比较冷门的科技。算法本身很简单,就是把重链剖分中的权值(子树大小)变成子树内的最大深度。显然,长链剖分复杂度是 O(n)O(n) 的,它和任何剖分一样,会把树剖分成 O(n)O(n) 条链,并满足链长和 O(n)O(n)

阅读全文 »