1970E2. Trails(Medium)

dp,matrices,2000, https://codeforces.com/problemset/problem/1970/E2

【马铉钦25化院】题目描述与E1完全相同，n的取值改为1≤n≤${10}^9$. 上面的$O(n{m}^2)$的方法不再能够满足要求。我们重新审视递推式：

$$a(n+1,j)=\sum _{i=1}^{m}a(n,i)(b_i{b}_j+b_i{c}_j+c_i{b}_j)$$

对每一组$i,j$,后面$(b_i{b}_j+b_i{c}_j+c_i{b}_j)$都是一个整体，在固定$j$时只随$i$变化，不妨记作$f_{ij}$。 那么$$a(n+1,j)=\sum_{i=1} ^m a(n,i)f_{ij}$$ 这个格式和matrices的tag不禁让人想到了矩阵的乘法。 我们令$A_0=[1,0,...,0]$为第0天的走法数（只能在1盆地），那么我们有： $A_{i+1}=A_i\times F$ ，其中$F$是一个$m\times m$的方阵，满足$f_{ij}=b_i{b}_j+b_i{c}_j+c_i{b}_j$. 那么，我们有：$A_n=A_0\times F^n$ ,只要求出$F^n$即可。 利用快速幂的思想（联想OJ的T02706：麦森数），我们可以将求$F^n$的时间复杂度降到$O(m^{3}logn$). 代码如下：

from copy import copy
def muls(ma1,ma2):#实现方阵乘法
    res=[[0]*m for i in range(m)]
    for i in range(m):
        for j in range(m):
            c=0
            for t in range(m):
                c+=ma1[i][t]*ma2[t][j]%1000000007
            res[i][j]=c%1000000007
    return res
    
m,n=map(int,input().split())
lis=list(map(int,input().split()))
lil=list(map(int,input().split()))
 
litr=[[0]*m for i in range(m)]
for j in range(m):
    for t in range(m):
        litr[j][t]=lis[t]*(lil[j]+lis[j])+lil[t]*lis[j]#获得方阵F
 

nb=(bin(n-1))[2:]
li=copy(litr)
for i in nb[::-1]:
    if i=='1':
        li=muls(li,litr)
    litr=muls(litr,litr)

print(sum(li[0])%1000000007)