ZigZagK的博客
[容斥+计数]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$ ,求所有合法方案的总...
[第一类斯特林数+广义容斥]BZOJ5406【Gift】题解
题目概述定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列,有些位置还没有确定,求相似度为 $i,i\in[0,n-1)$ ...
[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n​$ 种颜色的膜法卡,每种颜色有 $a_i​$ 种,总共有 $m​$ 张。现在要把所有卡片排成一排,如果相邻两个卡片颜色相同则产生一个膜法对,求膜法对个数为 $k​$ 的排列个数...
[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解
题目概述有 $n$ 个带权糖果和 $n$ 个带权药片,求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始想的是求出 $\ge K$ 的方案...
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合,求选出若干个子集(不可以不选)相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造,导致这道题的构造方法理解了半天…...
[思维+容斥]51Nod1317【相似字符串对】题解
题目概述字符串对 $(A,B)$ 是相似的需要满足两个串等长,且存在 $C$ 使得 $A+C=C+B$ 。求长度为 $n$ ,出现字母是小写字母前 $K$ 个的相似字符串对的个数。解题报告其实马...