洛谷6076 [JSOI2015]染色问题
LuoguBZOJ分析考虑容斥。设 $f(i,j,k)$ 为至少 $i$ 行、$j$ 列不涂色且至少有 $k$ 种颜色没有使用的方案数，根据组合意义可以得到直接 $\mathcal{O}(n^3)$ 计算即可。代码// =================================== // author: M_sea // website: http://m-sea-blog...
标签 排列组合 下的文章
- 首页
- 排列组合
AtCoder Grand Contest 005 简要题解
比赛地址STring和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：若 $d$ 为奇数，则应有 考虑计算 $f_i$。容易发现一...
CF886E Maximum Element
CodeforcesLuogu分析设 $f_i$ 表示长度为 $i$ 的不会出错的排列数。转移可以考虑枚举最大值的位置，容易得到总时间复杂度 $\mathcal{O}(n)$。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =========...
BZOJ5093 [Lydsy1711月赛]图的价值
BZOJ分析考虑一个点对答案的贡献。枚举它的出边数量，可以得到贡献为显然是卷积的形式，直接构造多项式然后 NTT 即可做到 $\mathcal{O}(k\log k)$ 计算。然后就做完了。顺便可以切掉【模板】第二类斯特林数·行代码// =================================== // author: M_sea // website: http://m-...
Codechef CNTL Counting is life
CodechefVjudge分析首先第一问很简单，当 $n,k$ 奇偶性相同时答案为 $2^k-1$，否则答案为 $2^k-2$。重点在第二问。我们先考虑 $n,k$ 奇偶性相同的情况，那么相当于选 $n$ 个数，要求每个数都出现奇数次，求方案数。考虑生成函数，出现次数是奇数的 EGF 为同上，可以做到 $\mathcal{O}(n\log p)$ 计算。代码// =============...
洛谷4609 [FJOI2016]建筑师
LuoguLOJ分析所有建筑大概是这个样子的 | | | | | | | | | | | | | | | ||||||||||||我们把最高的那个建筑的左边的每个看得见的建筑加上它右边连续的比它矮的建筑作为一组，最高的那个建筑的右边的每个看得见的建筑加上它左边连续的比它矮的建筑作为一组。（有点绕）那么大概是这个样子（相同数字的在同一组） | | | | | |...
AGC005F Many Easy Problems
AtCoderLuogu分析设要求的东西是 $f_i$，考虑怎么求这个东西。可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但它确实是 NTT 模数。代码// =================================== // author: M...
AtCoder Grand Contest 002 简要题解
比赛地址Range Product简单讨论一下即可。代码Box and Ball简单模拟一下即可。注意盒子里仅有一个球的情况。代码Knot Puzzle能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。代码Stamp Rally先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然，如果 $x,y$ 连通，则为 $sz_x$，否则为 $sz_x+sz_y$。这里...
AtCoder Grand Contest 001 简要题解
比赛地址BBQ Easy排序后相邻的两个放一组即可。正确性显然。Mysterious Light可以发现每次反射之后问题都变为一个子问题，于是直接递归做下去即可。可以发现边界为 $n\bmod x=0$。Shorten Diameter当 $k$ 为偶数时，枚举一个根，然后删掉所有到根距离 $>\frac{k}{2}$ 的点。在所有这样算出来的答案中取 $\min$ 即可。当 $k$ ...