Codeforces Round #373 (Div. 2)

　　A题，水题。只要细心一点就能做出来的。

　　B题，最后的排列只可能是rbrbr..或者brbrb..，那么枚举这两种情况，统计当前序列和他们不同的r或者b的个数，假设为x和y，那么较小的他们互换即可，而剩下的只能重刷，因此，答案是min(x,y)+max(x,y)-min(x,y)=max(x,y)。最后两种情况计算出来的答案取最小值即可。

　　C题，其实挺水的，但是也很容易写错。从最右边不断的找能进位的数字让其进位即可。小心点写就能A了。代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;

char s[N];
int n,t;

int main()
{
    scanf("%d%d",&n,&t);
    scanf("%s",s+1);
    s[0] = '0';
    int p,i;
    for(p=1;p<=n&&s[p]!='.';p++) ; // s[p] == '.'
    for(i=p+1;i<=n&&s[i]<'5';i++) ;// s[i] >= '5'
    for(i=i-1;i>p && t > 0;i--)
    {
        if(s[i+1] >= '5')
        {
            s[i+1] = 0;
            s[i]++;
            t--;
        }
    }
    if(s[p+1] >= '5' && t > 0)
    {
        s[p] = 0;
        while(s[--p] == '9') s[p] = '0';
        s[p]++;
    }
    if(s[0] == '0') puts(s+1);
    else puts(s);
    return 0;
}

　　D题，好题。题意不难理解，但是不好做。做法是，线段树的节点维护矩阵，每次成段更新都乘一个矩阵快速幂中那个递推矩阵A的若干次即可。之所以可以这样是因为矩阵乘法在可乘的情况下是满足分配率的，因此节点和加在一起也无妨。值得注意的一点是，在update的时候要把矩阵先做好快速幂再给update当参数，不然只传过去一个改变的量dt等更新具体的节点时再做矩阵的快速幂会超时。代码如下：

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <string.h>
#define t_mid (l+r>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 100000 + 5;

void add(int &a,int b)
{
    a += b;
    if(a < 0) a += mod;
    if(a >= mod) a -= mod;
    //a %= mod;
}

struct matrix
{
    int e[5][5],n,m;
    matrix() {}
    matrix(int _n,int _m): n(_n),m(_m) {memset(e,0,sizeof(e));}
    matrix operator * (const matrix &temp)const
    {
        matrix ret = matrix(n,temp.m);
        for(int i=1;i<=ret.n;i++)
        {
            for(int j=1;j<=ret.m;j++)
            {
                for(int k=1;k<=m;k++)
                {
                    add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod);
                }
            }
        }
        return ret;
    }
    matrix operator + (const matrix &temp)const
    {
        matrix ret = matrix(n,m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod);
            }
        }
        return ret;
    }
    void getE()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                e[i][j] = i==j?1:0;
            }
        }
    }
}A,E;

matrix qpow(matrix temp,int x)
{
    int sz = temp.n;
    matrix base = matrix(sz,sz);
    base.getE();
    while(x)
    {
        if(x & 1) base = base * temp;
        x >>= 1;
        temp = temp * temp;
    }
    return base;
}

void print(matrix p)
{
    int n = p.n;
    int m = p.m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%d ",p.e[i][j]);
        }
        cout << endl;
    }
}

matrix fibo(int x)
{
    matrix ans = matrix(1,2);
    ans.e[1][1] = ans.e[1][2] = 1;
    return ans * qpow(A, x-1);
}

matrix c[N<<2],lazy[N<<2];
int flag[N<<2];

int n,m;
void up(int o) {c[o] = c[ls] + c[rs];}
void down(int o,int l,int r)
{
    if(l == r) return ;
    if(flag[o])
    {
        lazy[ls] = lazy[ls] * lazy[o];
        lazy[rs] = lazy[rs] * lazy[o];
        c[ls] = c[ls] * lazy[o];
        c[rs] = c[rs] * lazy[o];
        flag[ls] = flag[rs] = 1;
        flag[o] = 0; lazy[o].getE();
    }
}
void build(int o,int l,int r)
{
    lazy[o] = E;
    flag[o] = 0;
    if(l == r)
    {
        int t;
        scanf("%d",&t);
        c[o] = fibo(t);
        return ;
    }
    build(lson);
    build(rson);
    up(o);
}
void update(int o,int l,int r,int ql,int qr,matrix now_mat)
{
    if(l == ql && r == qr)
    {
        c[o] = c[o] * now_mat;
        lazy[o] = lazy[o] * now_mat;
        flag[o] = 1;
        return ;
    }
    down(o,l,r);
    if(qr <= t_mid) update(lson,ql,qr,now_mat);
    else if(ql > t_mid) update(rson,ql,qr,now_mat);
    else
    {
        update(lson,ql,t_mid,now_mat);
        update(rson,t_mid+1,qr,now_mat);
    }
    up(o);
}
ll query(int o,int l,int r,int ql,int qr)
{
    if(l == ql && r == qr)
    {
        return c[o].e[1][1];
    }
    down(o,l,r);
    ll ans = 0;
    if(qr <= t_mid)
    {
        ans += query(lson,ql,qr);
        ans = (ans % mod + mod) % mod;
    }
    else if(ql > t_mid)
    {
        ans += query(rson,ql,qr);
        ans = (ans % mod + mod) % mod;
    }
    else
    {
        ans = query(lson,ql,t_mid) + query(rson,t_mid+1,qr);
        ans = (ans % mod + mod) % mod;
    }
    return ans;
}

int main()
{
    A = matrix(2,2); A.e[1][2] = A.e[2][1] = A.e[2][2] = 1;
    E = matrix(2,2); E.getE();
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int op;
        scanf("%d",&op);
        if(op == 1)
        {
            int ql,qr,dt;
            scanf("%d%d%d",&ql,&qr,&dt);
            update(1,1,n,ql,qr,qpow(A,dt));
        }
        else
        {
            int ql,qr;
            scanf("%d%d",&ql,&qr);
            printf("%I64d
",query(1,1,n,ql,qr));
        }
    }
    return 0;
}