#P8084. 「COCI 2015.3」JANJE

    ID: 7177 传统题 1000ms 64MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1700普及+/提高-顶点着色乘法原理补集计数加法原理线性 DP滚动数组2015COCI

「COCI 2015.3」JANJE

题目描述

年轻的 Bojan 现在是一名成功的电气工程专业学生,从小就喜欢涂色。想起童年时漫不经心的日子,他决定买一本涂色书和 kk 种颜色的颜料,然后开始工作。有趣的是,Bojan 不喜欢五颜六色的图片,所以他决定每张图片最多使用三种不同的颜色着色。此外,Bojan 永远不会用同一种颜色给两个相邻的区域上色,如果两个区域的边缘至少有一个连接点,则被视为相邻。例如,下图用 44 和 33 表示的区域是相邻的,而区域 11 和 22 则不是。此外,下面这张图片的着色方式符合 Bojan 的所有要求。

在开始给一张图片上色之前,Bojan 会问自己有多少种方法可以给这张图上色,从而满足他的所有条件。鉴于 Bojan 是学电气工程的,可以理解的是,组合学不是他的强项,所以他向你寻求帮助。

输入格式

输入仅一行两个整数 n,kn,k,分别代表涂色书里面的图片编号和 Bojan 的颜料拥有的颜色数量。

涂色书将会在附件中给出(即文件 Happy coloring book.pdf,请点击页面右侧的「文件」按钮查看),涂色书里面的图片按照先后顺序依次编号为 11 到 88。

输出格式

输出仅一行一个整数,代表 Bojan 在满足自己所有要求的上色方式的个数。只要至少有一个区域的颜色不同,就视为不同的上色方式。

2 2
0
5 3
12
7 3
96

数据范围与提示

对于所有数据,1⩽n⩽81\leqslant n\leqslant 8,1⩽k⩽10001\leqslant k\leqslant 1000。

图片对应的邻接图

以下是原涂色书图片的文字索引。每个顶点代表一个需要上色的区域,每条无向边代表一对相邻区域。未列出的区域对不相邻,图片外部的背景不参与上色。

  1. 毛毛虫:20 个区域组成一条链。从头到尾编号 11 至 2020,边为 (i,i+1)(i,i+1)(1≤i<201\le i<20)。眼睛、触角和脸部的线条不是独立的涂色区域。
  2. 海边小屋:顶点 1 为墙面,2 为门,3、4 为一扇窗的两格,5、6 为另一扇窗的两格,7 为屋顶,8 为屋顶内的圆。边为 (1,i)(1,i)(2≤i≤72\le i\le7)以及 (3,4),(5,6),(7,8)(3,4),(5,6),(7,8)。
  3. 标志:顶点 1 为大圆内扣除两个小区域后的部分,另外三个区域是大圆外侧的框内区域和圆内的两个小区域。边为 (1,2),(1,3),(1,4)(1,2),(1,3),(1,4)。
  4. 雪人:顶点 1 为帽子,顶点 2 至 5 依次为从上到下的四个圆形区域(不含内部纽扣)。边包括链 (1,2),(2,3),(3,4),(4,5)(1,2),(2,3),(3,4),(4,5)。顶点 3、4、5 上分别有 2、3、4 个纽扣,每个纽扣是只与所在圆相邻的一个顶点。
  5. 抽象球:顶点 1、2 为外环的上、下两部分,顶点 3 为中间完整的环,顶点 4、5 为内圆的上、下两部分。边为 (1,2),(1,3),(2,3),(3,4),(3,5),(4,5)(1,2),(1,3),(2,3),(3,4),(3,5),(4,5)。
  6. 金字塔:从上往下有 10 行,第 rr 行有 rr 块砖。顶点 (r,c)(r,c) 是该行从左数第 cc 块。同一行的相邻砖块连边;若 r<10r<10,(r,c)(r,c) 还和下一行的 (r+1,c),(r+1,c+1)(r+1,c),(r+1,c+1) 连边。
  7. 雏菊:顶点 1 为茎,2 为花盆,3、4 为一片叶的两半,5、6 为另一片叶的两半,7 为花瓣连成的区域,8 为花心。邻接边与图 2 的编号完全相同。
  8. 蹦床:30 个白色区域构成一个环,按圆周顺序编号,边为 (i,i+1)(i,i+1)(1≤i<301\le i<30)及 (30,1)(30,1)。灰色内部不参与上色。

本站涂色书附件 · COCI 原题和涂色书