学步园

思路：由于M相当之大，因此可以构造矩阵快速幂来求解
mat[i][j]表示第i个被子给第j个被子的水的百分比，如果k==0，则全给自己，mat[i][i]=1.0;
代码如下：

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define MAX 31
using namespace std;
//矩阵乘法一定不要忘记将矩阵初始赋值为0
int n,k,t,m;
double data[21],avg,res;
struct node{
    double kk[MAX][MAX];
}unit,a;
void init()
{
    for(int i=1;i<=MAX;i++)
        for(int j=1;j<=MAX;j++)
        {
            unit.kk[i][j]=(i==j);
            a.kk[i][j]=0;
        }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf",&data[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        if(k==0)
        {
            a.kk[i][i]=1.0;
            continue;
        }
        avg=1.0/k;
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&t);
            a.kk[i][t]=avg;
        }
    }
    scanf("%d",&m);
}
node mul(node aa,node bb)
{
    node cc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cc.kk[i][j]=0;
            for(int p=1;p<=n;p++)
                cc.kk[i][j]=cc.kk[i][j]+(aa.kk[i][p]*bb.kk[p][j]);
        }
    return cc;
}
node pow(node aa,int exp)
{
    node p=aa;
    node q=unit;
    while(exp)
    {
        if(exp&1)
            q=mul(q,p);


        exp/=2;
        p=mul(p,p);


    }
    return q;
}
void cal()
{
    node ans=pow(a,m);
    for(int i=1;i<=n;i++)
    {
        res=0;
        for(int j=1;j<=n;j++)
        {
            res+=(ans.kk[j][i]*data[j]);
        }
        if(i!=1)
            printf(" ");
        printf("%.2lf",res);
    }
    printf("\n");
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        cal();
    }
    return 0;
}