HH去散步
Time Limit: 20 Sec
Memory Limit: 64 MB
Memory Limit: 64 MB
Description
HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地点A走到给定地点B共有多少条符合条件的路径？
Input
第一行：五个整数N，M，t，A，B。
N表示学校里的路口的个数
M表示学校里的 路的条数
t表示HH想要散步的距离
A表示散步的出发点
B则表示散步的终点。
接下来M行
每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。
数据保证Ai ！= Bi,但不保证任意两个路口之间至多只有一条路相连接。
路口编号从0到N -1。
同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。
答案模45989。
N ≤ 20，M ≤ 60，t ≤ 230，0 ≤ A,B
Output
一行，表示答案。
Sample Input
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
Sample Output
4
Solution
看到t的取值范围，容易想到此题的解法为矩阵快速幂。
容易想到，我们可以设dpi, j表示从点i到点j的方案数，出初始时，可以令dpi, j表示图中点i到点j的边的数量，由于边是无向的，所以恒有dpi, j=dpj, i。方案数就是dpt i, j。
于是，我们很容易地得到了以下程序：
int main()
{
int n, m, t, s, e;
matrix dp;
read(n); read(m); read(t); read(s); read(e);
for (int i = 0; i<m;
i++)
{
int from, to;
read(from); read(to);
dp.data[from][to]++;
dp.data[to][from]++;
}
dp = pow(dp, t);
cout << dp.data[s][e] << endl;
return 0;
}
读者不要急于复制，我们忽略了一句十分重要的话“他不会立刻沿着刚刚走来的路走回”。采用如上程序得出的方案数比答案多。
为了解决这一问题，我们容易想到为dp加一个维度，或者改变一个维度的意义，比如，我们设dpk, i, j表示在k时刻，到达点i且上一次经过的边为j的方案数。转移过程比较明确，实现如下：
for (int k = 1; k<t; k++)
{
for (int i = 0; i<n;
i++)
{
for (int j =
graph[i].nex; j; j = graph[j].nex)
{
for (int l = 0; l<m;
l++)
{
if (l == graph[j].num)continue;
dp[k
+ 1][graph[j].to][graph[j].num] += dp[k][i][l];
}
dp[k +
1][graph[j].to][graph[j].num] %= mod;
}
}
}
首先解释各个变量的含义：graph——使用邻接表储存的图，graph[i].num表示边的编号，从零开始，正向边和反向边的编号相同。可如此以来，dp多了一个可以防止走回头路的维度，但少了一个区分起点的维度。似乎无法用矩阵快速幂优化。
这时，我们转换思路！
我们设dpi, j表示从第i条边到第j条边的方案总数，为了方便合并，我们假设计数时不考虑初始边。这样便又可以“生搬硬套”矩阵快速幂了。可是，问题来了，对于下图（即样例）：
初始时，dp10, 3=1（为了区分不同阶段的状态，我们用指数表示经过的边的数量，不包括起始边），dp13, 0=1。用矩阵乘法计算dp20, 0。发现算出的答案是3，显然这包括了走回头路的情况，原因就是我们无法通过状态确定开始移动时的方向，即在边0上，究竟是通过点1到达了边3，还是通过点0、2到达了边3？这样还是没有解决走回头路的问题。我们可以考虑在加一个维度，但这样岂不是又走回了方法二的老路？
其实，区分方向并不复杂，仅需将正向边和反向边用不同的编号标识，如果边的编号从0开始，正向边、反向边的编号相邻，可以用按位异或运算快速得到反向边的编号。
Code
//dp[i][j]^(k-1)——从边i->边j，共经过k条边(不包括起点）的方案数
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const unsigned int mod = 45989;
void read(int &x)
{
x = 0; char ch = getchar(); bool f = 0;
while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }
while (ch >= '0'&&ch
<= '9') { x = x * 10 + ch - 48; ch = getchar();
}
if (f)x = -x;
}
struct matrix
{
unsigned int data[120][120];
matrix operator*(const matrix &b)const
{
matrix c;
for (int i = 0;
i<120; i++)
{
for (int j = 0;
j<120; j++)
{
c.data[i][j]
= 0;
for (int k = 0;
k<120; k++)
{
c.data[i][j]
+= data[i][k] * b.data[k][j];
c.data[i][j]
%= mod;
}
}
}
return c;
}
};
matrix pow(matrix a, int b)
{
matrix m = a, ans;
memset(ans.data, 0, sizeof(ans.data));
for (int i = 0;
i<120; i++)
{
ans.data[i][i]
= 1;
}
while (b)
{
if (b & 1)ans = ans*m;
m = m*m;
b >>= 1;
}
return ans;
}
matrix dp;
struct graph_t
{
int to, nex, num;
}graph[181];
int tail = 20;
int times = -1;
void addedge(int u, int v)
{
int tmp1 = graph[u].nex, tmp2 =
graph[v].nex;
graph[u].nex = ++tail,
graph[v].nex = ++tail;
graph[tail -
1].to = v, graph[tail].to = u;
graph[tail -
1].num = ++times, graph[tail].num = ++times;
graph[tail -
1].nex = tmp1, graph[tail].nex = tmp2;
}
int main()
{
int n, m, t, s, e;
read(n); read(m); read(t); read(s); read(e);
for (int i = 0; i<m;
i++)
{
int from, to;
read(from); read(to);
addedge(from, to);
}
for (int i = 0; i<n;
i++)
{
for (int j =
graph[i].nex; j; j = graph[j].nex)
{
for (int k =
graph[i].nex; k; k = graph[k].nex)
{
if (graph[j].num
!= graph[k].num)
{
dp.data[graph[j].num
^ 1][graph[k].num]++;
}
}
}
}
dp = pow(dp, t - 1);
unsigned int ans = 0;
for (int i =
graph[s].nex; i; i = graph[i].nex)
{
for (int j =
graph[e].nex; j; j = graph[j].nex)
{
ans +=
dp.data[graph[i].num][graph[j].num ^ 1];
ans %=
mod;
}
}
cout << ans << endl;
return 0;
}
没有评论:
发表评论