QOJ 6504. CCPC Final 2022 D Flower's Land 2题解

这篇具有很好参考价值的文章主要介绍了QOJ 6504. CCPC Final 2022 D Flower's Land 2题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

QOJ 6504. CCPC Final 2022 D Flower's Land 2题解

题意简述

给你一个只含 \(0,1,2\) 的序列,相邻两个相同的数字可以直接消掉。

询问包含两种

  • 区间所有数 \(+1\) 并对 \(3\) 取模。

  • 求一段区间能否用上述消除方式消完。

    样例输入

    8 9
    01211012
    2 4 5
    2 3 6
    1 6 8
    1 6 8
    2 3 6
    2 1 8
    1 1 1
    1 7 7
    2 1 8
    

    样例输出 #1

    Yes
    No
    Yes
    No
    Yes
    

提示

在我们做相邻两个能被消掉,判断一段区间能否被消掉时,常常用矩阵来考虑。

把每一种颜色用一种矩阵来表示,若当前位是偶数就设为这个矩阵,若当前位是奇数就设为这个矩阵的逆。

求解就把所有的矩阵乘起来,看最后结果矩阵是不是 \(I\)

为什么矩阵是正确的呢?因为矩阵满足结合律但不满足交换律。

这样就可以保证 \(1,2,3,1,2,3\) 会判断为错。

如果还没理解,下面再解释详细一点:

这是一段序列 \(0122221000\) 显然他是合法的。

在矩阵中,因为满足结合律,你先算中间那段 \(2222\) ,因为奇数和偶数个数相同,一定为 \(I\) ,相当于没有了,变成了 \(0110000\) 。一直向下就可以得到 \(I\)

题解

我们用线段树来维护矩阵乘法,这很容易,具体就是加了以后如何在矩阵中体现出来。

