[BZOJ3231] [Sdoi2008]递归数列 题目大意
给定Ci,i∈[1,k] 定义
若i>k,Ai=Ai−1∗C1+Ai−2∗C2+⋯+Ai−k∗Ck 否则Ai=Bi 询问sum(A)n−sum(A)m−1 k≤15,n,m≤1018 题解
⎡⎣⎢⎢⎢⎢⎢⎢⎢sumnAnAn−1⋮An−k+1⎤⎦⎥⎥⎥⎥⎥⎥⎥==⎡⎣⎢⎢⎢⎢⎢⎢⎢100⋮0C1C11⋮0C2C20⋱⋯⋯⋯⋯⋯⋯CkCk000⎤⎦⎥⎥⎥⎥⎥⎥⎥∗⎡⎣⎢⎢⎢⎢⎢⎢⎢sumn−1An−1An−2⋮An−k⎤⎦⎥⎥⎥⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢⎢⎢100⋮0C1C11⋮0C2C20⋱⋯⋯⋯⋯⋯⋯CkCk000⎤⎦⎥⎥⎥⎥⎥⎥⎥n−k∗⎡⎣⎢⎢⎢⎢⎢⎢⎢sumkAkAk−1⋮A1⎤⎦⎥⎥⎥⎥⎥⎥⎥ CODE