摘要：
20251215 Parentheses and Swapping 推一下每个集合出现的概率，发现是若干个数的乘积。 容斥计数，所有方案减去没有出现某个集合的方案。 然后需要计算这个东西： \[\sum_S \frac{(n!-z(S))^k}{n!^k} \]分子二项式定理分一下，得到： \[\s 阅读全文
posted @ 2025-12-15 16:17
liduoduo2021
阅读(15)
评论(2)
推荐(0)
摘要：
EGF 对于一个数列 \(<f_n>\) ，其指数型生成函数\(（EGF）\) \(F_n=\sum_{0\le n}\frac{f_n}{n!}x^n\) 。 注意到其中的 \(\frac{1}{n!}\) 这一项，在计算组合数的时候，往往会用到阶乘，那么可以发现两个多项式的二项式卷积结果的 \( 阅读全文
posted @ 2025-12-02 21:55
liduoduo2021
阅读(5)
评论(0)
推荐(0)
摘要：
图 下文默认有标号 DAG生成子图计数 \(DAG\) 中总会还有入度为 \(0\) 的点，所以每次删去这些节点会得到一个同为 \(DAG\) 的子结构，考虑实现这样的转移。 令 \(dp_s\) 表示子集 \(s\) 的答案。全集为当前 \(s\) 时，\(f_t\) 表示 \(t\) 中点恰为被 阅读全文
posted @ 2025-11-21 10:22
liduoduo2021
阅读(6)
评论(0)
推荐(0)
摘要：
斐波那契 \[gcd(F_i,F_j)=F_{gcd(i,j)}\\ \sum_{i-1}^nF_i=F_{n+2}-F_2 \]二项式反演 定义 \(g(m)\) 表示恰好选 \(m\) 个时的方案数，\(f(m)\) 必定选\(m\) 个，其余不管的方案数。 由于 \(g\) 往往需要满足其余的 阅读全文
posted @ 2025-11-21 10:20
liduoduo2021
阅读(7)
评论(0)
推荐(0)
摘要：
多项式题单 FFT 快速傅里叶变换,对于两个多项式的乘法能够做到 \(O(nlogn)\) 的时间复杂度。 引入：单位根 对于所有满足 \(x^n=1\) 的复数解，我们称之为 \(n\) 次单位根。 其几何意义就是在复平面上均匀分布在单位圆（模为1的圆）上，构成正 \(n\) 边形的顶点，其中一个 阅读全文
posted @ 2025-11-21 10:20
liduoduo2021
阅读(17)
评论(0)
推荐(0)
摘要：
此文自20251029起，记录 \(atcoder\) 上的刷题记录。 [AGC001D] 构造 [AGC001E] 组合意义 [AGC002F] 计数dp [AGC003E] 观察 [AGC004D] 贪心 [AGC005D] 组合意义+容斥 [AGC006C] 置换幂 [AGC006D] 观察 阅读全文
posted @ 2025-11-21 10:17
liduoduo2021
阅读(4)
评论(0)
推荐(0)
摘要：
1110 Following Arrows 先分析 \(1\times m\) 的网格，考虑全是 \(L\) 的情况。 由于到某个点时，前面的点一定都指向它，所以每个格子本质独立。 考虑 \(n\times m\) 的网格，可变为存在唯一一条到终点的合法路径，某个格子的另种走法为走到之前的某个点。 阅读全文
posted @ 2025-11-21 10:17
liduoduo2021
阅读(36)
评论(0)
推荐(0)
摘要：
Week1 20241005考试总结 分数：100+0（80）+0+10=110（190） 主要原因：B题重大失误，100->0 更新：数据改后变成80了。 B题本来是想出了正解的，写也是写出来了的，大样例也是过了的（好水），但是零分...... 我的转移是从 \(O(n)\) 优化的，所以当时加了 阅读全文
posted @ 2025-11-21 10:14
liduoduo2021
阅读(15)
评论(0)
推荐(0)
摘要：
NKOJ P11061 签到题 对于多边形的三角形划分，可以每次对于相邻的三个三角形划分，将中间的点删掉，继续下一次的选点。 [20250701] 求和 对于换转移的状态，如果知道环上总权值，那么就可以用主元法，设一个参数然后解出。 [模拟赛20230824] 龙了个龙 要求出现次数为 \(k\) 阅读全文
posted @ 2025-11-21 09:17
liduoduo2021
阅读(12)
评论(0)
推荐(0)
摘要：
AGC027E 操作的不变量 对于做若干次操作的题目，观察操作，找到操作中不会改变的量，将能通过操作得到的转态归纳。如此题中，当 \(a=1,b=2\) 时，修改操作就不会改变序列 \(mod\ \ 3\) 的值。 本质不同的计数 类似此题中的结果有多少种本质不同的情况，往往从初始去dp修改是困难的 阅读全文
posted @ 2025-11-21 09:17
liduoduo2021
阅读(13)
评论(0)
推荐(1)
浙公网安备 33010602011771号