神奇的跑鞋

1s,512M

题目背景

放假了，nsoi的同学准备回家，学校和家之间有许多的城镇（按1到N编号，学校也看成城镇），城镇与城填之间有道路连通。小S的家就位于某个城镇。现在小S想尽快回家，所以他会走一条最短路回家。不过小S还有一双神奇的跑鞋，（它可以让小S从一个城镇到另一个不花时间（可以把距离看成0），当然跑鞋的能量是有限的，他最多可以用3次）。现在要你解决的是小s回家所走过的最短距离。输入：第一行四个整数（N，S，H，T）表示点的个数（N<=400),学校的编号，家的编号，以及跑鞋使用的次数。接下来M行，每行3个数，A,B,C表示A、B城镇的距离为C。输出：一个数表示最短距离，不通输出-1. 样例：输入： 3 1 3 1 1 2 5 1 3 100 2 3 1 输出： 0

以上内容和本题无任何关系。

题目描述

你有一双神奇的跑鞋。在白天是跑鞋，晚上变成了皮鞋。

作为门卫，你每天的工作就是开锁。平面上有 $n\times m$ 个锁，排成 $n$ 行 $m$ 列，记第 $i$ 行第 $j$ 列的锁为 $(i,j)$。白天 $(i,j)$ 和 $(i-1,j),(i,j-1)$ 连接着一条长为 $1$ 的线，线都是双向的（即相邻的锁之间有一条线）。但晚上要修线，你的皮鞋只能在给定的 $n\times m-1$ 条线上行走，保证锁之间仍两两连通，形成一棵树。

你想知道这双神奇的跑鞋是否有用，否则你不如加 QQ2745518585 去买一双洞洞鞋。

对于一个锁的集合：选择一个锁作为起点，沿着线访问所有集合中的锁，最后回到起点。定义代价为所有方案中路径总长的最小值。当白天的代价等于晚上的代价时，称这个集合是无用的。

定义 $f(x)$ 为大小为 $x$ 的无用集合的数量，并给定 $t$。

$t=1$ ：求 $\sum_{x\ge2}f(x)$。
$t=2$ ：求 $f(2)$。
$t=3$ ：求 $f(3)$。

答案对 $10^9+7$ 取模。

输入格式

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

接下来 $n$ 行，每行包含 $m$ 个字符，表示晚上的连线情况。当第 $i$ 行第 $j$ 个字符为：

0：$(i,j)$ 和 $(i-1,j),(i,j-1)$ 均无连线。
1：$(i,j)$ 仅与 $(i-1,j)$ 有连线。
2：$(i,j)$ 和 $(i,j-1)$ 有连线。
3：$(i,j)$ 和 $(i-1,j),(i,j-1)$ 均有连线。

保证所有连线能构成一棵树。

输出格式

一行一个整数表示答案。

样例1

输入

2 3 1
020
033

输出

样例2

输入

2 3 2
020
033

输出

样例3

输入

2 3 3
020
033

输出

样例4

见下发文件 $\texttt{shoes4.in/shoes4.ans}$。

数据范围

$1\le n,m\le10^3,1\le t\le3$

sub 顺序是乱的。

Sub1(4 pts)：$n,m\le2$
Sub2(5 pts)：$n=1$
Sub3(9 pts)：$n,m\le50,t=2$
Sub4(11 pts)：$t=2$
Sub5(9 pts)：$n,m\le20,t=3$
Sub6(13 pts)：$t=3$
Sub7(14 pts)：$n,m\le4,t=1$
Sub8(10 pts)：$n,m\le50,t=1$
Sub9(9 pts)：$t=1$；不存在 $(i,j)$ 与 $(i-1,j)$ 和 $(i,j-1)$ 均有连线
Sub10(16 pts)：$t=1$

邂逅编程之美

UOJ

新改错

]. 神奇的跑鞋