#P2435. 染色
染色
题目背景
此题时限2s
此题时限2s
此题时限2s
题目描述
有一个 n 行 m 列的格点图,你需要给每个点上染上 k 种颜色中的一种,要求没有两个相邻点颜色相同。给定第一行与最后一行的染色,试求总染色方案数。
输入格式
第一行三个整数 n,m,k。
第二行 m 个整数,第一行的染色方案,用 0~k-1 表示每种颜色。
第三行 m 个整数,最后一行的染色方案,用 0~k-1 表示每种颜色。
输出格式
一个整数,表示答案,对 376544743 取模。
3 2 3
1 0
1 0
3
提示
样例解释,三种方案:
1 0| 1 0| 1 0 0 1| 0 2| 2 1 1 0| 1 0| 1 0
no n<= m<= k=
1 5 5 2
2 10^7 100000 2
3 20 3 3
4 50 同上 同上
5 100 6 同上
6 同上 同上 同上
7 50 4 4
8 同上 同上 同上
9 100 8 同上
10 同上 同上 同上