题目链接
解题思路
矩阵上的线段树。
因为矩阵有分配律（A+B）C = AC + BC，所以计算总和时直接把增量矩阵乘上去就行了。用矩阵快速幂。
fib的计算尽量拉到主函数计算。
代码
#include#include #define MAX_SIZE 100010const int MOD_NUM = 1e9 + 7;typedef long long ll;struct mat { mat() {} mat(int a, int b, int c, int d) { ans[0][0] = a; ans[0][1] = b; ans[1][0] = c; ans[1][1] = d; } int ans[2][2]; bool JudgeOne() { for(int i=0; i<2; i++) for(int j=0; j<2; j++) if(i == j && ans[i][j] != 1 || i != j && ans[i][j] != 0) return false; return true; } void SetOne() { for(int i=0; i<2; i++) for(int j=0; j<2; j++) ans[i][j] = (i == j) ? 1 : 0; } mat operator *(const mat &b)const { mat c(0,0,0,0); for(int k=0; k<2; k++) for(int i=0; i<2; i++) for(int j=0; j<2; j++) c.ans[i][j] = (c.ans[i][j] + (ll)ans[i][k] * b.ans[k][j]) % MOD_NUM; return c; } mat operator +(const mat &b)const { mat c; for(int i=0; i<2; i++) for(int j=0; j<2; j++) c.ans[i][j] = (ans[i][j] + b.ans[i][j]) % MOD_NUM; return c; }};struct node { mat sum; mat tempt; }tree[4*MAX_SIZE];mat a[MAX_SIZE];mat temp;mat cal_fib(int x){ mat c; mat t(0,1,1,1); c.SetOne(); while(x) { if(x & 1) c = c * t; t = t * t; x = x >> 1; } return c;}void build(int l, int r, int root){ tree[root].tempt.SetOne(); if(l == r) { tree[root].sum = a[l]; return ; } int mid = (l + r) / 2; build(l, mid, root*2); build(mid+1, r, root*2+1); tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}void down(int root){ tree[root*2].sum = tree[root*2].sum * tree[root].tempt; tree[root*2].tempt = tree[root*2].tempt * tree[root].tempt; tree[root*2+1].sum = tree[root*2+1].sum * tree[root].tempt; tree[root*2+1].tempt = tree[root*2+1].tempt * tree[root].tempt; tree[root].tempt.SetOne();}void query_1(int l, int r, int L, int R, int root, mat value){ if(L == l && r == R) { tree[root].tempt = tree[root].tempt * value; tree[root].sum = tree[root].sum * value; return ; } if(!tree[root].tempt.JudgeOne()) { down(root); } int mid = (L + R) / 2; if(r <= mid) query_1(l, r, L, mid, root*2, value); else if(l > mid) query_1(l, r, mid+1, R, root*2+1, value); else { query_1(l, mid, L, mid, root*2, value); query_1(mid+1, r, mid+1, R, root*2+1, value); } tree[root].sum = tree[root*2].sum + tree[root*2+1].sum;}int query_2(int l, int r, int L, int R, int root){ if(L == l && r == R) { return tree[root].sum.ans[0][1]; } if(!tree[root].tempt.JudgeOne()) { down(root); } int ret = 0; int mid = (L + R) / 2; if(r <= mid) ret = query_2(l, r, L, mid, root*2); else if(l > mid) ret = query_2(l, r, mid+1, R, root*2+1); else { ret = query_2(l, mid, L, mid, root*2) + query_2(mid+1, r, mid+1, R, root*2+1) % MOD_NUM; } return ret % MOD_NUM;}int main(){ int n, m, d; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { mat base(0, 1, 1, 1); scanf("%d", &d); a[i] = cal_fib(d); } build(1, n, 1); for(int i=0; i