2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6155 Subsequence Count 矩阵快速幂

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6155

题意:

题解来自:http://www.cnblogs.com/iRedBean/p/7398272.html

先考虑dp求01串的不同子序列的个数。

dp[i][j]表示用前i个字符组成的以j为结尾的01串个数。

如果第i个字符为0,则dp[i][0] = dp[i-1][1] + dp[i-1][0] + 1,dp[i][1] = dp[i-1][1]

如果第i个字符为1,则dp[i][1] = dp[i-1][1] + dp[i-1][0] + 1,dp[i][0] = dp[i-1][0]

显然这是线性递推,我们考虑如何用矩阵表示这种递推关系。

下面分别对应加入一个字符0或1时表示递推关系的矩阵。

然后用线段树维护每个区间的矩阵乘积就可以解决查询操作了。

对于修改操作,我们给区间维护一个flip标记,表示该区间是否要翻转,用线段树区间更新的方法去更新flip标记就好了。

将一个区间翻转后,它对应矩阵也要发生改变,这里我们只要将矩阵的第一列与第二列交换后再将第一行与第二行交换就好了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
const int mod = 1e9+7;
typedef long long LL;
struct Matrix{
    LL maze[3][3];
    friend Matrix operator*(const Matrix& a, const Matrix& b){
        Matrix c;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                c.maze[i][j]=0;
                for(int k=0; k<3; k++){
                    c.maze[i][j]+=a.maze[i][k]*b.maze[k][j];
                    c.maze[i][j]%=mod;
                }
            }
        }
        return c;
    }
};
const Matrix m[2]={{1,0,0,1,1,0,1,0,1},{1,1,0,0,1,0,0,1,1}};
Matrix T[maxn<<2];
bool flip[maxn<<2];
char s[maxn];
void build(int l, int r, int rt){
    flip[rt] = 0;
    if(l == r){
        T[rt] = m[s[l]-‘0‘];
        return;
    }
    int mid = (l+r)>>1;
    build(l, mid, rt*2);
    build(mid+1, r, rt*2+1);
    T[rt] = T[rt*2]*T[rt*2+1];
}
void Flip(Matrix &mat){
    swap(mat.maze[0][0],mat.maze[0][1]);
    swap(mat.maze[1][0],mat.maze[1][1]);
    swap(mat.maze[2][0],mat.maze[2][1]);
    swap(mat.maze[0][0],mat.maze[1][0]);
    swap(mat.maze[0][1],mat.maze[1][1]);
    swap(mat.maze[0][2],mat.maze[1][2]);
}
void pushdown(int rt){
    if(flip[rt]){
        flip[rt*2]^=flip[rt];
        flip[rt*2+1]^=flip[rt];
        Flip(T[rt*2]);
        Flip(T[rt*2+1]);
        flip[rt]=false;
    }
}
void update(int L, int R, int l, int r, int rt){
    if(L<=l&&r<=R){
        flip[rt]^=1;
        Flip(T[rt]);
        return;
    }
    pushdown(rt);
    int mid=(l+r)/2;
    if(R<=mid) update(L,R,l,mid,rt*2);
    else if(L>mid) update(L,R,mid+1,r,rt*2+1);
    else{
        update(L,mid,l,mid,rt*2);
        update(mid+1,R,mid+1,r,rt*2+1);
    }
    T[rt]=T[rt*2]*T[rt*2+1];
}
Matrix query(int L, int R, int l, int r, int rt){
    if(L<=l&&r<=R){
        return T[rt];
    }
    pushdown(rt);
    int mid=(l+r)/2;
    if(R<=mid) return query(L,R,l,mid,rt*2);
    else if(L>mid) return query(L,R,mid+1,r,rt*2+1);
    else return query(L,mid,l,mid,rt*2)*query(mid+1,R,mid+1,r,rt*2+1);
}
int main()
{
    int T,n,q;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        build(1,n,1);
        while(q--)
        {
            int op,l,r;
            scanf("%d%d%d",&op,&l,&r);
            if(op==1) update(l,r,1,n,1);
            else{
                Matrix ret = query(l,r,1,n,1);
                printf("%lld\n", (ret.maze[2][0]+ret.maze[2][1])%mod);
            }
        }
    }
    return 0;
}
时间: 08-18

