今天模拟赛中出现了一个题，需要对一个\(n\)个点，\(m\)条边的图做边覆盖计数，边覆盖是一个边集\(S\subseteqE\)使得任意一个点\(i\)都存在一条边\((u,v)\inE\)满足\(u=i\)或\(v=i\)，即覆盖所有的点。\(n\leq40,m\leq60\)，1s512M。然后被我使用神秘做法冲过去了（然后莫

CF1943D2CountingIsFun(HardVersion)

A每一轮对总分的贡献都是\(2\)，如果\(p_1+p_2+p_3\)为奇数则无解。\(p_1+p_2\lep_3\)，最多\(p_1+p_2\)轮。\(p_1+p_2>p_3\)，可以\(1,2\)轮流将\(3\)耗完，然后互相匹配，最多\(\dfrac{p_1+p_2+p_3}{2}\)。B如何判断一个\(k_0\)是否符合条件？处

很厉害的题，记录下题意是随机一棵无根树，随一个根，每条边存在（能走通）的概率为\(p\)，以根为起点，每次一方选择当前点的一个能走通的儿子走过去，问先手必胜的概率.容易发现可以当成有根树.用\(F(x)\)和\(G(x)\)表示必胜树和必败树的egf，有\[\begin{cases}F(x)=xe^{F(x)}\le

byTheBigYellowDuck联赛前恶补知识点...排列数&组合数从\(n\)元集合中选出\(m\)个元素的有序排列数记为\(A_n^m\)。计算公式为\[\displaystyleA_n^m=n(n-1)(n-2)\cdots(n-m+1)=\dfrac{n!}{(n-m)!}\]从\(n\)元集合中选出\(m\)个元素的无序排列数记为\(C_n^m\)，

Luogu8389[ZJOI2022]树考虑容斥，每个点有三个状态：不钦定、钦定都是叶子、钦定都是非叶子。对于每一种钦定状态都计算答案，然后乘上对应容斥系数即可。叶子的钦定是可做的，考虑非叶子的钦定，我们可以用“容斥套容斥”的思想理解：对于钦定都是非叶子的点\(i\)，考虑用总方案数减去钦定

同样来自@Explodingkonjac学长的讲题。但是我没认真听讲，所以自己想出来了。原本的想法是设对于每一组分别设\(dp_{i,j}\)为当前枚举到第\(i\)个位置，已经钦定了\(j\)个该组中的人投给自己组的方案数。转移就是枚举有多少人投给\(i\)然后容斥。但是可能是我没有处理好，总

因为一组\(x\)可能对应多组\(p\)，考虑怎么让决策唯一化。我们从大到小依次钦定每个值的位置，即倒着遍历\(i=n,n-1,\cdots,1\)，找到最左端的位置\(v\)满足，对于现在还活着的所有区间\(j\)满足\(l_j\lev\ler_j\)，都有\(x_j=v\)，令\(p_j=i\)，然后删去所有包含\(i\)的区间。

题目链接点击打开链接题目解法好牛（难）的题！！！所有都被覆盖不难想到容斥暴力的容斥是钦定集合\(S\)中的位置都没被覆盖，然后把不能填棋子的点都去掉，假设剩下的不受限制的点的个数为\(c\)，则答案为\(\sum2^c(-1)^{|S|}\)这个暴力是很难直接优化的如果一列被有点被钦定了，那么

0.二项式反演0.1.形式\[F(n)=\sum_{i=0}^{n}(-1)^{i}{n\choosei}G(i)\iffG(n)=\sum_{i=0}^{n}(-1)^{i}{n\choosei}F(i)\]\[F(n)=\sum_{i=0}^{n}{n\choosei}G(i)\iffG(n)=\sum_{i=0}^{n}(-1)^{n-i}{n\choosei}F(i)\]\[F(x)=\sum_{i=x}^{n}

F.FancyArrays第一眼感觉是去容斥掉条件1，因为条件2其实挺紧的。不妨用\(f(l,r)\)表示\(a\)值域在\([l,r]\)的方案（满足条件2）。那么答案为\(f(0,+\infty)-f(0,x-1)-f(x+k,+\infty)\)，因为如果选了\([0,x-1]\)的数，那么还要更大的话，一定会选到\([x,x+k-1]\)，所以你要

说是技巧，其实应该是常识。。。2-SAT没学好导致的。首先是一些奇怪的情况。我们假设蓝绿是一组，红黄是一组，椭圆是scc，那么红黄会选黄，蓝绿会选绿，然而绿又能推出红，遂卒。但是这是不可能的。实际上考虑建图时我们干了什么事情。我们建了类似于这样的东西：实际上这两对点是对等

B考虑我们实际上仅仅在钦定\((u,v)\)不切断时需要通过\(v\)所在子树的异或和这个状态来更新\(u\)对应异或和的状态，此时状态内每一位都是独立的。所以直接拆位仍然能够转移，得到\(f_{i,j,0/1}\)表示节点\(i\)子树内第\(j\)位异或和确定情况下的答案。而在钦定\((u,

Saintex1分钟就切啦,有什么好说哒!首先可能想到设\(c_{i,j}\)表示(i,j)被操作的次数,那么答案很好求。但是这个数量并不好记录。如果仅仅钦定(i,j)从小到大之类的东西也不好搞。所以考虑钦定其他的东西。设\(dp_{i,j,k}\)表示前i位,有j个操作(x,y)满足\(x<y\leqi\)

洛谷传送门AtCoder传送门神题！！！！！！！！！/bx全部格子都被覆盖不好处理，考虑钦定\(k\)个格子不被覆盖，容斥系数就是\((-1)^k\)。发现网格的行不一定连续，但是列是连续的。如果一列有格子被钦定，那么这一列就不能放棋子。由此想到枚举不能放棋子的列（至少有一个棋子被钦定的列）集合\(S\)，把

题意对于集合\({1,2,\cdots,n}\)，求它的子集族中，有多少个满足：任意两个子集互不相同；\(1,2,\cdots,n\)都在其中至少出现了\(2\)次。\(n\le3000\)，答案对\(M\)取模。题解第一个限制形同虚设，下面着重考虑第二个限制。考虑到第二个限制集合的每个元素都是等价的，考虑二项

P7154[USACO20DEC]SleepingCowsP按奶牛和牛棚的大小混合排序，由于匹配极大，故钦定奶牛或牛棚不被匹配状态设计：\(f[i][j][0/1]\)表示考虑到第\(i\)个奶牛和牛棚\(j\)个没有被钦定奶牛没有被匹配，是否钦定过不匹配的奶牛过牛棚（\(0/1\)）转移方程：若为奶牛\(f[i][j][0]=f[i-

听不懂（悲）DP知识刷表和填表SleepingCowsP主要难点在提前钦定不用来匹配的牛，状态加一个0/1，代表当前点之前是否有被钦定的牛若当前为牛棚，则\(f_{i,j,0}=f_{i−1,j,0}+(j+1)f_{i−1,j+1,0}\)\(f_{i,j,1}=(j+1)f_{i−1,j+1,1}\)若当前为牛牛，则\(f_{i,j,0}=f_{i−1,j−1,0}\)

题目链接：https://codeforces.com/problemset/problem/1585/F题解：难难难考虑容斥：设\(A_i\)表示\(b_i\neqb_{i+1}\)(\(i=1,2,\cdots,n-1\))时对应的\(\{b_i\}\)方案的答案那么答案就是$$\bigcap_{{i=1}}^{n}A_{i}=|U|-\left|\bigcup_{i=1}^n\overline{A_i}\right|$$

惊奇地发现我的赛时做法也可以通过转化一下计算式优化到\(O(n+m)\)。或许也算是一种另解？首先，我们考虑把后手的决策视为图上的一个自环或一条边。对于每条边，你要对其选择其连接的一个点，且使得其满足两两不同。对先手的决策，则意味着对这个点/边的额外代价，包括无额外代价。（\(|

考虑对于每个合法的序列\(b\)对应出唯一序列的\(a\)：\(a_i\)为所有对应区间\([l_j,r_j]\)包含\(i\)的\(b_j\)的最大值，若没有则为\(1\)。这样填完之后所有\(a_i\)均为其最小可能值，若所有\(b_i\)的值都正确，则序列\(b\)合法。容易发现这样的映射是单射。考虑统计

啥也不会，自闭了，黄队带我飞。AT评分网站[ARC057D]全域木/洛谷/ATdifficulty：3019根据kruskal的过程设计DP。设\(f_{V,i,j}\)表示当前完全图中的各个联通块的大小的可重集为\(V\)，目前考虑加入的边的权值为\(i\)，已经钦定好的边导致未被钦定的有\(j\)条加入到生成树中不

发现很多题解连容斥原理的“钦定”和“至少”的区别都讲不清楚，误导萌新，所以写一下这两个东西的区别“钦定”这个东西是会算重的，而“至少”不会。举个例子吧，比如\(1\2\3\)三个位置不合法，如果我说“钦定”两个位置不合法，那么这里计算方案的时候这个不合法的方案会被计算三次，分

挺套路的DP。第一步是显然的：转换贡献体，DP一条从\((0,0)\)到\((n+1,n+1)\)的路径，然后计算有多少个排列满足这条路径不经过任何一个\((i,p_i)\)。正着统计肯定不好求，考虑容斥。即我们钦定一些路径上的点，满足这些点必须对应某个\((i,p_i)\)，然后计算有多少个\(p\)符合这个

考虑原先求的是SCC为1的方案数，这很困难！因为并没有能够转移到子问题的路径。不妨考虑容斥，即SCC为1的方案数=所有方案数-SCC不为1的方案数。不妨先集合划分出S