UpdateAfterEvent

Description

　　小松鼠打了10个小时的游戏，一脸满足。却发现周围再次围满了游客，逃！

　　她发现整个西湖内的松鼠都以相同的速度在树之间跳跃。每跳跃一次花费一个单位的时间。我们可以把西湖抽象为一张n个点的无向图，初始时每个点上都有若干只松鼠，它们每单位时间都可以沿着一条无向边进行跳跃。

　　对于一只当前在点i的松鼠，它在接下来的一个单位时间内等概率向相邻的点跳跃。更具体地讲，我们称与点i通过一条无向边直接相连的点为与i相邻的点，假设这样的点有p个，那么对于每一个与i相邻的点，在下一时刻都有1/p的概率跳到它。

　　超萌小松鼠已知初始时刻（0时刻）每棵树上的松鼠分布情况，她想知道在T时刻，在同一棵树上的松鼠对数的期望。关于“松鼠对数”的解释：假设有4只松鼠在同一棵树上，那么我们称有6对在同一棵树上的松鼠。为了避免精度误差，我们将答案模10^9 + 7输出。

Input

　　第一行三个数n，T。意义如题面中所述。接下来一行n个数，第i个数ai表示第i个点初始时刻有ai只松鼠。接下来n行，每行n个数，第i行第j个数如果为1表示点i与点j间有无向边相连，为0则表示没有。

Output

　　输出一行一个数，表示T时刻在同一棵树上的松鼠对数的期望在模10^9 +7意义下的答案。

Solution

这道题考察了许多知识点，考察综合能力。

首先，题目总体是考察概率期望，但切忌陷入思路死角，去求每棵树上的最终期望松鼠对数。实际上，我们对于每只松鼠，去求它到某点的概率p,那么每两只松鼠在某点的期望便是p1*p2*1（还有很多可转化为概率来做的期望题）由于要除法取模，要预先递推求出逆元，复习一下公式：inv[1]=1;inv[i]=(mod-mod/i)*inv[mod%i]%mod. 

那么对于松鼠到某点的概率求取，我们先O(N^2)求出最开始互相连点之间的概率，然后每一时刻，枚举中间点，进行概率传递，由于t比较大，可以用矩阵快速幂思想来将其优化到log2n级别。

最后，由于我们计算期望是O（n^3）的，无法过n<=1000的点，发现如下式子：

设p(i,j)为i到j点的概率。假设计算终点在1，则ans=p(1,1)*p(2,1)+p(1,1)*p(3,1)*.....+p(1,1)*p(n,1)+p(2,1)*p(3,1)+p(2,1)*p(4,1)+.......发现可以转化为p(1,1)*(p(2,1)+p(3,1)+p(4,1)+....+p(n,1))+p(2,1)*(p(3,1)+p(4,1)+.....+p(n,1)).由此发现是可以前缀和优化的，由此只用枚举一点和终点，从而变成O(N^2).当然可以每个统计一次，然后最后除以2.貌似更方便哈.....

上代码：

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct matrix{
    ll a[maxn][maxn];
}nd,ans;
int n,t,e[maxn][maxn];
matrix operator *(matrix &x,matrix &y){
    matrix c;
    memset(c.a,0,sizeof(c.a));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++){
        c.a[i][j]=(c.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod;
    }
    return c;
}
void pow(int t){
    for(int i=1;i<=n;i++) ans.a[i][i]=1;
    while(t){
        if(t&1) ans=ans*nd;//最后为1 
        nd=nd*nd;
        t/=2;
    }
}
ll p[maxn][maxn],inv[maxn],v[maxn];
void init(){
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
    inv[1]=1;
    for(int i=2;i<=1000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) scanf("%d",&e[i][j]);
    memset(nd.a,0,sizeof(nd.a));
    for(int i=1;i<=n;i++){
        int res=0;
        for(int j=1;j<=n;j++)  res+=e[i][j];
        for(int j=1;j<=n;j++)  nd.a[i][j]=inv[res]*e[i][j];
    } 
    if(t>1){
        pow(t);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) p[i][j]=ans.a[i][j];
    }
    else{
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) p[i][j]=nd.a[i][j];
    }
    
    ll calc=0; 
    for(int i=1;i<=n;i++){
        ll t1=0,t2=0;
        for(int j=1;j<=n;j++){
            ll tt=(p[j][i]*v[j])%mod;
            t1=(t1+tt)%mod;
            t2=(t2+tt*p[j][i])%mod;
        }
        calc=(calc+(t1*t1%mod-t2+mod)%mod*inv[2]%mod)%mod;
    }
    printf("%lld",calc);
}
int main(){
    init();
    
    return 0;
}