首页 > 其他分享 >P7739 [NOI2021] 密码箱

P7739 [NOI2021] 密码箱

时间：2024-04-18 22:12:44浏览次数：25  
标签：begin P7739 end 密码箱 long NOI2021 1ll bmatrix mod

题意：

Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中，他发掘出了一个远古时期的密码箱。经过周密而严谨的考证，Yelekastee 得知密码箱的密码和某一个数列 \(\{ a_n \}\) 相关。数列 \(\{ a_n \}\) 可以用如下方式构造出来：

  1. 初始时数列长度为 \(2\) 且有 \(a_0 = 0, a_1 = 1\)；
  2. 对数列依次进行若干次操作，其中每次操作是以下两种类型之一：
  • W 类型：给数列的最后一项加 \(1\)。
  • E 类型：若数列的最后一项为 \(1\)，则给倒数第二项加 \(1\)；否则先给数列的最后一项减 \(1\)，接着在数列尾再加两项，两项的值都是 \(1\)。

受到技术限制，密码箱并没有办法完整检查整个数列，因此密码箱的密码设定为数列 \(\{ a_n \}\) 经过函数 \(f\) 作用后的值，其中 \(f\) 的定义如下：

\[f(a_0, \ldots , a_{k - 1}, a_k) = \begin{cases} a_0, & k = 0 \\ f \! \left( a_0, a_1, \ldots , a_{k - 2}, a_{k - 1} + \frac{1}{a_k} \right) \! , & k \ge 1 \end{cases} \]

Yelekastee 并不擅长运算，因此他找到了你，希望你能根据他提供的操作序列计算出密码箱的密码。不幸的是，他的记性并不是很好，因此他会随时对提供的操作序列做出一些修改，这些修改包括以下三种：

  • APPEND c，在现有操作序列后追加一次 c 类型操作，其中 c 为字符 W 或 E。
  • FLIP l r，反转现有操作序列中第 \(l\) 个至第 \(r\) 个（下标从 \(1\) 开始，修改包含端点 \(l\) 和 \(r\)，下同）操作，即所有 W 变为 E，所有 E 变为 W。
  • REVERSE l r，翻转现有操作序列中第 \(l\) 个至第 \(r\) 个操作，也就是将这个区间中的操作逆序。

分析：

发现 \(f\) 的倒数形如：

\[\frac{1}{a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\dots}}} \]

考虑从右往左加入 \(a_{i}\)，将 \(\frac{a}{b} \rightarrow \frac{A}{B}\)：

\[\frac{A}{B}=\frac{1}{a_{i}+\frac{a}{b}} \]

可以发现 \(A=b,\ B=a_{i} \times b+a\)。

似乎可以使用矩阵乘法。

\[\begin{bmatrix} A \\ B \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & a_{i} \end{bmatrix} \times \begin{bmatrix} a \\ b \end{bmatrix} \]

最后答案即为：

\[\begin{bmatrix} 0 & 1 \\ 1 & a_{0} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & a_{1} \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\ 1 & a_{2} \end{bmatrix} \times \dots \times \begin{bmatrix} 0 & 1 \\ 1 & a_{3} \end{bmatrix} \times \begin{bmatrix} 0 \\ 1 \end{bmatrix} \]

不难构造出，\(W\) 操作就是在后面乘上 \(\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\)，\(E\) 操作就是在后面乘上 \(\begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix}\)。

由于有翻转操作和取反操作，因此可以使用 FHQ-Treap 来维护。

具体地，平衡树每个节点维护以下信息：

  • 该节点的类型（是 \(W\) 还是 \(E\)）。

  • 子树内的矩阵连乘积。

  • 子树内的翻转矩阵连乘积。

  • 子树内的取反矩阵连乘积。

  • 子树内的翻转取反矩阵连乘积。

  • 子树内的翻转标记。

  • 子树内的取反标记。

