首页 > 其他分享 >QOJ 6504. CCPC Final 2022 D Flower's Land 2题解

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

时间：2023-07-13 22:22:10浏览次数：45  
标签：Flower int 题解 ll 矩阵 CCPC Mar ans

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\) 后的矩阵都记录下来。这样就可以了。

代码

#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;
}

标签：Flower,int,题解,ll,矩阵,CCPC,Mar,ans
From： https://www.cnblogs.com/hfjh/p/17552363.html

相关文章

  • yarn : 无法加载文件 E:\nodejs\yarn.ps1，因为在此系统上禁止运行脚本。问题解决
    1.在电脑的开始菜单中，搜索PowerShell ,然后以管理员身份运行，如下所示：2.以管理员身份运行后，会出现命令窗口，接下来，输入命令get-ExecutionPolicy 查看权限,会看到它的返回值是 Restricted ,意思是当前是禁用的。3.执行命令：set-ExecutionPolicyRemoteSigned，没有报错就......
  • CF1846D Rudolph and Christmas Tree 题解
    Decription一颗圣诞树由\(n\)个底边为\(d\)，高度为\(h\)的等腰三角形组成，每个三角形以\(y\)轴为对称轴，底边均平行于\(x\)轴，三角形有可能重叠。给出\(n,d,h\)以及每个三角形底边与\(x\)轴的距离,求该圣诞树的面积。Solution如图，这是一棵圣诞树,其由两部分组成，完整......
  • NOI2021 题解
    [NOI2021]轻重边转化一下题意：每次给一条链染色，查一条链从\(x\)到\(y\)有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以LCT，码量可能要小点。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>usingnamespace......
  • 题解 最大加权矩阵
    题目链接虽然是一道橙题，但还是蕴含了重要算法思想——降维思想。如果是一维形式，即最大子段和，我们采取先求前缀和，并固定右端点，减去左边最小的办法求。对于这题，若固定了上下边界，则可以利用列的前缀和将其“压缩”为一维形式，再采取“最大子段和”的方式求解。如下面一个二维矩阵：......
  • 题解 醋溜便当
    题目链接题目让我们找出每个点是否存在长度\(\in[x,k\timesx]\)的回路，若找到一长度为\(a(0<a\lex)\)的回路，那么必然存在\(pa\in[x,k\timesx](p\in\Z)\)，若找到长度\(\in[x,k\timesx]\)的回路，直接符合条件。所以问题转化为求是否存在\(\in[1,k\timesx]\)的回路，只需......
  • 【题解】CF gym 104337 G. Guess the Polynomial
    statement：https://codeforces.com/gym/104337/problem/G。即求\(f(x)=\sum\limits_{i=0}^{p-2}a_ix^i\)，其中只有不超过\(n\)个\(a_i\)非\(0\)。记：\[\begin{aligned}A_{n}^{k}&=\sum_{i\equivk\pmod{n}}a_i=\frac{1}{n}\sum_{i=0}^{n-1}f(\omega_{n}^{......
  • CF1450C2 题解
    题目传送门再不写题解社贡要掉到\(0\)了。题目分析显然如果\(3\)个格子构成了满足获胜条件的情况，这\(3\)个格子模\(3\)的余数各不相同。那么我们将格子按模\(3\)的余数分为\(3\)类，只要保证相邻\(3\)个格子中有\(2\)个不同就行了，不需要动第\(3\)个。我们令......
  • Facetook Priority Wall 题解
    题目传送门一道模拟题。用一个map存储每个人的优先级因子，然后存进vector里进行排序。难点在于分辨\(X\)和\(Y\)与当前是什么操作。不过需要注意，只要出现了名字就需要输出，且我们认为与你没关系的人不加分。Code#include<bits/stdc++.h>#definelllonglong#define......
  • centos7ping不通主机却能够上网时的问题解决方案
       ......
  • Codeforeces #1844 A~D题解
    Codeforeces#1844A~D题解ASubtractionGame博弈论A+Bproblem由于只有两种数字可选，若石子数量为a+b，先手选完之后必然为a或b，因此后手可以直接选完BPermutations&Primes构造构造方法：35791108642，这样把1放中间可以让最多的区间拿到1，接下来避免同时拿......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99