| 题目名称 | 1919. [CF 293B]不同的路径 |
|---|---|
| 输入输出 | distinctpaths.in/out |
| 难度等级 | ★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 11 |
| 题目来源 |
 cstdio
于2015-03-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 0.274 s | 19.80 MiB | C++ |
| 关于 不同的路径 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这题的做法真是哔了狗了
——没错，我把题搬过来就是为了吐槽这一句话 | ||||
【题目描述】
你有一个n*m的矩形网格。一些格子中已经涂上了k种颜色中的某些颜色。你需要给所有未染色格子用这k种颜色染色，使得任意一条从左上角到右下角的路径都不包含两个同色格子。路径只能向右或向下。
输出答案模1000000007（10^9+7）的值。
【输入格式】
第一行包含三个整数n,m,k（1<=n,m<=1000,1<=k<=10）。接下来的n行每行包含m个整数，表示了网格的这一行。0代表相应的格子未被染色，否则就是这个格子已被染上的颜色，颜色是一个1~k的正整数。
【输出格式】
输出一行一个整数，代表可能的染色方案数模10^9+7的值。
【样例输入】
Input
2 2 4 0 0 0 0
Output
48
Input
2 2 4 1 2 2 1
Output
0
Input
5 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
3628800
Input
2 6 10 1 2 3 4 5 6 0 0 0 0 0 0
Output
4096