ZOJ-3772 Calculate the Function(线段树，矩阵乘法)

超、凢脫俗 2022-06-03 09:08 160阅读 0赞

Calculate the Function

--------------------

Time Limit: 2 Seconds       Memory Limit: 65536 KB

--------------------

You are given a list of numbers A1 A2 .. AN and M queries. For the i-th query:

*  The query has two parameters Li and Ri.
 *  The query will define a function Fi(x) on the domain \[Li, Ri\] ∈ **Z**.
 *  Fi(Li) = ALi
 *  Fi(Li + 1) = A(Li + 1)
 *  for all x >= Li + 2, Fi(x) = Fi(x - 1) + Fi(x - 2) × Ax

You task is to calculate Fi(Ri) for each query. Because the answer can be very large, you should output the remainder of the answer divided by 1000000007.

#### Input ####

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

The first line contains two integers N, M (1 <= N, M <= 100000). The second line contains N integers A1 A2 .. AN (1 <= Ai <= 1000000000).

The next M lines, each line is a query with two integer parameters Li, Ri (1 <= Li <= Ri <= N).

#### Output ####

For each test case, output the remainder of the answer divided by 1000000007.

#### Sample Input ####

1
    4 7
    1 2 3 4
    1 1
    1 2
    1 3
    1 4
    2 4
    3 4
    4 4

#### Sample Output ####

1
    2
    5
    13
    11
    4
    4

题意：

给你n个数，A1,A2......An，然后有m次查询，每次查询给你一个L和R，然后令F(L)=AL,F(L+1)=AL+1。

然后告诉你你递推式F(n)=F(n-1)+F(n-2)*An，求F(R)。

思路：

看到这个数据范围，第一反应是矩阵快速幂，后来发现每次乘的矩阵都在变化，所以想到应该是用线段树去优化。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <iterator>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    #include <time.h>
    #define lson rt<<1
    #define rson rt<<1|1
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)	res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    struct Mat {
    	LL n, m;   //行列  
    	LL mat[3][3];
    };
    Mat operator *(Mat a, Mat b) {  //矩阵相乘    
    	Mat c;
    	memset(c.mat, 0, sizeof(c.mat));
    	c.n = a.n, c.m = b.m;
    	for (int i = 1; i <= a.n; i++) {
    		for (int j = 1; j <= b.m; j++) {
    			for (int k = 1; k <= a.m; k++) {
    				c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % MOD;
    				c.mat[i][j] = (c.mat[i][j] % MOD + MOD) % MOD;
    			}
    		}
    	}
    	return c;
    }
    
    struct node
    {
    	int l, r, mid;
    	Mat res;
    }t[MAXN << 2];
    
    Mat a[MAXN];
    Mat ans;
    
    void pushup(int rt)
    {
    	t[rt].res = t[rson].res*t[lson].res;
    }
    void build(int l, int r, int rt)
    {
    	int m = (l + r) >> 1;
    	t[rt].l = l, t[rt].r = r;
    	t[rt].mid = m;
    	if (l == r)
    	{
    		t[rt].res = a[l];
    		return;
    	}
    	build(l, m, lson);
    	build(m + 1, r, rson);
    	pushup(rt);
    }
    void query(int p, int q, int rt)
    {
    	if (p <= t[rt].l&&t[rt].r <= q)
    	{
    		ans = ans*t[rt].res;
    		return;
    	}
    	if (q>t[rt].mid)
    		query(p, q, rson);
    	if (p <= t[rt].mid)
    		query(p, q, lson);
    }
    
    int main()
    {
    	int T;
    	scanf("%d", &T);
    	int n, m;
    	int A, B;
    	Mat p;
    	p.m = 1;
    	p.n = 2;
    	while (T--)
    	{
    		scanf("%d%d", &n, &m);
    		for (int i = 1; i <= n; i++)
    		{
    			a[i].m = 2;
    			a[i].n = 2;
    			a[i].mat[1][1] = 1;
    			scanf("%lld", &a[i].mat[1][2]);
    			a[i].mat[2][1] = 1;
    			a[i].mat[2][2] = 0;
    		}
    		build(1, n, 1);
    		for (int i = 1; i <= m; i++)
    		{
    			scanf("%d%d", &A, &B);
    			p.mat[1][1] = a[A + 1].mat[1][2];
    			p.mat[2][1] = a[A].mat[1][2];
    			if (B - A  == 0)
    				printf("%lld\n", p.mat[2][1] % MOD);
    			else if (B - A  == 1)
    				printf("%lld\n", p.mat[1][1] % MOD);
    			else
    			{
    				ans.m = 2;
    				ans.n = 2;
    				ans.mat[1][1] = 1;
    				ans.mat[1][2] = 0;
    				ans.mat[2][1] = 0;
    				ans.mat[2][2] = 1;
    				query(A + 2, B, 1);
    				p = ans*p;
    				printf("%lld\n", p.mat[1][1] % MOD);
    			}
    		}
    	}
    }