2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6155 Subsequence Count 矩阵快速幂的相关文章

2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6154 CaoHaha&#39;s staff 思维

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6154 题意:在笛卡尔坐标系下,画一个面积至少为  n 的简单多边形,每次只能画一条边或者一个格子的对角线,问至少要画几条. 解法:如果一个斜着的矩形长宽分别是 a,b,那么它的面积是 2ab.最优解肯定是离 sqrt(n/2)很近的位置.想想 n=5 时答案为什么是7 然后在那个小范围内枚举一下就好了.我给一张做题时画的图 #include <bits/stdc++.h> using namesp

2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6153 A Secret KMP,思维

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6153 题意:给了串s和t,要求每个t的后缀在在s中的出现次数,然后每个次数乘上对应长度求和. 解法:关键在于想到把s和t都翻转之后,把t求next,然后用t去匹配s,在匹配过程中把fail指针跳到的地方加1,但是还没完,最后需要反向遍历第二个串将大串对小串的贡献加上去就可以了. 这道题是很多现场AC的代码是有漏洞的,比如bazbaba,bazbaba这个答案是34,但是很多现场AC的代码会输出31.

2016中国大学生程序设计竞赛 - 网络选拔赛

solved 4/11 2016中国大学生程序设计竞赛 - 网络选拔赛

HDU 5961 传递 【图论+拓扑】 (2016年中国大学生程序设计竞赛(合肥))

传递 Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)   Problem Description 我们称一个有向图G是传递的,当且仅当对任意三个不同的顶点a,,若G中有 一条边从a到b且有一条边从b到c ,则G中同样有一条边从a到c.我们称图G是一个竞赛图,当且仅当它是一个有向图且它的基图是完全图.换句 话说,将完全图每条边定向将得到一个竞赛图.下图展示的是一个有4个顶点的竞

HDU 5969 最大的位或 【贪心】 (2016年中国大学生程序设计竞赛(合肥))

最大的位或 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description B君和G君聊天的时候想到了如下的问题.给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大.其中|表示按位或,即C. C++. Java中的|运算. Input 包含至多10001组测试数据.第一行有一个正整数,表示数据的组数.接下

HDU 5965 扫雷 【模拟】 (2016年中国大学生程序设计竞赛(合肥))

扫雷 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 998    Accepted Submission(s): 289 Problem Description 扫雷游戏是晨晨和小璐特别喜欢的智力游戏,她俩最近沉迷其中无法自拔.该游戏的界面是一个矩阵,矩阵中有些格子中有一个地雷,其余格子中没有地雷. 游戏中,格子可能处于己知和未知的状态

HDU 5963 朋友 【博弈论】 (2016年中国大学生程序设计竞赛(合肥))

朋友 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description B君在围观一群男生和一群女生玩游戏,具体来说游戏是这样的:给出一棵n个节点的树,这棵树的每条边有一个权值,这个权值只可能是0或1. 在一局游戏开始时,会确定一个节点作为根.接下来从女生开始,双方轮流进行 操作.当一方操作时,他们需要先选择一个不为根的点,满足该点到其父亲的边权为1; 然

HDU 5968 异或密码 【模拟】 2016年中国大学生程序设计竞赛(合肥)

异或密码 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem Description 晨晨在纸上写了一个长度为N的非负整数序列{ai}.对于这个序列的一个连续子序列{al,al+1,-,ar}晨晨可以求出其中所有数异或的结果 alxoral+1xor...xorar其 中xor表示位异或运算,对应C.C++. Java等语言中的^运算.小璐提出了M个询问,每个询问用

HDU 5943 Kingdom of Obsession 【二分图匹配 匈牙利算法】 (2016年中国大学生程序设计竞赛(杭州))

Kingdom of Obsession Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 49    Accepted Submission(s): 14 Problem Description There is a kindom of obsession, so people in this kingdom do things very