因为只有 \(0,1,2\) ,我们把当前,\(+1\) 后, \(+2\) 后的矩阵都记录下来。这样就可以了。文章来源地址https://www.toymoban.com/news/detail-556138.html

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
int n,q;
char x;
int a[N], opt, l, r;
inline ll mpow(ll x,int k){
	ll ans = 1;
	while(k){
		if(k & 1) ans = ans * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ans;
}
struct Mar{
	ll a[3][3];
	inline Mar operator *(const Mar b)const{
		Mar c;
		for(int i = 1; i <= 2; ++i){
			for(int j = 1; j <= 2; ++j){
				c.a[i][j] = 0;
				for(int k = 1;k <= 2; ++k){
					c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
				}	
			}
		}
		return c;
	}
	inline bool check(){
		if(a[1][1] != 1) return 0;
		if(a[1][2] != 0) return 0;
		if(a[2][1] != 0) return 0;
		if(a[2][2] != 1) return 0;
		return 1;
	}
	inline Mar inv()const{
		Mar c, b; 
		c.a[1][1] = 1;
		c.a[1][2] = 0;
		c.a[2][1] = 0;
		c.a[2][2] = 1;
		for(int i = 1; i <= 2; ++i)for(int j = 1; j <= 2; ++j) b.a[i][j] = a[i][j];
		for(int i = 1; i <= 2; ++i){
			for(int j = 1; j <= 2; ++j){
				if(i == j) continue;
				ll w = b.a[j][i] * mpow(b.a[i][i],mod - 2) % mod;
				for(int k = 1; k <= 2; ++k){
					b.a[j][k] = (b.a[j][k] - b.a[i][k] * w % mod + mod) % mod;
				}
				for(int k = 1; k <= 2; ++k){
					c.a[j][k] = (c.a[j][k] - c.a[i][k] * w % mod + mod) % mod;
				}
			}
		}
		for(int i = 1; i <= 2; ++i){
			for(int j = 1; j <= 2; ++j){
				c.a[i][j] = c.a[i][j] * mpow(b.a[i][i],mod - 2) % mod;
			}
		}
		return c;
	}
	inline void print(){
		for(int i = 1; i <= 2; ++i){
			for(int j = 1; j <= 2; ++j){
				cout<<a[i][j]<<' ';
			}
			cout<<'\n';
		}
	}
}I;
struct node{
	Mar now,nxt,nnt;
	int tag;
}tr[N << 2];
Mar m[3], m_[3];
inline void pre(){
	I.a[1][1] = 1,
	I.a[1][2] = 0;
	I.a[2][1] = 0;
	I.a[2][2] = 1;

	m[0].a[1][1] = 2,m[0].a[1][2] = 3;
	m[0].a[2][1] = 5,m[0].a[2][2] = 7;

	m[1].a[1][1] = 11,m[1].a[1][2] = 13;
	m[1].a[2][1] = 17,m[1].a[2][2] = 19;

	m[2].a[1][1] = 23,m[2].a[1][2] = 29;
	m[2].a[2][1] = 31,m[2].a[2][2] = 37;

	m_[0] = m[0].inv();
	m_[1] = m[1].inv();
	m_[2] = m[2].inv();
}
inline void input(){
	cin>> n >> q;
	for(int i = 1; i <= n; ++i){
		cin>>x;
		a[i] = x - '0';
	}
}
inline void pd(int x){
	cout<<"now:"<<'\n';
	tr[x].now.print();
	cout<<"nxt:"<<'\n';
	tr[x].nxt.print();
	cout<<"nnt:"<<'\n';
	tr[x].nnt.print();
	cout<<"tag:"<<'\n'<<tr[x].tag<<'\n';
} 
inline void downdate(int x){
	tr[x << 1].tag = (tr[x << 1].tag + tr[x].tag) % 3;
	tr[x << 1 | 1].tag = (tr[x << 1 | 1].tag + tr[x].tag) % 3;
	while(tr[x].tag > 0){
		swap(tr[x << 1].now, tr[x << 1].nxt);
		swap(tr[x << 1].nnt, tr[x << 1].nxt);
		swap(tr[x << 1 | 1].now, tr[x << 1 | 1].nxt);
		swap(tr[x << 1 | 1].nnt, tr[x << 1 | 1].nxt);
		--tr[x].tag;
	}
}
inline void pushup(int x){
	tr[x].now = tr[x << 1].now * tr[x << 1 | 1].now;
	tr[x].nxt = tr[x << 1].nxt * tr[x << 1 | 1].nxt;
	tr[x].nnt = tr[x << 1].nnt * tr[x << 1 | 1].nnt;
}
inline void build(int x, int l, int r){
	if(l == r){
		if(l % 2){
			tr[x].now = m_[a[l]];
			tr[x].nxt = m_[(a[l] + 1) % 3];
			tr[x].nnt = m_[(a[l] + 2) % 3];
		}else{ 
			tr[x].now = m[a[l]];
			tr[x].nxt = m[(a[l] + 1) % 3];
			tr[x].nnt = m[(a[l] + 2) % 3];
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	pushup(x);
}
inline void adtr(int x){
	tr[x].tag = (tr[x].tag + 1) % 3;
	swap(tr[x].now, tr[x].nxt);
	swap(tr[x].nnt, tr[x].nxt);
}
inline void add(int x, int l, int r, int L, int R){
	if(L <= l && r <= R){
		adtr(x);
		return ;
	}
	downdate(x);
	int mid = (l + r) >> 1;
	if(L <= mid) add(x << 1, l, mid, L, R);
	if(R > mid) add(x << 1 | 1, mid + 1, r, L, R);
	pushup(x);
}
inline Mar query(int x, int l, int r, int L, int R){
	if(L <= l && r <= R){
		// cout<<x<<'\n';
		// tr[x].now.print();
		return tr[x].now;
	}
	downdate(x);
	int mid = (l + r) >> 1;
	Mar ans = I;
	if(L <= mid) ans = ans * query(x << 1, l, mid, L, R);
	if(R > mid) ans = ans * query(x << 1 | 1,mid + 1, r, L, R);
	return ans; 
}
inline void op(){
	build(1,1,n);
	for(int i = 1; i <= q; ++i){
		cin>> opt >> l >> r;
		if(opt == 1){
			add(1, 1, n, l, r);
		}else if(opt == 2){
			if(query(1, 1, n, l, r).check()){
				cout<<"Yes"<<'\n';
			}else{
				cout<<"No"<<'\n';
			}
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	pre();
	input();
	op();
	return 0;
}

到了这里,关于QOJ 6504. CCPC Final 2022 D Flower's Land 2题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 题解动态规划:蓝桥杯2022国赛B组 题解 A题目

    在这组题(蓝桥杯C/C++ B组 国赛)里面挑了几道喜欢的题目,做了一下,笔记思路如下。( 其实是我觉得能做出的题 ) 题目图片来源于:CSDN 罚时大师月色 请问2022,拆分成10个不同的正整数有多少种不同的分法。 这道题目,拿到手上的时候,第一个想法是暴力,但是,每次

    2023年04月08日
    浏览(95)
  • 2022CSP-J2题解

    今天(2022,10,29), C S P − J S CSP-JS C S P − J S 第二轮成功举办, 虽然大部分省市疫情取消 本蒟蒻今天有幸参加CSP,特发入门组题解 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a a a 和 b b b ,求 a b a^b a b 的值是多少。 a b a^b a b 即 b b b 个 a a a 相乘

    2023年04月08日
    浏览(84)
  • 2022 CSP-J 复赛题解

    【题目描述】 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a 和 b ,求 a b 的值是多少。 a b 即 b 个 a 相乘的值,例如 23 即为 3 个 2 相乘,结果为 2 × 2 × 2 = 8。 “简单!”小文心想,同时很快就写出了一份程序,可是测试时却出现了错误。 小文

    2024年02月07日
    浏览(63)
  • 2022CSP-J 题解[完整版]

    “西西弗”的脑子是被宇宙射线影响了吗,造的题目我都写到睡着了…… 题目描述 小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数 a a a 和 b b b ,求 a b a^b a b 的值是多少。 a b a^b a b 即 b b b 个 a a a 相乘的值,例如 2 3 2^3 2 3 即为 3 3 3 个 2 2 2 相乘,

    2024年02月10日
    浏览(70)
  • NewStarCTF 2022 web方向题解 wp

    先看题目,要传参加绕过。 分析一下代码:首先get一个data= data://test/plain, Wel…。然后key1和2用数组可以绕过。num=2077a可以绕过弱类型。eval()中的php语句被 # 注释了,我们需要通过换行 %0a 来忽视这个注释,所以再构造cmd=%0asystem(‘ls /’); 看看题干,伪随机数工具。 分析一下代

    2024年02月11日
    浏览(36)
  • 2022icpc西安站部分题解-E

    E. Find Maximum 题意:给定边界L和R,算满足的所有的的最大值, 其中满足: 。 题解: 打表发现发现了f(x)与x的三进制有关系,即f(x)等于x三进制的每个数相加,再加上三进制数的有效位数。下图从左向右依次是x,x的三进制,f(x)。 于是便是将问题转变为在区间中找到三进制的每

    2024年02月08日
    浏览(37)
  • 2022数学建模“五一杯”B题 题解+论文

    摘要 本文主要研究温度等因素对矿石加工质量控制问题。提高矿石加工质量,对节约不可再生资源和能源,推动节能减排,助力“双碳”’目标的实现,具有重要的意义。 针对问题一,我们要实现在给定系统温度和原矿参数的情况下,预测可能性最大的产品的指标。由于在

    2024年02月02日
    浏览(63)
  • 洛谷2022SCP第一轮J组模拟题(LGR-2022-J1)部分题解

    LGR-2022-J1 T3. 小恺编写了如下函数,希望计算斐波那契数列 f(n) 第 n 项对 10000 取余数的值:

    2024年02月09日
    浏览(36)
  • 【简单算法】2022SCUACM集训队冬季选拔全题解

    没想到现在冬季选拔都这么难了…… 题目传送门 本文juejin:https://juejin.cn/post/7222531019319722039/ 本文CSDN:https://blog.csdn.net/hans774882968/article/details/130184851 作者:hans774882968以及hans774882968以及hans774882968 参考:https://www.cnblogs.com/ycx-akioi/p/AtCoder-abc165.html 最长严格上升子序列树上版本

    2023年04月16日
    浏览(35)
  • 2022蓝桥杯C++B组国赛真题题解

    目录 A:2022 B:钟表 C:卡牌 D:最大数字 E:出差 F:费用报销 G:故障 H:机房 I:齿轮 J:搬砖 问题描述 将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法? 注意交换顺序视为同一种方法, 例如 2022=1000+1022 和 1022+1000 就视为同一种方法。 答案提交 这是一道结果填空的

    2024年02月06日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包