洛谷3643 [APIO2016]划艇
Luogu LOJ 分析 一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校,第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数,然而第二维高达 $10^9$。 可以想到把所有端点离散化一下(这里改成左闭右开区间会方便一些),$dp_{i,j}$ 的定义改为前 $i$ 个学校,第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。 考虑转移。我们枚举一个 $...
Luogu LOJ 分析 一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校,第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数,然而第二维高达 $10^9$。 可以想到把所有端点离散化一下(这里改成左闭右开区间会方便一些),$dp_{i,j}$ 的定义改为前 $i$ 个学校,第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。 考虑转移。我们枚举一个 $...
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数,不难得到 可以发现是一个差卷积的形式,于是直接 NTT 即可。 代码 // ===============...
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数,$g_i$ 为 $i$ 个点的无向图个数,那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
Luogu LOJ 分析 预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include...
Luogu LOJ 分析 设 $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$ 的情况。 代码 //...
LOJ 分析 树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。 首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点($1$ 的深度一定为奇数)。 将深度为奇数的点作为左部点、深度为偶数的点作为右部点,两部分间两两连边,则问题变为求生成树个数。 考虑 Prufer 序列,则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次,故生成树个数为 $k...
Luogu LOJ 分析 考虑要求的东西的组合意义,为从 $nk$ 个物品中选出 $t$ 个物品的方案数,其中 $t\bmod k=r$。 考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品,选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移 直接矩阵快速幂即可。 需要注意的是 $k=1$ 时转移矩阵是 $[2]$。 代码 // ====================...
Codeforces Luogu 分析 显然对于合法的图,满足不在最短路树上边连接的点在同一层。 设 $f_{i,j}$ 表示前 $i$ 个点,$[i-j+1,i]$ 中的点在同一层时的方案数,$g_{i,j,k}$ 表示这一层有 $i$ 个点,上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。 $f$ 的转移不难得到:枚...
LOJ 分析 容易想到容斥,计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$,因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌,所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
Luogu LOJ 分析 为了方便,设 $n<m<l$,$V=nml$。 考虑容斥,求出至少有 $i$ 个极大数的方案数 $c_i$。 那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。 首先考虑求选出 $i$ 个数的方案数 $f_i$,不难得到 总时间复杂度 $\mathcal{O}(n)$。 代码 /...