1284: SP教数学
Description
Output
对于每组数据的2操作，输出一行对1e9 + 7取模的答案
7 4
2 2 1 1 3 3 2
2 1 5
2 6 7
1 3 4 3
2 6 6
Sample Output
6
3
2
题解：
//比赛全是原题 数据要不卡的难受 要不水的暴力能把2^50的复杂度跑过去 也是服气 不想费事安安心心拉VJ不好么TAT 线段树+矩阵快速幂
出题人的解释
我们知道对于斐波那契数可以通过乘以一个矩阵来进行递推。那么对于 +x 这一区间操作，我们可以对这一区间均乘以这个矩阵：
0 1
1 1
所以我们可以通过维护一棵线段树来完成这些，线段树上的每一个节点存储一个 1 x 2 的矩阵 [f(n-1),f(n)] 即可。为了快速计算某个 f(n) 的值，我们可以使用矩阵快速幂。 时间复杂度： O(mlogn + (n+m)logx)
下面有两个AC代码供参考
弱者的代码
AC代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N =
100100;
const int mod =
1e9 +
7;
int n, m, c[N];
LL M[
2][
2] = {{
0ll,
1ll}, {
1ll,
1ll}}, V[
2][
2];
struct node{
LL mat[
2][
2];
LL lz[
2][
2];
bool pu;
}t[N <<
2];
#define lc x << 1
#define rc x << 1 | 1
void rset(LL a0[
2][
2]) { a0[
0][
0] =
1, a0[
1][
1] =
1, a0[
1][
0] =
0, a0[
0][
1] =
0;}
void mat_mul(LL a0[
2][
2], LL b0[
2][
2], LL ret[
2][
2])
{
LL tmp[
2][
2];
memset(tmp,
0,
sizeof(tmp));
for (
int i =
0; i <=
1; i ++)
for (
int j =
0; j <=
1; j ++)
for (
int k =
0; k <=
1; k ++) tmp[i][j] = (tmp[i][j] + a0[i][k] * b0[k][j] % mod) % mod;
for (
int i =
0; i <=
1; i ++)
for (
int j =
0; j <=
1; j ++) ret[i][j] = tmp[i][j];
}
void mat_pow(LL a0[
2][
2],
int k, LL ans[
2][
2])
{
LL tmp[
2][
2];
for (
int i =
0; i <=
1; i ++)
for (
int j =
0; j <=
1; j ++) tmp[i][j] = a0[i][j];
while(k){
if (k &
1) mat_mul(ans, tmp, ans);
mat_mul(tmp, tmp, tmp);
k >>=
1;
}
}
void up(
int x){
t[x].mat[
0][
0] = (t[lc].mat[
0][
0] + t[rc].mat[
0][
0]) % mod;
t[x].mat[
1][
0] = (t[lc].mat[
1][
0] + t[rc].mat[
1][
0]) % mod;
}
void pushdown(
int x)
{
if (!t[x].pu)
return ;
t[lc].pu =
true, t[rc].pu =
true, t[x].pu =
false;
mat_mul(t[x].lz, t[lc].mat, t[lc].mat);
mat_mul(t[x].lz, t[rc].mat, t[rc].mat);
mat_mul(t[x].lz, t[lc].lz, t[lc].lz);
mat_mul(t[x].lz, t[rc].lz, t[rc].lz);
rset(t[x].lz);
}
void build(
int x,
int l,
int r)
{
rset(t[x].lz); rset(t[x].mat); t[x].pu =
false;
if (l == r){
mat_pow(M, c[l] -
1, t[x].mat);
t[x].mat[
0][
0] += t[x].mat[
0][
1], t[x].mat[
0][
0] %= mod;
t[x].mat[
1][
0] += t[x].mat[
1][
1], t[x].mat[
1][
0] %= mod;
return;
}
int mid = (l + r) >>
1;
build(lc, l, mid); build(rc, mid +
1, r); up(x);
}
void modify(
int x,
int l,
int r,
int a,
int b)
{
if (a <= l && r <= b){
t[x].pu =
true;
mat_mul(t[x].lz, V, t[x].lz);
mat_mul(V, t[x].mat, t[x].mat);
return ;
}
pushdown(x);
int mid = (l + r) >>
1;
if (a <= mid) modify(lc, l, mid, a, b);
if (b > mid) modify(rc, mid +
1, r, a, b);
up(x);
}
LL query(
int x,
int l,
int r,
int a,
int b)
{
if (a <= l && r <= b)
return t[x].mat[
0][
0];
pushdown(x);
int mid = (l + r) >>
1;
LL ret =
0;
if (a <= mid) ret = (ret + query(lc, l, mid, a, b)) % mod;
if (b > mid) ret = (ret + query(rc, mid +
1, r, a, b)) % mod;
return ret;
}
int read(){
int x =
0;
char ch = getchar();
while (ch <
'0' || ch >
'9') ch = getchar();
while (ch >=
'0' && ch <=
'9'){ x = x *
10 + ch -
'0'; ch = getchar(); }
return x;
}
int main()
{
n = read(), m = read();
for (
int i =
1; i <= n; i ++) c[i] = read();
build(
1,
1, n);
int ty, l, r, v;
for (
int i =
1; i <= m; i ++){
ty = read();
if (ty ==
1) {
l = read(), r = read(), v = read();
rset(V); mat_pow(M, v, V);
modify(
1,
1, n, l, r);
}
else {
l = read(), r = read();
printf(
"%d\n", query(
1,
1, n, l, r));
}
}
return 0;
}
出题人的标程
#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef
long long ll;
const ll MOD =
1e9 +
7;
const
int MAXN =
1e5 +
10;
struct node {
ll x, y;
}
sum[MAXN <<
2];
struct mat{
ll p[
3][
3], sz;
mat operator + (const mat &x) {
mat tp; tp.sz = sz;
for (
int i =
1; i <= sz; i++)
for (
int j =
1; j <= sz; j++)
tp.p[i][j] = (p[i][j] + x.p[i][j]) % MOD;
return tp;
}
mat operator * (const mat &x) {
mat tp; tp.sz = sz;
for (
int i =
1; i <= sz; i++)
for (
int j =
1; j <= sz; j++) {
tp.p[i][j] =
0;
for (
int k =
1; k <= sz; k++)
tp.p[i][j] = (tp.p[i][j] + p[i][k] * x.p[k][j] % MOD) % MOD;
}
return tp;
}
}unit, Am;
ll a[MAXN];
mat lazy[MAXN <<
2];
mat pow_mod(mat a, ll n) {
mat res = unit;
while (n) {
if (n &
1) res = res * a;
a = a * a;
n >>=
1;
}
return res;
}
void init() {
memset(&unit,
0, sizeof(unit));
memset(&Am,
0, sizeof(Am));
unit.sz = Am.sz =
2;
for (
int i =
1; i <=
2; i++) unit.p[i][i] =
1;
Am.p[
1][
1] = Am.p[
1][
2] = Am.p[
2][
1] =
1;
}
bool Is_unit(mat x) {
if (x.p[
1][
1] || x.p[
2][
2])
return false;
return true;
}
void push_up(
int rt) {
sum[rt].x = (
sum[rt <<
1].x +
sum[rt <<
1 |
1].x) % MOD;
sum[rt].y = (
sum[rt <<
1].y +
sum[rt <<
1 |
1].y) % MOD;
}
void push_down(
int rt) {
ll x, y;
if (!Is_unit(lazy[rt])) {
lazy[rt <<
1] = lazy[rt <<
1] * lazy[rt];
lazy[rt <<
1 |
1] = lazy[rt <<
1 |
1] * lazy[rt];
x = (
sum[rt <<
1].x * lazy[rt].p[
1][
1] % MOD +
sum[rt <<
1].y * lazy[rt].p[
1][
2] % MOD) % MOD;
y = (
sum[rt <<
1].x * lazy[rt].p[
2][
1] % MOD +
sum[rt <<
1].y * lazy[rt].p[
2][
2] % MOD) % MOD;
sum[rt <<
1] = (node){x, y};
x = (
sum[rt <<
1 |
1].x * lazy[rt].p[
1][
1] % MOD +
sum[rt <<
1 |
1].y * lazy[rt].p[
1][
2] % MOD) % MOD;
y = (
sum[rt <<
1 |
1].x * lazy[rt].p[
2][
1] % MOD +
sum[rt <<
1 |
1].y * lazy[rt].p[
2][
2] % MOD) % MOD;
sum[rt <<
1 |
1] = (node){x, y};
lazy[rt] = unit;
}
}
void build(
int l,
int r,
int rt) {
lazy[rt] = unit;
if (l == r) {
if (a[l] ==
1)
sum[rt] = (node) {
1,
0};
else if (a[l] ==
2)
sum[rt] = (node) {
1,
1};
else {
mat tmp = pow_mod(Am, a[l] -
2);
sum[rt].x = (
1 * tmp.p[
1][
1] +
1 * tmp.p[
1][
2]) % MOD;
sum[rt].y = (
1 * tmp.p[
2][
1] +
1 * tmp.p[
2][
2]) % MOD;
}
return;
}
int m = (l + r) >>
1;
build(lson);
build(rson);
push_up(rt);
}
ll query(
int L,
int R,
int l,
int r,
int rt) {
if (L <= l && r <= R)
return sum[rt].x;
push_down(rt);
int m = (l + r) >>
1;
ll res =
0;
if (L <= m) res = (res + query(L, R, lson)) % MOD;
if (R > m) res = (res + query(L, R, rson)) % MOD;
return res;
}
void update(
int L,
int R, mat add,
int l,
int r,
int rt) {
if (L <= l && r <= R) {
lazy[rt] = lazy[rt] * add;
ll x = (
sum[rt].x * add.p[
1][
1] % MOD +
sum[rt].y * add.p[
1][
2] % MOD) % MOD;
ll y = (
sum[rt].x * add.p[
2][
1] % MOD +
sum[rt].y * add.p[
2][
2] % MOD) % MOD;
sum[rt] = (node){x, y};
return;
}
push_down(rt);
int m = (l + r) >>
1;
if (L <= m) update(L, R, add, lson);
if (R > m) update(L, R, add, rson);
push_up(rt);
}
int main() {
init();
int n, m;
scanf(
"%d%d", &n, &m);
for (
int i =
1; i <= n; i++)
scanf(
"%lld", &a[i]);
build(
1, n,
1);
while (m--) {
int op, l, r;
ll x;
scanf(
"%d", &op);
if (op ==
1) {
scanf(
"%d%d%lld", &l, &r, &x);
mat add = pow_mod(Am, x);
update(l, r, add,
1, n,
1);
}
else {
scanf(
"%d%d", &l, &r);
printf(
"%lld\n", query(l, r,
1, n,
1));
}
}
return 0;
}