标记的合并只需要异或 \(1\) 即可。时间复杂度 \(O(n \log n)\)。常数巨大，轻度卡常。

代码：

#include<bits/stdc++.h>
#define N 200005
#define mod 998244353
#define ll long long
using namespace std;

struct node {
	int n, m;
	int a[5][5];
	friend node operator * (node x, node y) {
		node z;
		if(x.n == 2 && x.m == 2 && y.n == 2 && y.m == 2) {
			z.n = z.m = 2;
			z.a[1][1] = 1ll * ((long long)1ll * x.a[1][1] * y.a[1][1] % mod + (long long)1ll * x.a[1][2] * y.a[2][1] % mod + mod) % mod;
			z.a[1][2] = 1ll * ((long long)1ll * x.a[1][1] * y.a[1][2] % mod + (long long)1ll * x.a[1][2] * y.a[2][2] % mod + mod) % mod;
			z.a[2][1] = 1ll * ((long long)1ll * x.a[2][1] * y.a[1][1] % mod + (long long)1ll * x.a[2][2] * y.a[2][1] % mod + mod) % mod;
			z.a[2][2] = 1ll * ((long long)1ll * x.a[2][1] * y.a[1][2] % mod + (long long)1ll * x.a[2][2] * y.a[2][2] % mod + mod) % mod;
			return z;
		}
		else {
			z.n = 2; z.m = 1;
			z.a[1][1] = 1ll * ((long long)1ll * x.a[1][1] * y.a[1][1] % mod + (long long)1ll * x.a[1][2] * y.a[2][1] % mod + mod) % mod;
			z.a[2][1] = 1ll * ((long long)1ll * x.a[2][1] * y.a[1][1] % mod + (long long)1ll * x.a[2][2] * y.a[2][1] % mod + mod) % mod;
			return z;
		}
	}
};

