TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5289
  • 题目
  • P5289图论构造三合一 | Trinity题解
    限制 : 时间限制 : - MS   空间限制 : 262144 KB  SPJ
    评测说明 : 1s,256MB
    问题描述

    一个 \(n\) 个点的完全图,将 \(n(n-1)/2\) 条边分成若干组,使每组边构成的特殊子图。

    1. 分成 \(n/2\) 组,每组是一棵树,保证 \(n\) 是偶数。
    2. 分成 \(n-1\) 组,每组是一个匹配,保证 \(n\) 是偶数。
    3. 分成 \((n-1)/2\) 组,每组是一个哈密顿回路,保证 \(n\) 是奇数。

    方案可能很多种,你可以任意输出一种。

    点击查看此题原内容“Trinity题解”

    题解:

    令 $ DP[k][p] $ 是 $ p $ 行 $ k $ 列网格图中的答案,附加条件是每一行至少有一个格子被涂黑。因为答案是 $ \sum DP[M][p]\binom{N}{P} $ ,从现在起,我们将聚焦于对DP表的计算。固定一个 $ k $ 行 $ p $ 列的网格图(这一次,有些行可能是空的)。我们构造与网格图有关的三个矩阵 $ A,B,C $ 。如果我们在右侧附加上第 $ (p+1) $ 列,这三个矩阵会发生什么?
    • 如果第 $ i $ 行在附加前非空, $ A_i $ 会是 $ p+1 $ ,否则 $ A_i $ 的值不变。
    • $ B,C $ 的前 $ p $ 个元素不变。
    • 我们得到两个值 $ B_{p+1},C_{p+1} $ :这两个值依赖于新添加的一列。
    如果一个网格图每一行都非空,则我们称这个网格图是好的。我们可以按下述方法使用一个有 $ p $ 行 $ k $ 列的网格图构造一个 $ p+q $ 行 $ k+1 $ 列的好的网格图。
    • 最初我们有一个 $ p $ 行 $ k $ 列的好的网格图。
    • 在某些位置插入 $ q $ 个空行,现在我们有了一个 $ p+q $ 行 $ k $ 列的网格图。
    • 在右边附加上一个新(不必为空)列。在空行的格子一定是黑色的。现在我们得到了一个有 $ p+q $ 行 $ k $ 列的好的网格图。
    按上述流程更新DP表。对每一个三元组 $ (k,p,q) $ 按 $ k $ 的升序进行方程为" $ DP[k+1][p+q]+=DP[k][p]\times $ 系数"的转移,系数是在上述流程中得到新的三个矩阵 $ A,B,C $ 的方案数:显然三个矩阵的初始值不影响系数。 如何计算系数? 如果 $ q=0 $ ,我们只关心 $ B,C $ 两矩阵的最后一个值,他们是新加入的一列中最靠上或最靠下的黑色格子的位置。有一种情况是新插入的一列是空列,有 $ \binom{p+1}{2} $ 种方案插入的一列不是空列。因此系数是 $ \binom{p+1}{2}+1 $ 。 如果 $ q>0 $ 会发生什么?我们在 $ p $ 个已有的行中插入 $ q $ 个新行。可以视作这是一个 $ p $ 个灰球和 $ q $ 个黑球的序列(黑球满足新插入的行),黑球的位置 $ A_l $ 满足 $ A_l=k+1 $ 。 更多的,我们应该考虑矩阵 $ B,C $ 的最后一个元素,用球的语言就是满足黑球最靠左或最靠右的位置。然而,问题是,我们不知道灰球的信息:它既可以是黑的,也可以不是黑的。数量的排列分析如下:
    • 想象一个有 $ p $ 个灰球和 $ q $ 个黑球的序列。
    • 考虑所有在最右边的一个黑球右边的所有灰球,可以从中选择至多一个并把它涂成红色。
    • 考虑所有在最左边的一个黑球左边的所有回球,可以从中选择至多一个并把它涂成红色。
    麻烦的部分是“最多”;。我们在两个端点各附加一个灰球,现在它变成以下所述:
    • 想象一个有 $ p+2 $ 个灰球和 $ q $ 个白球的序列。两端点都是灰色的。
    • 考虑所有在最右边的一个黑球右边的所有灰球,可以从中选择一个并把它涂成红色。
    • 考虑所有在最左边的一个黑球左边的所有灰球,可以从中选择一个并把它涂成红色。
    现在我们可以把红球当作黑球,现在就是一个有 $ p $ 个灰球和 $ q+2 $ 个黑球的序列,因此,系数就是 $ \binom{p+q+2}{q+2} $ 。 现在我们算出了系数,这个算法时间复杂度为 $ O(N^2M) $ ,可以获得部分分。 如何改进?定义矩阵 $ x,y $ ,初始 $ x $ 为给定, $ y $ 为空。对于每对 $ (p,q) $ 满足 $ q>0 $ ,我们按以下进行运算: \begin{equation*}y_{p+q}+=x_p\times\binom{p+q+2}{q+2}\end{equation*} 我们可以忽略 $ q=0 $ 的情况,因为明显地可以在 $ O(N) $ 时间内完成。) 我们想快速地进行这个操作。仔细观察系数: \begin{equation*}\binom{p+q+2}{q+2}=\frac{(p+q+2)!}{p!}\end{equation*} 因此,令 $ X_p=\frac{x_p}{p!},Y_q=\frac{y_q}{(q+2)!} $ ,可以变形如下: \begin{equation*}y_{p+q}+=X_p\times\frac{1}{(q+2)!}\end{equation*} 这是一个标准的复杂度,并且可以在 $ O(N\log N) $ 地时间内完成。整个算法总的时间复杂度为 $ O(NM\log M) $ 。
    输入格式

    第一行两个数 \(n,k\) ,表示图的规模和任务类型。

    输出格式

    一个 \(n\times n\) 的矩阵,其中 \(p[i][j]\) 表示节点 \(i,j\) 的边属于第几组。你需要保证 \(1\leq p[i][j]=p[j][i]\leq 组数\)\(p[i][i]=0\)

    样例输入 1

    5 3

    样例输出 1

    0 1 2 2 1
    1 0 1 2 2
    2 1 0 1 2
    2 2 1 0 1
    1 2 2 1 0

    样例输入 2

    4 2

    样例输出 2

    0 1 2 3
    1 0 3 2
    2 3 0 1
    3 2 1 0

    样例输入 3

    4 1

    样例输出 3

    0 1 2 1
    1 0 1 2
    2 1 0 2
    1 2 2 0

    提示

    \(2\leq n\leq 1000\)
    \(1\leq k\leq 3\)
    感谢CQXYM提供spj