http://www.bnuoj.com/bnuoj/problem_show.php?pid=16493
【题解】：矩阵快速幂
【code】：
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std; int N;
struct matrix
{
double a[][];
}origin,res; matrix multiply(matrix x,matrix y)
{
matrix temp;
for(int i=;i<=N;i++)
{
for(int j=;j<=N;j++)
{
double ans=;
for(int k=;k<=N;k++)
{
ans+=x.a[i][k]*y.a[k][j];
}
temp.a[i][j]=ans;
}
} return temp;
} matrix calc(int n)
{
while(n)
{
if(n%==)
res=multiply(origin,res);
origin=multiply(origin,origin);
n/=;
}
return res;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
N=n;
double x[];
int i,j;
for(i=;i<=n;i++)
{
scanf("%lf",&x[i]);
}
memset(origin.a,,sizeof(origin.a));
for(i=;i<=n;i++)
{
int k;
scanf("%d",&k);
if(k==) origin.a[i][i]=1.0;
for(j=;j<=k;j++)
{
int p;
scanf("%d",&p);
origin.a[p][i]=1.0/k;
}
}
memset(res.a,,sizeof(res.a));
for(i=;i<=n;i++)
{
res.a[i][i]=;
}
int m;
scanf("%d",&m);
calc(m);
for(i=;i<=n;i++)
{
double ans=;
for(j=;j<=n;j++)
{
ans+=res.a[i][j]*x[j];
}
if(i==)
{
printf("%.2lf",ans);
}
else
{
printf(" %.2lf",ans);
}
}
putchar(); }
return ;
}