void Out(node X) {
	cout << endl;
	for(int i = 1; i <= X.n; i++) {
		for(int j = 1; j <= X.m; j++) cout << X.a[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}

node Empty() {
	node now;
	now.n = now.m = 2;
	now.a[1][1] = now.a[2][2] = 1;
	now.a[1][2] = now.a[2][1] = 0;
	return now;
}
int n, Q, root, cnt;
int ls[N], rs[N], siz[N], pri[N];
node My[N];
char r[N];
node val[N], val_f[N], val_r[N], val_fr[N];
bool tagf[N], tagr[N]; //f:是否取反 r:是否翻转 

node W, E, P, X;

int newnode(char opt) {
	cnt++;
	siz[cnt] = 1;
	pri[cnt] = rand() * rand(); 
	
	if(opt == 'E') {
		val[cnt] = val_r[cnt] = E;
		val_f[cnt] = val_fr[cnt] = W;
	}
	else {
		val[cnt] = val_r[cnt] = W;
		val_f[cnt] = val_fr[cnt] = E;
	}
	
	My[cnt] = val[cnt];
	r[cnt] = opt;
	return cnt;
}


void pushup(int u) {
	siz[u] = siz[ls[u]] + siz[rs[u]] + 1;
	val[u] = val[ls[u]] * My[u] * val[rs[u]];
	node now;
	if(r[u] == 'E') now = W;
	else now = E;
	val_f[u] = val_f[ls[u]] * now * val_f[rs[u]];
	val_r[u] = val_r[rs[u]] * My[u] * val_r[ls[u]];
	val_fr[u] = val_fr[rs[u]] * now * val_fr[ls[u]];
}

void maketag(int u, bool F, bool R) { //Flip, Revserse, 
	node A = val[u], B = val_r[u], C = val_f[u], D = val_fr[u];
	if(!F && R) { //只翻转
		swap(ls[u], rs[u]);
		val[u] = B;
		val_r[u] = A;
		val_f[u] = D;
		val_fr[u] = C;
		tagr[u] ^= 1;
	}
	else if(F && !R) { //只取反 
		val[u] = C;
		val_r[u] = D;
		val_f[u] = A;
		val_fr[u] = B;
		tagf[u] ^= 1;
		if(r[u] == 'E') {
			r[u] = 'W';
			My[u] = W;
		}
		else {
			r[u] = 'E';
			My[u] = E;
		}
	}
	else if(F && R) { //取反+翻转
		swap(ls[u], rs[u]);
		val[u] = D;
		val_r[u] = C;
		val_f[u] = B;
		val_fr[u] = A; 
		tagf[u] ^= 1;
		tagr[u] ^= 1;
		if(r[u] == 'E') {
			r[u] = 'W';
			My[u] = W;
		}
		else {
			r[u] = 'E';
			My[u] = E;
		}
	}
}

void pushdown(int u) {
	maketag(ls[u], tagf[u], tagr[u]);
	maketag(rs[u], tagf[u], tagr[u]);
	tagf[u] = tagr[u] = 0;
}

int merge(int x, int y) {
	if(x == 0 || y == 0) return x + y;
	pushdown(x); pushdown(y);
	if(pri[x] < pri[y]) {
		rs[x] = merge(rs[x], y);
		pushup(x);
		return x;
	} 
	else {
		ls[y] = merge(x, ls[y]);
		pushup(y);
		return y;
	}
}

void split(int u, int &x, int &y, int k) {
	if(u == 0) {
		x = y = 0;
		return;
	}
	pushdown(u);
	if(k <= siz[ls[u]]) {
		y = u;
		split(ls[u], x, ls[u], k);
	}
	else {
		x = u;
		split(rs[u], rs[u], y, k - siz[ls[u]] - 1);
	}
	pushup(u);
}

void Insert(char opt) {
	root = merge(root, newnode(opt));
}

string S, opt;

void Flip(int l, int r) {
	int x, y, z;
	split(root, x, y, l - 1);
	split(y, y, z, r - l + 1);
	maketag(y, 1, 0);
	root = merge(merge(x, y), z);
}

void Reverse(int l, int r) {
	int x, y, z;
	split(root, x, y, l - 1);
	split(y, y, z, r - l + 1);
	maketag(y, 0, 1);
	root = merge(merge(x, y), z);
}

void Print() {
	node Ans = P * val[root] * X;
	cout << Ans.a[2][1] << " " << Ans.a[1][1] << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	val[0] = val_f[0] = val_r[0] = val_fr[0] = Empty();
	W.n = W.m = E.n = E.m = P.n = P.m = 2;
	W.a[1][1] = 1; W.a[1][2] = 1; W.a[2][1] = 0; W.a[2][2] = 1;
	E.a[1][1] = 0; E.a[1][2] = -1; E.a[2][1] = 1; E.a[2][2] = 2;
	P.a[1][1] = 1; P.a[1][2] = 1; P.a[2][1] = 0; P.a[2][2] = 1;
	X.n = 2; X.m = 1;
	X.a[1][1] = 0; X.a[2][1] = 1;
	cin >> n >> Q >> S;
	for(int i = 0; i < n; i++) Insert(S[i]);
	Print();
	while(Q--) {
		cin >> opt;
		if(opt[0] == 'A') { //append
			char c;
			cin >> c;
			Insert(c);
		}
		else if(opt[0] == 'F') {
			int l, r;
			cin >> l >> r;
			Flip(l, r); 
		}
		else {
			int l, r;
			cin >> l >> r;
			Reverse(l, r);
		}
		Print();
	}
	return 0;
}

标签：begin,P7739,end,密码箱,long,NOI2021,1ll,bmatrix,mod
From： https://www.cnblogs.com/xcs123/p/18144616

相关文章

  • NOI2021 轻重边 题解
    NOI2021轻重边题目链接：#4812.[NOI2021]轻重边前置知识：#树链剖分#线段树题目大意给定\(n\)个点组成的树，\(m\)次操作。修改操作会让路径\(a\tob\)上的所有点的所有连边对答案的贡献变为\(0\)，路径\(a\tob\)的所有边的贡献变为\(1\)；查询操作则统计路径\(a\tob\)的......
  • P8112 [Cnoi2021] 符文破译 题解
    题目传送门思路先看数据范围，我们发现两个字符串的长度最大会达到\(5\times10^7\)。这立刻打消了我用暴力的想法。于是，我选择了用KMP模式匹配，这一个能够在线性时间内判定字符串\(A\)是否是字符串\(B\)的字串，并求出字符串\(A\)在字符串\(B\)中各次出现的位置。如......
  • P7735 [NOI2021] 轻重边 题解
    是一道树剖好题，之前听lsl讲过一点，于是很快就做出来了。题意：有一个\(n\)个节点的树，最开始的时候所有边都是轻边，维护两个操作：操作一：将\(u\)到\(v\)的路径中经过的所有点的邻边变为轻边，再将这条路径上的边变为重边。操作二：求出\(u\)到\(v\)这条路径上有多少条重边......
  • P8111 [Cnoi2021] 区间
    [Cnoi2021]区间LuoguP8111题目背景Cirno有一个区间\([a,b](1\lea\leb\len)\)，而你的任务是在规定的次数内帮Rumia猜出这个区间。每次，你可向Cirno询问一个数字\(k\)，而Cirno会告诉你这个数字与区间\([a,b]\)的关系。题目描述为了猜到这个区间，你需要实现一个函......
  • NOI2021 路径交点
    洛谷传送门LOJ传送门两条路径的交点数量只和起点数量有关。容易发现是终点排列的逆序对数的奇偶性。求一个\(f_{i,j}\)表示从第\(1\)层的第\(i\)个点到第\(k\)层的第\(j\)个点的路径数量，对这个矩阵求行列式即可。对于相交的路径数不用考虑，因为总存在和它对应的一条......
  • [NOI2021] 庆典
    题目描述C国是一个繁荣昌盛的国家，它由\(n\)座城市和\(m\)条有向道路组成，城市从\(1\)到\(n\)编号。如果从\(x\)号城市出发，经过若干条道路后能到达\(y\)号城市，那么我们称\(x\)号城市可到达\(y\)号城市，记作\(x\Rightarrowy\)。C国的道路有一个特点：对于三座城市......
  • [NOI2021] 轻重边题解
    题目传送门一眼数据结构考虑树上有什么数据结构支持\(x\)到\(y\)节点的修改和查询，那就是：树链剖分。那么这道树链剖分的题有个\(trick\)：边点转换&染色法，对于每次修改，考虑将修改路径上的点全部染上一种独一无二的颜色，而查询的时候，就查询路径上相邻的相同的颜色节点个数即可......
  • 洛谷 P7739 - [NOI2021] 密码箱
    感觉难度和今年D2T2差不多。首先一个很显然的事情是，每一步得到的分数的分子分母都是互质的，证明参考SBT。而最后答案要求我们将分子分母都求出来而不是求分数值，所以可以很明显的想到将分数当成一个二元组然后维护变换。考虑从右往左扫，假设当前分数为\(\dfrac{x}{y}\)，那么扫过......
  • [NOI2021] 路径交点 题解
    [NOI2021]路径交点题解题意给定一张\(k\)层的有向图，第\(i\)层有\(n_i\)​个顶点，第​\(1\)层与第\(k\)​层顶点数相同。对于第​​\(j\)\((1\leqj<k)\)层的顶点，只会连向第\(j+1\)层的顶点。没有边连向第\(1\)层的顶点，第\(k\)层的顶点不会向其他顶点连边......
  • NOI2021 题解
    [NOI2021]轻重边转化一下题意：每次给一条链染色，查一条链从\(x\)到\(y\)有几条边两端颜色相同。那这个随便树剖线段树就好了。也可以LCT，码量可能要小点。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>usingnamespace......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99