飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1973

题意:有n个容器，在每秒每个容器同时向k_i个容器中分配当前的容量*1/k_i，求m秒后各容器中的容量

分析:易知第i+1秒和第i秒有关，所以可以想到矩阵快速幂。主要是构造矩阵，如果第i个向第j个容器分配，则mat i_j为1/k_i;注意如果第i个容器没有向任何一个容器分配，则mat i_i=1（这个使我wa了一发），原始矩阵A就是各个容器的原始容量，最后的A*(mat)^n就是各个容器的最终容量。

//
//  main.cpp
//  zoj2974
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
struct Matrix{
    double mat[23][23];
    
};
double ai[23];
int T;
Matrix mat;
void init(){
    memset(mat.mat,0,sizeof(mat.mat));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&ai[i]);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d",&a);
        if(a==0){
            mat.mat[i][i]=1;
            continue;
        }
        for(int j=1;j<=a;j++){
            double t=1.0/a;
            scanf("%d",&b);
            mat.mat[i][b]=t;
        }
    }
    scanf("%d",&m);
}
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                c.mat[i][j]=c.mat[i][j]+a.mat[i][k]*b.mat[k][j];
            }
        }
    }
    return c;
}
Matrix poww(Matrix x,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=n;i++)ans.mat[i][i]=1;
    while(k>0){
        if(k&1)
            ans=MUL(ans, x);
        x=MUL(x,x);
        k/=2;
    }
    return ans;
}
double ans[23];
void play(){
    memset(ans,0,sizeof(ans));
    Matrix _a=poww(mat,m);
  
    for(int j=1;j<=n;j++){
        for(int k=1;k<=n;k++){
            ans[j]=ans[j]+ai[k]*_a.mat[k][j];
        }
    }
}
void pri(){
    bool fir=1;
    for(int i=1;i<=n;i++)
    {
        if(!fir)printf(" ");
        fir=0;
        printf("%.2f",ans[i]);
    }
    printf("\n");
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    scanf("%d",&T);
    
    while(T--){
        init();
        play();
        pri();
    }
    return 0;
}