P3758 [TJOI2017]可乐
P3758 [TJOI2017]可乐
[TJOI2017]可乐
题目描述
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 1 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 0 秒时可乐机器人在 1 号城市，问经过了 t 秒，可乐机器人的行为方案数是多少？
输入输出格式
输入格式
第一行输入两个正整数 N，M。N 表示城市个数，M 表示道路个数。 接下来 M 行每行两个整数 u，v，表示 u，v 之间有一条道路。保证两座城市之间只有一条路相连，且没有任何一条道路连接两个相同的城市。 最后一行是一个整数 t，表示经过的时间。
输出格式
输出可乐机器人的行为方案数，答案可能很大，请输出对 2017 取模后的结果。
输入输出样例
输入样例 #1
3 21 22 32
输出样例 #1
8
构造出整张图的 0 - 1邻接矩阵 E， 令E自乘t次得到新矩阵G. G[x][y]表示 x 走 t 步到 y 的方案数
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, m;const int N = 35, mod = 2017;int f[N][N], g[N][N];int t;struct Martix{
int f[N][N]; void clear()
{ memset(f, 0, sizeof f);
}
Martix operator*(const Martix b)
{
Martix c;
c.clear(); for(int i = 0; i <= 30; i++)
{ for(int k = 0 ;k <= 30; k++)
{ for(int j = 0; j <= 30; j++)
{
c.f[i][j] += f[i][k] * b.f[k][j];
c.f[i][j] %= mod;
}
}
} return c;
}
}E;Martix qp(Martix a,int b){
Martix res = E;
b--; while(b)
{ if(b & 1) res = res * a;
a = a * a;
b >>= 1;
} return res;
}int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= m; i++)
{ int u, v; scanf("%d %d", &u, &v);
E.f[u][v] = E.f[v][u] = 1;
} for(int i = 0; i <= n; i++)
{
E.f[i][i] = 1;
E.f[i][0] = 1;
} scanf("%d", &t);
E = qp(E, t );
int ans = 0; for(int i = 0; i <= n; i++)
{
ans += E.f[1][i];
ans %= mod;
} printf("%d", ans); return 0;
}