[Zjoi2019] 麻将

麻将真好(du)van(liu)

  • 首先考虑对于一个状态来说: 摆牌的顺序是没有关系的, 只与牌数有关.

那么如何确定当前局面能否胡牌?

  1. 7个对子胡牌的情况非常好判断.
  2. 考虑顺子胡牌的情况:

继续阅读 [Zjoi2019] 麻将

Matrix Tree

其实挺没用的, 简单记录一下

对于一个无向图G,它的生成树个数等于其基尔霍夫\text{Kirchhoff} 矩阵任何一个N-1阶主子式的行列式的绝对值.

  • \text{Kirchhoff} 矩阵:
    定义为图中度数矩阵D – 邻接矩阵A

继续阅读 Matrix Tree

容斥本质

容斥的思想贯穿了几乎所有的反演等…
它的重(du)要(liu)可见一斑

这里自行脑补一个Veen图吧 (

基本公式

  • 已知A_1,A_2,A_3… A_nA_1 \bigcup A_2 \bigcup…\bigcup A_n

继续阅读 容斥本质

SA

构造

  • O(n\log n) : 倍增
  • O(n) : Dc3 无卵用感觉

性质

关于SA, 令h_i=\text{height}_{rank_i}, 有

  • h_i\geq h_{i-1}-1

继续阅读 SA

Codeforces 886E

nice problem…

fake sol

开始是这样想的, 可以枚举好序列第一个出现答案的位置, 记为pos

那么显然, 前面的所有数字都是不可以比pos^{th}的数字大的, 而且后面也应该保证有k

方案数是

\sum_{i=pos+k}^{n-1}\binom{i-1}{pos+k-1} \cdot (pos+k-1)! (n-(pos+k-1))!

继续阅读 Codeforces 886E