洛谷 P3758 [TJOI2017]可乐

Description

  • 加里敦星球的人们特别喜欢喝可乐。因而,他们的敌对星球研发出了一个可乐机器人,并且放在了加里敦星球的1号城市上。这个可乐机器人有三种行为: 停在原地,去下一个相邻的城市,自爆。它每一秒都会随机触发一种行为。现 在给加里敦星球城市图,在第0秒时可乐机器人在1号城市,问经过了t秒,可乐机器人的行为方案数是多少?

Input

  • 第一行输入两个正整数况N,M,N表示城市个数,M表示道路个数。(1 <= N <=30,0 < M < 100)

    接下来M行输入u,v,表示u,v之间有一条道路。(1<=u,v <= n)保证两座城市之间只有一条路相连。

    最后输入入时间t

Output

  • 输出可乐机器人的行为方案数,答案可能很大,请输出对2017取模后的结果。

Sample Input

Sample Output

Data Size

  • 对于20%的pn,有1 < t ≤ 1000

    对于100%的pn,有1 < t ≤ 10^6。

题解:

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 35
#define mod 2017
using namespace std;

struct Node
{
    Node() {memset(m, 0, sizeof(m));}
    int m[N][N];
}a;
int n, m, k, ans;

Node cal(Node x, Node y)
{
    Node z;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k <= n; k++)
                z.m[i][j] += ((x.m[i][k] % mod) * (y.m[k][j] % mod)) % mod,
                z.m[i][j] %= mod;
    return z;
}

Node power(Node a, int b)
{
    Node r = a, base = a;
    while(b)
    {
        if(b & 1) r = cal(r, base);
        base = cal(base, base);
        b >>= 1;
    }
    return r;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) a.m[i][0] = 1; //自爆
    for(int i = 0; i <= n; i++) a.m[i][i] = 1; //停留
    for(int i = 1; i <= m; i++)
    {
        int u, v; cin >> u >> v;
        a.m[u][v] = a.m[v][u] = 1;
    }
    cin >> k;
    a = power(a, k - 1);
    for(int i = 0; i <= n; i++)
        ans += a.m[1][i] % mod,
        ans %= mod;
    cout << ans;
    return 0;
}
02-01 12:22