#PQJ199x1061. QOJ 199_1061

    ID: 2771 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SDOI 2019动态规划

QOJ 199_1061

SDOI2019 Round 2 Day 1 Problem B. 染色(coloring.c/cpp/pas) Input file: coloring.in Output file: coloring.out Time limit: 3 seconds Memory limit: 256 megabytes 给定2 × n 的格点图。其中一些结点有着已知的颜色,其余的结点还没有被染色。一个合法的染色 方案不允许相邻结点有相同的染色。 现在一共有c 种不同的颜色,依次记为1 到c。请问有多少对未染色结点的合法染色方案? Input 第一行有两个整数n 和c,分别描述了格点图的大小和总的颜色个数。 之后两行,每行有n 个整数:如果是0 则表示对应结点未被染色,否则一定是一个1 到c 的整数 表示对应结点已经染了某一种颜色。 Output 输出一个整数,为总的染色方案数对109 + 9 取模后的值。 Examples coloring.in coloring.out 3 5 1 0 1 0 0 0 172 5 7 1 0 0 0 2 0 0 3 0 0 116370 10 13 0 2 0 0 1 0 2 0 0 3 0 1 0 1 0 0 0 0 4 0 770175525 Page 4 of 8

SDOI2019 Round 2 Day 1 Notes 子任务1:(44 分)1 ≤n ≤10000 且5 ≤c ≤10000;不存在一列有2 个已染色结点;被染色结点 全部位于第一行;第一列和最后一列均有结点已被染色。 子任务2:(32 分)1 ≤n ≤10000 且5 ≤c ≤10000;不存在一列有2 个已染色结点;第一列和最 后一列均有结点已被染色。 子任务3:(12 分)1 ≤n ≤10000 且5 ≤c ≤10000;第一列和最后一列均有结点已被染色。 子任务4:(8 分)1 ≤n ≤10000 且5 ≤c ≤10000。 子任务5:(4 分)1 ≤n ≤100000 且5 ≤c ≤100000。 Page 5 of 8