P7739 [NOI2021] 密码箱的加密算法是什么？

本文共计2223个文字，预计阅读时间需要9分钟。

P7739 [NOI2021] 密码箱 题目链接：Link 本题主要思路来源于 Rikka (疯狂 + % + )。题目中的贡献值计算实际上是一个连续整数的倒数和，即：[a_1 + 1/(a_2 + 1/(a_3 + ... + 1/a_n))] 若从 (a_k) 到 (a_n)。

P7739 [NOI2021] 密码箱

题目链接： Link

本题解主要思路来源 @Rikka__(疯狂 % )。

考虑题里面的贡献的计算其实是一个连分数的倒数，即：

\[a_1+\frac {1}{a_2+\frac{1}{a_3 + ...}} \]

若从 \(a_k\) 到 \(a_1\) 从下向上合并的话能够发现其实是一个 $ \Large \frac{a'}{b'} = \frac {1}{a_i+\frac{a}{b}}$ 的形式。（首先根据辗转相除法的那一套理论明显是不用考虑约分）

那么考虑将 \(a_i\) 合并上后对答案的影响：

\[\frac {a'}{b'} = \frac{1}{a_i+\frac{a}{b}} = \frac {b}{a_i \times b + a} \]

那么也就是 \(a' = b ,b' = a_i \times b + a\)

转移是固定的故可以考虑使用矩阵进行转移：

\[\left[ \begin {array}{l} a'\\ b' \end{array} \right] = \left[ \begin {array}{l} 0 &1\\ 1&a_i \end{array} \right] \left[ \begin {array}{l} a\\ b \end{array} \right] \]

故答案即为：

\[\left[ \begin {array}{l} 0&1\\ 1&a_1 \end{array} \right] \left[ \begin {array}{l} 0&1\\ 1&a_2 \end{array} \right] ... \left[ \begin {array}{l} 0&1\\ 1&a_k \end{array} \right] \left[ \begin {array}{l} 0\\ 1 \end{array} \right] \]

继续考虑使用矩阵表述操作 W 和 E：

W：

\(a_k \rightarrow a_{k}+1\)

发现矩阵从 \(\left[\begin {array}{l}0&1\\1&a_k\end{array}\right]\) 变成 \(\left[\begin{array}{l} 0&1\\1&a_{k}+1 \end{array} \right ]\) 可以发现转移矩阵即为：\(\left[\begin{array}{l} 1&1\\0&1\end{array}\right]\) （右乘）

E：

\(a_k>1\)

\(a_k \rightarrow a_k - 1\) 并添加两个 \(1\) 到末尾。

按照上面的思路，发现 \(a_k \rightarrow a_k - 1\) 转移矩阵即为 \(\left[\begin{array}{l} 1&-1\\0&1\end{array}\right]\)

末尾添加两个 \(1\) 转移矩阵为 \(\left[\begin{array}{l}0&1\\1&1\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\)

按顺序整合一下即为 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)

\(a_k = 1\)

这时 \(a_k\) 对应的矩阵为 \(\left[\begin{array}{l}0&1\\1&1\end{array}\right]\)。

按照正常的运算应该为 \(\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&1\\0&1\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\) 。

按照结合律可变为 \(\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&2\\1&1\end{array}\right]\)

我们同样设一个矩阵 \(\left[\begin{array}{l}x&y\\z&k\end{array}\right]\)

满足：

\[\left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}0&1\\1&1\end{array}\right]\left[\begin{array}{l}x&y\\z&k\end{array}\right] = \left[\begin{array}{l}0&1\\1&a_{k-1}\end{array}\right]\left[\begin{array}{l}1&2\\1&1\end{array}\right] \]

解得矩阵 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)

故对于 E 操作只需要乘上 \(\left[\begin{array}{l}0&-1\\1&2\end{array}\right]\)

剩余部分比较简单，只需要用一颗支持序列翻转、取反操作的平衡树实现即可。具体维护 区间连乘积，区间取反连乘积，区间翻转连乘积，区间取反翻转连乘积。同时维护取反标记和翻转标记即可

时间复杂度：\(O(n\log n)\)

优化：

其实有时空复杂度都更优的写法，考虑对于 REVERSE 和 FLIP 操作也像 W E 那样去通过矩阵进行转移，具体的通过矩阵中 \(4\) 个元素的线性组合去构造转移矩阵。

设矩阵 $A = \left[\begin{array}{l} a&b \ c&d \end{array}\right] $。

有：

\[Flip(A) =\left[\begin{array}{l} a-b&-b \\ -a+b-c+d&b+d \end{array}\right]\\ \space \\\space \\ Reverse(A) = \left[\begin{array}{l} d-2c&-2a+b-4c+2d \\ c&a+2c \end{array}\right] \]

这样就可以不去维护 \(4\) 种乘积，空间和时间得到巨大优化。可以通过解方程来证明。

