ZigZagK的博客
[容斥+分治NTT]LOJ575【「LibreOJ NOI Round #2」不等关系】题解
题目概述LOJ575解题报告有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数,转移方程很显然是前缀和、后缀和的形式,但是前缀和后缀和是没有办法加速的,复杂度...
[容斥+分治NTT]LOJ2541【「PKUWC2018」猎人杀】题解
题目概述LOJ2541解题报告可以把题目转化为,有一个外人向 $n$ 个人开枪,打到第 $i$ 个人的概率是 $w_i\over \sum w$ ,并且可以对死人开枪(但没有效果),问最后才打死...
[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛(7)1010【Connectivity of Erdős-Rényi Graph】题解
题目概述HDU7218解题报告这道题看起来和城市规划很像,但是由于要考虑概率,所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率,考虑两个连通块的概率:...
[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(8)1013【Shattrath City】题解
题目概述HDU7232解题报告比赛的时候想的是正着做,写完DP式子发现是个看起来很可做的东西,结果实际上不能做,寄掉了。实际上应该倒着做,$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 ...
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(1)1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥,长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和,以及 $g_i$ 表示走了 $i$ 行全非法的权值和(特殊的,如果 $i=1$...
[容斥+计数]HHKB Programming Contest 2020 D【Squares】题解
题目概述HHKB Programming Contest 2020 D解题报告其实不难,就是烦的一批,考试的时候写复杂了然后调不出来。首先补集转化,我们求相交的数量,然后总数量减去相交的数量。为...
[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解
题目概述ACL Beginner Contest F解题报告直接求不太可做,我们考虑容斥,用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$ 个元素两两组合的方案数为 $f_...
[容斥]Codeforces1425D【Danger of Mad Snakes】题解
题目概述CF1425D解题报告把和的平方拆开:$$ (\sum_{i=1}^{m}B_i)^2=\sum_{i=1}^{m}B_i^2+\sum_{i=1}^{m-1}\sum_{j=i+1}^...
CodeChef April Challenge 2019 Division 2
上次打完之后分数还是不够Div1……只能再打Div2。UPD:这次打完分数还是不够QAQ。Maximum Remaining去重后第二大。#include<cstdio> #incl...
[容斥+三元环]BZOJ5407【girls】题解
题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪,但是三个妹子之间不能有冲突,一种方案 $(i,j,k),i<j<k$ 的贡献为:$Ai+Bj+Ck$ ,求所有合法方案的总...