Daniel_yuan's Blog

以下等式被称作单位根反演：

手玩发现，一个极简分数，如果其分母和进制的 \(\gcd\) 为 \(1\)，那么就符合题意。

那么就变成了求 \(\sum_{i=1}^n\sum_{j=1}^m[(j,k)=1][(i,j)=1]\)。

其实这个求和式的化简并不难，只是需要多发现式子之间的联系。

简单学习了模拟费用流之后一直有点迷糊，后来在交流中似乎悟到了些什么。

能推出这道题挺开心的，而且对模拟费用流有了更进一步的理解。

做过不少 DP of DP 题，但是考试还是想不到，很气，写个总结记录下。

首先对于已有的一堆牌，我们应该要能确定它能不能胡。

这部分具体的可以参考我的另一篇博客，顺带说一句，[ZJOI2019] 麻将的前置知识居然被拿去 [GXOI/GZOI2019] 出了个宝牌一大堆，ZJOI 恐怖如斯。

不会打麻将的 OIer 不是好 ACMer。

虽然看完这篇博客你可能并不会变成雀神，但是你可能看到和麻将有关的题目就不会那么慌了。

把初始状态和目标状态交换，题目不变。

为了方便，设 \(p_i\) 为 \(i\) 被选的概率，对应到输入即 \(\frac{p_i}{\sum_{j=1}^n p_j}\) 。

设 \(f(S)\) 表示从 \(S\) 状态开始，期望走 \(f(S)\) 步到达全零状态。为了方便，我们定义 \(\varnothing\) 表示全零状态。

那么显然有

FWT 是快速求形如 \(C(x)=\sum_{i?j=x}A(i)B(j)\) 的算法，其中 \(?\) 表示一种二进制的位运算。

网络流进阶。主要是有上下界的各种网络流或费用流以及几个消负环的方法。

在看这个 Blog 之前你最好已经熟练掌握了 Dinic 网络流和 EK 费用流。

定义一个串 \(S\) 的划分 \(s_1,s_2...s_k\) 为回文划分当且仅当 \(s_1,s_2...s_k\) 都是回文串。

现在考虑求一个串 \(S\) 的回文划分数。\(1\leq |S| \leq 10^6\)。