洛谷T21776 子序列
题目描述
你有一个长度为 nn 的数列 \{a_n\}{an} ,这个数列由 0,10,1 组成,进行 mm 个的操作:
1~l~r1 l r :把数列区间 [l, r][l,r] 内的所有数取反。即 00 变成 11 ,11 变成 00 。
2~l~r2 l r :询问数列在区间 [l, r][l,r] 内共有多少个本质不同的子序列。
输入输出格式
输入格式:
第一行包含两个整数 n, mn,m ,意义如上所述。
接下来一行包含 nn 个数,表示数列 \{a_n\}{an} 。
接下来 mm 行,每行包含三个数,表示一个操作,操作格式如上所述。
输出格式:
对于每个询问,输出答案模 10^9 + 7109+7 的结果。
输入输出样例
说明
对于 10 \%10% 的数据,1 \leq n, m \leq 10^21≤n,m≤102 。
对于 30 \%30% 的数据,1 \leq n, m \leq 10^31≤n,m≤103 。
对于 100 \%100% 的数据,1 \leq n, m \leq 10^51≤n,m≤105 。
这道题同HDU6155(只不过我在HDU上T飞了)
首先我们考虑一下暴力怎么写
dp[i][1]表示到第$i$个位置,以$1$结尾,本质不同的子序列
dp[i][0]表示到第$i$个位置,以$0$结尾,本质不同的子序列
转移的时候,假设第$i$个字符是1
那么对它有贡献的是以前以$0$结尾的子序列,以及以前以$1$结尾的子序列,以及空串
那么此时
$dp[i][1]=dp[i-1][0]+dp[i-1][1]+1$
$dp[i][0]=dp[i-1][0]$
当第$i$个字符是$0$的时候同理,不难得到
$dp[i][1]=dp[i-1][1]$
$dp[i][0]=dp[i-1][0]+dp[i-1][1]+1$
大家有没有发现一件事情?
这个dp的转移是递推!也就是说我们可以用矩阵乘法来加速!
而矩阵乘法可以用线段树来维护!
它的矩阵为
对于操作1的话,先交换要改变的矩阵的第一行和第二行,再交换要改变的矩阵的第一列和第二列
至于为什么?这个可以转移之间的关系入手,也可以直接找规律
这样就实现了两个矩阵的转换
另外还有一点、
对于结果矩阵,我们只会用到[3][1]和[3][2]这两项(分别代表dp[n][1],dp[n][0])
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long int
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int MAXN=1e6+;
const int mod=1e9+;
inline int read()
{
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
char c[MAXN];
struct Matrix
{
LL mat[][];
Matrix(){memset(mat,,sizeof(mat));}
};
struct node
{
int l,r,w;
bool f;
Matrix m;
}T[MAXN];
Matrix zero,one,HHHHH;
Matrix rev(Matrix &a)
{
for(LL i=;i<=;i++) swap(a.mat[][i],a.mat[][i]);
for(LL i=;i<=;i++) swap(a.mat[i][],a.mat[i][]);
}
Matrix MatrixMul(Matrix a,Matrix b)
{
Matrix c;
for(LL k=;k<=;k++)
for(LL i=;i<=;i++)
for(LL j=;j<=;j++)
c.mat[i][j]=(c.mat[i][j]+(a.mat[i][k]*b.mat[k][j])%mod )%mod;
return c;
}
void update(int k)
{
T[k].m=MatrixMul(T[ls].m,T[rs].m);
}
void pushdown(int k)
{
if(T[k].f)
{
T[ls].f^=;T[rs].f^=;
rev(T[ls].m);rev(T[rs].m);
T[k].f=;
}
}
void Build(int k,int ll,int rr)
{
T[k].l=ll;T[k].r=rr;T[k].f=;
if(ll==rr)
{
if(c[ll]=='') T[k].m=zero;
else T[k].m=one;
return ;
}
int mid=ll+rr>>;
Build(ls,ll,mid);
Build(rs,mid+,rr);
update(k);
}
void IntervalChange(int k,int ll,int rr)
{
if(ll<=T[k].l&&T[k].r<=rr)
{
T[k].f^=;
rev(T[k].m);
return ;
}
pushdown(k);
int mid=T[k].l+T[k].r>>;
if(ll<=mid) IntervalChange(ls,ll,rr);
if(rr>mid) IntervalChange(rs,ll,rr);
update(k);
}
Matrix IntervalAsk(int k,int ll,int rr)
{
Matrix ans=HHHHH;
if(ll<=T[k].l&&T[k].r<=rr)
{
ans=T[k].m;
return ans;
}
pushdown(k);
LL mid=T[k].l+T[k].r>>;
if(ll<=mid)
ans=MatrixMul(IntervalAsk(ls,ll,rr),ans);
if(rr>mid)
ans=MatrixMul(ans,IntervalAsk(rs,ll,rr));
return ans;
}
int main()
{
int N,M;
zero.mat[][]=zero.mat[][]=zero.mat[][]=zero.mat[][]=zero.mat[][]=;
one.mat[][]=one.mat[][]=one.mat[][]=one.mat[][]=one.mat[][]=;
HHHHH.mat[][]=HHHHH.mat[][]=HHHHH.mat[][]=;
int T;
T=;
while(T--)
{
N=read();M=read();
scanf("%s",c+);
Build(,,N);
while(M--)
{
int opt=read(),l=read(),r=read();
if(opt==)
{
IntervalChange(,l,r);
}
else if(opt==)
{
Matrix ans=IntervalAsk(,l,r);
printf("%lld\n", (ans.mat[][]+ans.mat[][])%mod );
}
}
}
return ;
}
最新文章
- Java多线程9:ThreadLocal源码剖析
- servler--请求重定向
- 堆排序算法(C#实现)
- 核心游记之 page_address_init
- 在汉澳sinox2014建立ZFS高可靠文件存储系统
- apache 配置
- Python之多线程多进程
- IIS7二级域名添加同一证书
- 【mysql】mysql存储引擎
- python3读取MySQL-Front的MYSQL密码
- Redis内存分析工具redis-rdb-tools
- 【杂谈】Tomcat 之 Lifecycle接口
- Win10上安装Keras 和 TensorFlow(GPU版本)
- Azure HDInsight 上的 Spark 群集配合自定义的Python来分析网站日志
- Spring boot(六)优雅使用mybatis
- Apache tica详述
- JavaScript创建对象的方法汇总
- Go面试题精编100题
- The .NET weak event pattern in C#
- [Web 前端] CSS篇之 4. position 和 display 的取值和各自的意思和用法
热门文章
- pandas 6 合并数据 concat, append 垂直合并,数据会变高/长
- redhat下搭建jdk+tomcat环境
- java 实现顺序结构线性列表
- 埃及分数 迭代加深搜索 IDA*
- 在KVM中执行windows 10虚机(by quqi99)
- Zepto源代码分析之二~三个API
- Constructor call must be the first statement in a constructor
- java学习记录笔记--继承,super,Object类
- 登录那些事儿+ Session原理
- NOIP2017 小凯的疑惑 解题报告(赛瓦维斯特定理)