bzoj1875 HH去散步

HH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间 内，走过一定的距离。 但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多 少种散步的方法。 现在给你学校的地图（假设每条路的长度都是一样的都是1），问长度为t，从给定地 点A走到给定地点B共有多少条符合条件的路径

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。 接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

一行，表示答案。

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Day1

矩阵乘法，跟hdu的那道题一样，模数变一下而已。

http://blog.csdn.net/lzr010506/article/details/51136389

换了一种写法。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 45989
#define N 22
using namespace std;
int n,m,t,a,b;
struct Matrix
{
    int map[N * 6][N * 6];
    void clear() {memset(map,0,sizeof(map));}
    friend Matrix operator * (Matrix &a,Matrix &b)
    {
        Matrix ret;
        for(int i = 0; i <= 2 * m; i ++)
            for(int j = 0; j <= 2 * m; j ++)
            {
                ret.map[i][j] = 0;
                for(int k = 0; k <= 2 * m; k ++)      
                    ret.map[i][j] = ret.map[i][j] + a.map[i][k] * b.map[k][j] % mod;
                ret.map[i][j] %= mod;
            }
        return ret;
    }
    friend Matrix operator ^ (Matrix &a,int b)
    {
        Matrix ret;
        ret.clear();
        for(int i = 0; i <= m * 2; i ++) ret.map[i][i] = 1;
        while(b)
        {
            if(b & 1) ret = ret * a;
            a = a * a;
            b >>= 1;
        }
        return ret;
    }
}ori,base;
int head[N],cnt;
struct node
{
    int from,to,next;
}edge[N * 6];
void init()
{
    memset(head,-1,sizeof(head));
    cnt = 1;
}
void edgeadd(int from,int to)
{
    edge[cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].next = head[from];
    head[from] = cnt ++;
}
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch-'0'; ch = getchar(); }
    return x * f;
}
int main()
{
    init();
    n = read();
    m = read();
    t = read();
    a = read();
    b = read();
    a ++;
    b ++;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        x = read();
        y = read();
        x ++;
        y ++;
        edgeadd(x, y);
        edgeadd(y, x);
    }
    for(int i = head[a]; i != -1; i = edge[i].next)
        base.map[0][i] ++;
    for(int i = 1; i < cnt; i ++)
    {
        int x = edge[i].from, y = edge[i].to;
        for(int j = head[y]; j != -1; j = edge[j].next)
            if(j != (i + ((i & 1)? 1: -1)))
                ori.map[i][j] ++;
    }
    ori = ori ^ (t - 1);
    base = base * ori;
    int sum = 0;
    for(int i = 1; i < cnt; i ++)
        if(edge[i].to == b)
            sum = (sum + base.map[0][i])%mod;
    printf("%d\n",sum);
    return 0;
}