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)}
線分樹を使って、乗号の左側の行列の積を維持して、マトリックスの相乗の順序に注意して、マトリックスは交換率に合いませんが、結合法則に合います.
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;
}