染色 - Luogu - 题目详情

ID: 1790

远端评测题

2000ms

125MiB

难度: 6

上传者:

标签>

动态规划,dp

题目背景

此题时限2s

有一个 $n$ 行 $m$ 列的格点图，你需要给每个点上染上 $k$ 种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。

第一行三个整数 $n,m,k$ 。

第二行 $m$ 个整数，第一行的染色方案，用 $0\sim k-1$ 表示每种颜色。

第三行 $m$ 个整数，最后一行的染色方案，用 $0\sim k-1$ 表示每种颜色。

一个整数，表示答案，对 $376544743$ 取模。

3 2 3
1 0
1 0

样例解释，三种方案：

1 0| 1 0| 1 0
0 1| 0 2| 2 1
1 0| 1 0| 1 0

测试点编号	$n$	$m$	$k$
$1$	$≤5$		$≤2$
$2$	$≤10^7$	$≤10^5$	$≤2$
$3$	$≤20$	$≤3$	$≤3$
$4$	$≤50$	$≤3$
$5-6$	$≤100$	$≤6$
$7-8$	$≤50$	$≤4$	$≤4$
$9-10$	$≤100$	$≤8$	$≤4$