洛谷 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。
题解:
- 矩阵快速幂。
- 思路来自Zhang_RQ大大
#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;
}