1970E3. Trails(Hard)

dp,matrices,2200, https://codeforces.com/problemset/problem/1970/E3

【马铉钦25化院】题目描述与E1完全相同，n的取值改为1≤n≤ $10^{9}$ ,m的取值改为1≤m≤ $10^{5}$ . 由于m的取值增大，上面的方法无疑会TLE，我们需要另辟蹊径。由于 $m \times m$ 方阵乘法需要 $O (m^{3}$ )，我们希望能够降低进行乘法的方阵的边长。观察方阵F的生成公式： $f_{i j} = b_{i} b_{j} + b_{i} c_{j} + c_{i} b_{j} = (b_{i} + b_{j}) (c_{i} + c_{j}) - c_{i} c_{j}$ . 这是一个秩为2的方阵，我们能不能把它的乘方化成一个 $2 \times 2$ 矩阵的乘方呢？其实是可以的。注意到 $F = D \times E$ ,其中D是一个 $n \times 2$ 矩阵，满足

{\begin{cases} d_{i 0} = b_{i} + c_{i} \\ d_{i 1} = c_{i} \end{cases}

E是一个 $2 \times n$ 矩阵，满足

{\begin{cases} e_{0 j} = b_{j} + c_{j} \\ e_{1 j} = - c_{j} \end{cases}

那么，我们有：$$F^n=(D\times E)(D\times E)(D\times E)...(D\times E)=D(E\times D)(E\times D)...(E\times D)E$$ 而这里的 $E \times D$ 就是所需的 $2 \times 2$ 矩阵了。实现代码如下：

python

r=1000000007
def muls(ma1,ma2,ro1,co1,ro2,co2):#实现矩阵乘法
    res=[[0]*co2 for i in range(ro1)]
    for i in range(ro1):
        for j in range(co2):
            c=0
            for t in range(co1):
                c+=ma1[i][t]*ma2[t][j]%r
            res[i][j]=c%r
    return res

m,n=map(int,input().split())
lis=list(map(int,input().split()))
lil=list(map(int,input().split()))
r1,r2,r3=0,0,0
for i in range(m):
    r1+=(lis[i]+lil[i])**2
    r2+=(lis[i]+lil[i])*lil[i]
    r3+=lil[i]**2
    r1,r2,r3=r1%r,r2%r,r3%r
mat=[[r1,r2],[-r2,-r3]]#求出E*D
me=[[1,0],[0,1]]

nb=bin(n-1)[2:]
for i in nb[::-1]:
    if i=='1':
        me=muls(me,mat,2,2,2,2)
    mat=muls(mat,mat,2,2,2,2)

out=[[lis[i]+lil[i] for i in range(m)],[-lil[j] for j in range(m)]]#矩阵E

a1,b1=lis[0]+lil[0],lil[0]    
out=muls(me,out,2,2,2,m)
cou=0
for i in range(m):#只需要结果的第一行的和：如果这里求出整个m*m方阵会MLE
    cou+=out[0][i]*a1+out[1][i]*b1
    cou=cou%r
    
print(cou)

1970E3. Trails(Hard) ​

1970E3. Trails(Hard)