//editor : DRYAYST //Wo shi ge da SHA BI #include<bits/stdc++.h> #define g() getchar() #define il inline #define ull unsigned long long #define eps 1e-10 #define ll long long #define pa pair<int, int> #define for_1(i, n) for(int i = 1; i <= (n); ++i) #define for_0(i, n) for(int i = 0; i < (n); ++i) #define for_xy(i, x, y) for(int i = (x); i <= (y); ++i) #define for_yx(i, y, x) for(int i = (y); i >= (x); --i) #define for_edge(i, x) for(int i = head[x]; i; i = nxt[i]) #define int long long #define DB double #define ls tr[x].l #define rs tr[x].r #define m_p make_pair #define fi first #define se second using namespace std; const int N = 1e6 + 10, INF = 0x7f7f7f7f, mod = 998244353; il int qpow(int x, int k) {int ans = 1; while(k) {if(k & 1) ans = ans * x % mod; x = x * x % mod; k >>= 1; } return ans; } il int Add(int x, int y) {return (x += y) %= mod;} il int Del(int x, int y) {return (x = x - y + mod) % mod;} il int Mul(int x, int y) {return x * y % mod;} il int inv(int x) {return qpow(x, mod - 2); } inline int re() { int x = 0, p = 1; char ch = getchar(); while(ch > '9' || ch < '0') {if(ch == '-') p = -1; ch = getchar();} while(ch <= '9' and ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} return x * p; } mt19937 rd(20050426); int n, Q, rt, cnt ; char s[N], op[100]; struct Matrix { int a[2][2]; Matrix() {memset(a, 0, sizeof(a)); } il Matrix operator * (const Matrix &b) const {Matrix c; for_0(k, 2) for_0(i, 2) for_0(j, 2) c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod; return c;} il Matrix Rev(Matrix A) {Matrix c; c.a[0][0] = (A.a[1][1] - 2 * A.a[1][0] % mod + mod) % mod; c.a[0][1] = ((-2 * A.a[0][0] + A.a[0][1] - 4 * A.a[1][0] + 2 * A.a[1][1]) % mod + mod) % mod; c.a[1][0] = A.a[1][0]; c.a[1][1] = (A.a[0][0] + 2 * A.a[1][0] % mod) % mod; return c; } il Matrix Flip(Matrix A) { Matrix c; c.a[0][0] = (A.a[0][0] - A.a[0][1] + mod) % mod; c.a[0][1] = (-A.a[0][1] + mod) % mod; c.a[1][0] = ((-A.a[0][0] + A.a[0][1] - A.a[1][0] + A.a[1][1]) % mod + mod) % mod; c.a[1][1] = (A.a[0][1] + A.a[1][1]) % mod; return c; } }A, B, ans, use; //A，B分别为两个转移矩阵 struct Tree {int l, r; int val, siz, rtag, ftag; Matrix V, S; }tr[N]; il int Newed(int x) { int id = ++cnt; tr[id].V = (x==0?A:B); tr[id].S = tr[id].V; tr[id].l = tr[id].r = 0; tr[id].siz = 1; tr[id].rtag = tr[id].ftag = 0; tr[id].val = rd(); return id; } il void push_up(int x) {if(!x) return; tr[x].siz = tr[ls].siz + tr[rs].siz + 1; tr[x].S = tr[ls].S * tr[x].V * tr[rs].S; return; } il void push_rdown(int x) { if(!x) return ; tr[x].S = use.Rev(tr[x].S); swap(tr[x].l, tr[x].r); tr[x].rtag ^= 1; } il void push_fdown(int x) { if(!x) return ; tr[x].S = use.Flip(tr[x].S), tr[x].V = use.Flip(tr[x].V); tr[x].ftag ^= 1; } il void push_down(int x) { if(!x) return; if(tr[x].rtag) push_rdown(tr[x].l), push_rdown(tr[x].r), tr[x].rtag = 0; if(tr[x].ftag) push_fdown(tr[x].l), push_fdown(tr[x].r), tr[x].ftag = 0; } il int Merge(int k1, int k2) { if(!k1 || !k2) return k1 + k2; if(tr[k1].val < tr[k2].val) { push_down(k1); tr[k1].r = Merge(tr[k1].r, k2); push_up(k1); return k1; } else {push_down(k2); tr[k2].l = Merge(k1, tr[k2].l); push_up(k2); return k2; } } int Build(int l, int r) { if(l == r) {int now = Newed(s[l] != 'W'); return now;} int mid = (l + r) >> 1; int k1 = Build(l, mid), k2 = Build(mid + 1, r); return Merge(k1, k2); } il int Insert(int rt, int fl) {return Merge(rt, Newed(fl)); } void Split(int rt, int x, int &k1, int &k2) { if(!rt) {k1 = 0; k2 = 0; return ; } push_down(rt); if(tr[tr[rt].l].siz < x) {k1 = rt; Split(tr[rt].r, x - tr[tr[rt].l].siz -1 , tr[k1].r, k2); push_up(k1); } else {k2 = rt; Split(tr[rt].l, x, k1, tr[k2].l); push_up(k2);} } il int Flip(int rt, int l, int r) { int k1, k2, k3; Split(rt, r, k1, k3); Split(k1, l - 1, k1, k2); push_fdown(k2); return Merge(k1, Merge(k2, k3)); } il int Reverse(int rt, int l, int r) { int k1, k2, k3; Split(rt, r, k1, k3); Split(k1, l-1, k1, k2); push_rdown(k2); return Merge(k1, Merge(k2, k3)); } signed main() { n = re(), Q = re(); scanf("%s", s + 1); A.a[0][0] = 1; A.a[0][1] = 1; A.a[1][1] = 1; B.a[0][1] = mod - 1; B.a[1][0] = 1; B.a[1][1] = 2; tr[0].V.a[0][0] = 1; tr[0].V.a[1][1] = 1; tr[0].S = tr[0].V; rt = Build(1, n); ans = A * tr[rt].S; printf("%lld %lld\n", ans.a[1][1], ans.a[0][1]); while(Q--) { scanf("%s", op + 1); if(op[1] == 'A') { scanf("%s", op + 1); rt = Insert(rt, op[1] != 'W'); } else if(op[1] == 'F') {int l = re(), r = re(); rt = Flip(rt, l, r); } else {int l = re(), r = re(); rt = Reverse(rt, l, r); } ans = A * tr[rt].S; printf("%lld %lld\n", ans.a[1][1], ans.a[0][1]); } }

可能代码有点不能看,建议 loj 格式化后观看更清晰。