ZOJ Problem Set-3772 Calculate the Function行列+線分ツリー

2878 ワード

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5235
F(x)*A(x+2)+F(x+1)=F(x+2)があるので、行列を作ります.
{0        1}   {F(x)}      {F(x+1)}
{A(x+2) 0{{F(x+1)}={F(x+2)}
線分樹を使って、乗号の左側の行列の積を維持して、マトリックスの相乗の順序に注意して、マトリックスは交換率に合いませんが、結合法則に合います.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)

using namespace std;

typedef long long ll;
const int maxn = 100000+10;
const int mod = 1000000007;
int a[maxn];
struct Mat
{
    int m[2][2];
    void setE()
    {
        m[0][0] = m[1][1] = 1;
        m[0][1] = m[1][0] = 0;
    }
    void setZ()
    {
        m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0;
    }
    void display()
    {
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++)
            {
                printf("%d ", m[i][j]);
            }
            putchar('
'); } } }; Mat mat[maxn * 8]; Mat operator * (const Mat &a, const Mat &b) { Mat ret; ret.setZ(); for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) ret.m[i][j] = ((ll)a.m[i][k]*b.m[k][j] + ret.m[i][j])%mod; return ret; } void Build(int cur, int l, int r) { int m; if(l == r) { mat[cur].m[0][0] = 0; mat[cur].m[0][1] = 1; mat[cur].m[1][0] = a[l]; mat[cur].m[1][1] = 1; }else { m = l + ((r-l)>>1); Build(ls(cur), l, m); Build(rs(cur), m+1, r); mat[cur] = mat[rs(cur)] * mat[ls(cur)]; } } Mat Query(int cur, int l, int r, int ql, int qr) { int m; Mat ret; if(ql <= l && r <= qr) return mat[cur]; else { m = l + ((r-l)>>1); ret.setE(); if(ql <= m) ret = ret * Query(ls(cur), l, m, ql, qr); if(m < qr) ret = Query(rs(cur), m+1, r, ql, qr) * ret; } return ret; } int main() { // freopen("data.in", "r", stdin); int tcas, n, m, l, r; Mat L, R, ret; scanf("%d", &tcas); while(tcas--) { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); Build(1, 1, n); while(m--) { scanf("%d%d", &l, &r); R.m[0][0] = a[l]; R.m[0][1] = 0; R.m[1][0] = a[l+1]; R.m[1][1] = 0; if(r - l >= 2) { L = Query(1, 1, n, l+2, r); ret = L * R; printf("%d
", ret.m[1][0]); } else { printf("%d
", a[r]); } } } return 0; }