洛谷6620 [省选联考 2020 A 卷] 组合数问题
LuoguLOJ分析预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <b...
标签 排列组合 下的文章
- 首页
- 排列组合
洛谷3757 [CQOI2017]老C的键盘
LuoguLOJ分析为什么 17 年省选还出 13 年的题的弱化版啊设 $dp_{u,i}$ 表示以 $u$ 为根的子树，$u$ 的排名为 $i$ 的方案数。转移时将 $v$ 合并到 $u$ 中，在 $i+j-1$ 个比 $u$ 小的数中选出 $j$ 个放在 $v$ 子树中，在 $sz_u+sz_v-i-j$ 个比 $u$ 大的数中选出 $sz_v-j$ 个放在 $v$ 子树中，即乘上两个组...
洛谷5364 [SNOI2017]礼物
LuoguLOJ分析设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理可能需要特判 $n\leq 2$ 的情况。代码// ========...
LOJ6044 「雅礼集训 2017 Day8」共
LOJ分析树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点（$1$ 的深度一定为奇数）。将深度为奇数的点作为左部点、深度为偶数的点作为右部点，两部分间两两连边，则问题变为求生成树个数。考虑 Prufer 序列，则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次，故生成树个数为 $k^{n-k...
洛谷3746 [六省联考2017]组合数问题
LuoguLOJ分析考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移直接矩阵快速幂即可。需要注意的是 $k=1$ 时转移矩阵是 $[2]$。代码// =============================...
CF814E An unavoidable detour for home
CodeforcesLuogu分析显然对于合法的图，满足不在最短路树上边连接的点在同一层。设 $f_{i,j}$ 表示前 $i$ 个点，$[i-j+1,i]$ 中的点在同一层时的方案数，$g_{i,j,k}$ 表示这一层有 $i$ 个点，上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。$f$ 的转移不难得到：枚举上一层的...
LOJ6503 「雅礼集训 2018 Day4」Magic
LOJ分析容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。代码// ======...
洛谷5400 [CTS2019]随机立方体
LuoguLOJ分析为了方便，设 $n<m<l$，$V=nml$。考虑容斥，求出至少有 $i$ 个极大数的方案数 $c_i$。那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。首先考虑求选出 $i$ 个数的方案数 $f_i$，不难得到总时间复杂度 $\mathcal{O}(n)$。代码// ========...
LOJ6495 「雅礼集训 2018 Day1」树
LOJ分析设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。转移讨论一下整棵树最深的节点在哪里即可边界为 $dp_{1,1}=dp_{1,2}=1$。代码偷懒把第一问打了个表 QAq// =====...
洛谷3270 [JLOI2016]成绩比较
LuoguLOJ分析考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即总时间复杂度为 $\mathcal{O}(n^2m)$。代码// ====================...