TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4279
  • Problem
  • P4279AfterEvent | CQXYM的养鸡场
    Limits : Time Limit : - MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

    CQXYM为了经验与附魔,建立了养鸡场。CQXYM的养鸡场有 \(n\) 个鸡圈,有些鸡圈之间有道路相连。初始时第 \(i\) 个鸡圈有 \(c_i\) 只鸡,每只小鸡会用一单位时间等概率地去与当前点相连的点。\(t\) 单位时间后,CQXYM去每个鸡圈喂鸡,将该圈的小鸡两两繁殖一次,每繁殖一次小鸡,CQXYM可以获得一点经验。CQXYM想知道繁殖完小鸡后获得经验的期望点数。

    Input Format

    第一行输入两个数 \(n,t\)

    第二行输入 \(n\) 个数,第 \(i\) 个数为初始该圈的小鸡数量 \(c_i\)

    接着输入 \(n\) 行,每行输入 \(n\) 个整数,第 \(i\) 行第 \(j\) 列的数 \(g_{i,j}\) 为$1$表示鸡圈 \(i,j\) 之间有边相连,为$0$则表示没有边相连。

    Output Format

    输出一个数,表示期望获得的经验点数模$10^9+7$的值。

    Sample Input

    5 8
    1 2 3 4 5
    0 0 1 0 1
    0 0 0 1 1
    1 0 0 1 0
    0 1 1 0 0
    1 1 0 0 0

    Sample Output

    561920191

    Hint

    对于70%的数据,$1 \leqslant n \leqslant 100,1 \leqslant t \leqslant 10^9$

    对于另外30%的数据,$1 \leqslant n \leqslant 1000,t = 1$

    对于所有数据,$1 \leqslant c_i \leqslant 100,g_{i,j} = g_{j,i}=0$ 或 $1$

    输入的数均为自然数。

    原题UpdateAfterEvent,CQXYM魔改搬运题面