题解 P7739 [NOI2021] 密码箱

wishapig · 2021-07-30 12:06:22 · 题解

文章中的做法是我在现场想出来的，然而被卡成 70。

首先分子分母显然一定互质，不用考虑除一个 \gcd 的事情（点名排水系统）。

Part1

考虑这么一个连分数：

（它是 f(a_0,a_1,\cdots,a_k) 的倒数）

如果从 a_k 到 a_0，从下往上进行合并时，我们会发现实际上是一个 \dfrac{a'}{b'}=\dfrac{1}{a_i+\dfrac{a}{b}} 的形式

那么考虑一个 a_i 合并上之后会对 a,b 造成什么变化：

也就是：a'=b,b'=a_i\times b+a

这可以用矩阵来描述：

好耶我们可以使用式子

来求出最后的分数了，然而这也是一个暴力。

Part2

好了我们有了一个矩阵描述连分数的想法，由于矩阵乘法有结合律，可以任意变换乘法的先后顺序，那么我们能否使用常矩阵来描述 W 和 E 操作呢？

首先看一下 W 操作，它让 a_k\rightarrow a_k+1

考虑矩阵从 \begin{bmatrix} 0 & 1 \\ 1 & a_k \end{bmatrix} 变成了 \begin{bmatrix} 0 & 1 \\ 1 & a_k+1 \end{bmatrix}。

一定是有一个矩阵 \begin{bmatrix} x & y \\ z & w \end{bmatrix}，使得 \begin{bmatrix} 0 & 1 \\ 1 & a_k \end{bmatrix}\begin{bmatrix} x & y \\ z & w \end{bmatrix}=\begin{bmatrix} 0 & 1 \\ 1 & a_k+1 \end{bmatrix}。

通过构造可以得到 \begin{bmatrix} x & y \\ z & w \end{bmatrix}=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}，也就是如果出现了一个 W 操作，那可以在矩阵连乘积的最后再乘上一个 \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}，从而一个 W 操作可以用一个常矩阵来描述。

之后是 E 操作，要分 a_k=1 和 a_k>1 两种情况，首先来看一下 a_k>1 时的情况。

• 添加两个 1 到数列末尾。

第一个 a_k\rightarrow a_k-1，可以依照上面的思想，构造 \begin{bmatrix} 0 & 1 \\ 1 & a_k \end{bmatrix}\begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}=\begin{bmatrix} 0 & 1 \\ 1 & a_k-1 \end{bmatrix}。

之后是两个添加操作，那么就直接在矩阵连乘积的末尾再乘上 \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}。

（注意所有的这些矩阵乘法都可以通过使用结合律改变乘法顺序得到实际意义）

于是第一种 a_k>1 的情况可以在连乘积之后乘上 \begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}=\begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix} 来描述。

还有第二种 a_k=1 的情况，此时有 a_{k-1}\rightarrow a_{k-1}+1，这似乎比较难直接构造一个矩阵。

然后我们灵机一动，这个 a_k>1 时数列的变化这么阴间，一定是有意弄成这样来达到某个目的的，于是我们大胆猜想 a_k=1 时的矩阵也是 \begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix}，可以验证这是对的：

当 a_k=1 时，a_k 对应的矩阵就是 \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}，按正常的顺序，应当是（最后两项为）\begin{bmatrix} 0 & 1 \\ 1 & a_{k-1} \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}（中间一项是使 a_{k-1}+1 的矩阵，最后一项是 a_k 对应的矩阵，注意由于结合律我没有写上括号，在实际计算中可以按顺序进行乘法），这个东西化简出来是 \begin{bmatrix} 0 & 1 \\ 1 & a_{k-1} \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 1 & 1 \end{bmatrix}。

而如果我们直接在最后乘上一个 \begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix}，会得到 \begin{bmatrix} 0 & 1 \\ 1 & a_{k-1} \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix}，这个化简出来是 \begin{bmatrix} 0 & 1 \\ 1 & a_{k-1} \end{bmatrix}\begin{bmatrix} 1 & 2 \\ 1 & 1 \end{bmatrix}，与前面那个刚好相同！所以直接在连乘积之后乘上一个 \begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix} 的大胆想法是正确的。

所以我们用一个 \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} 来描述 W 操作，一个 \begin{bmatrix} 0 & -1 \\ 1 & 2 \end{bmatrix} 来描述 E 操作。

Part3

ds 带师可以略过这一部分

之后 W 和 E 操作就分别对应一种矩阵，要用某种数据结构维护矩阵连乘积，支持区间取反和区间翻转。

要维护的信息是区间连乘积，区间取反连乘积，区间翻转连乘积，区间取反翻转连乘积，和两个 \rm tag：是否取反，是否翻转。

有了区间翻转操作，那就要用平衡树而非线段树来维护区间了，选用任何一种可以支持区间翻转的平衡树都可以实现，我在考场上使用的是 \rm fhq\ treap（人傻常数大结果被卡成 70 分）

Part4

小小细节：

• 在最开始数列中有 a_0=0,a_1=1，因此初始的矩阵连乘积是 \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}。

• 拆了结构体 70 \rightarrow 100（恼）。

• fhq treap 真的打不过 splay。

code：

const int mod=998244353;
const int N=2e5+500;
struct mat{ int a00,a01,a10,a11; } I,a,b,cur;
int pri[N],siz[N],ls[N],rs[N],tagf[N],tagi[N];
mat val[N],fil[N],inv[N],fnv[N],It[N],Itv[N];
int n,q,l,r,rt,rt1,rt2,rt3,rt4,treesize;
char s[N],c[100];
mat operator * (const mat& a, const mat& b){
    mat c;
    c.a00=(1ll*a.a00*b.a00+1ll*a.a01*b.a10)%mod;
    c.a01=(1ll*a.a00*b.a01+1ll*a.a01*b.a11)%mod;
    c.a10=(1ll*a.a10*b.a00+1ll*a.a11*b.a10)%mod;
    c.a11=(1ll*a.a10*b.a01+1ll*a.a11*b.a11)%mod;
    return c;
}
inline int Newnode(int k){
    int now=++treesize;
    if (k==0){
        val[now]=a; inv[now]=b;
        fil[now]=a; fnv[now]=b;
        It[now]=a; Itv[now]=b;
    } else {
        val[now]=b; inv[now]=a;
        fil[now]=b; fnv[now]=a;
        It[now]=b; Itv[now]=a;
    }
    siz[now]=1;
    return now;
}
inline void pushup(int now){
    if (!now) return;
    siz[now]=siz[ls[now]]+siz[rs[now]]+1;

    val[now]=(val[ls[now]]*It[now])*val[rs[now]];
    inv[now]=(inv[ls[now]]*Itv[now])*inv[rs[now]];

    fil[now]=(fil[rs[now]]*It[now])*fil[ls[now]];
    fnv[now]=(fnv[rs[now]]*Itv[now])*fnv[ls[now]];
}
inline void pushtagf(int now){
    if (!now) return;
    swap(val[now],fil[now]);
    swap(inv[now],fnv[now]);
    swap(ls[now],rs[now]);
    tagf[now]^=1;
}
inline void pushtagi(int now){
    if (!now) return;
    swap(val[now],inv[now]);
    swap(fil[now],fnv[now]);
    swap(It[now],Itv[now]);
    tagi[now]^=1;
}
inline void pushdown(int now){
    if (!now) return;
    if (tagf[now]) pushtagf(ls[now]),pushtagf(rs[now]),tagf[now]=0;
    if (tagi[now]) pushtagi(ls[now]),pushtagi(rs[now]),tagi[now]=0;
}
int Merge(int now, int las){
    if (!now || !las) return now|las;
    pushdown(now); pushdown(las);
    if (pri[now]<pri[las]){
        rs[now]=Merge(rs[now],las);
        pushup(now); return now;
    } else {
        ls[las]=Merge(now,ls[las]);
        pushup(las); return las;
    }
}
void Split(int now, int& r1, int& r2, int pos){
    if (!now){ r1=r2=0; return; }
    pushdown(now);
    if (siz[ls[now]]+1<=pos) r1=now,Split(rs[now],rs[r1],r2,pos-siz[ls[now]]-1);
    else r2=now,Split(ls[now],r1,ls[r2],pos);
    pushup(r1); pushup(r2);
}
int main(){
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);

    srand(19260817);
    for (int i=1; i<=n+q; i++) pri[i]=i;
    random_shuffle(pri+1,pri+1+n+q);
    I.a00=I.a11=1; I.a10=I.a01=0;
    a.a00=a.a01=a.a11=1; a.a10=0;
    b.a00=0,b.a01=mod-1,b.a10=1,b.a11=2;

    val[0]=fil[0]=inv[0]=fnv[0]=It[0]=Itv[0]=I;

    for (int i=1; i<=n; i++) rt=Merge(rt,Newnode(s[i]=='W'?0:1));

    cur=a*val[rt];
    printf("%d %d\n",cur.a11,cur.a01);

    for (; q; q--){
        scanf("%s",c+1);
        if (c[1]=='A'){
            scanf("%s",c+1);
            rt=Merge(rt,Newnode(c[1]=='W'?0:1));
        } else
        if (c[1]=='F'){
            scanf("%d%d",&l,&r);
            Split(rt,rt1,rt2,r);      // rt1:[1..r],rt2:[r+1..n]
            Split(rt1,rt3,rt4,l-1);   // rt3:[1..l-1],rt4:[l..r]
            pushtagi(rt4);
            rt=Merge(Merge(rt3,rt4),rt2);
        } else {
            scanf("%d%d",&l,&r);
            Split(rt,rt1,rt2,r);      // rt1:[1..r],rt2:[r+1..n]
            Split(rt1,rt3,rt4,l-1);   // rt3:[1..l-1],rt4:[l..r]
            pushtagf(rt4);
            rt=Merge(Merge(rt3,rt4),rt2);
        }
        cur=a*val[rt];
        printf("%d %d\n",cur.a11,cur.a01);
    }
    return 0;
}
/*
2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3
*/

代码仅供参考，不喜勿喷。

Bonus

提供一个只用维护连乘积的做法，不需要维护 4 个乘积：

对一个矩阵 \begin{bmatrix} a & b \\ c & d \end{bmatrix}，考虑直接通过 a,b,c,d 的线性组合凑出 Flip 和 Reverse 操作序列之后的矩阵。

通过这题的特殊性（只有两种常矩阵的乘积）和人类智慧（指高斯消元解方程组），凑出了以下矩阵变换：

这两个都可以用数学归纳法证明对任意操作序列都是对的。

那么在 pushup 的时候矩阵乘法的次数就会减少至原来的 \dfrac{1}{4}，常数显著优化 （还是打不过 splay）。

inline void pushtagf(int now){
    if (!now) return;

    int A=val[now].a00,B=val[now].a01,C=val[now].a10,D=val[now].a11;
    val[now]=(mat){(D-2*C%mod+mod)%mod,((-2ll*A+B-4ll*C+2ll*D)%mod+mod)%mod,C,(A+2*C%mod)%mod};

    swap(ls[now],rs[now]);
    tagf[now]^=1;
}
inline void pushtagi(int now){
    if (!now) return;
    int A=val[now].a00,B=val[now].a01,C=val[now].a10,D=val[now].a11;
    val[now]=(mat){(A-B+mod)%mod,(mod-B)%mod,((D-A+B-C)%mod+mod)%mod,(B+D)%mod};

    A=It[now].a00,B=It[now].a01,C=It[now].a10,D=It[now].a11;
    It[now]=(mat){(A-B+mod)%mod,(mod-B)%mod,((D-A+B-C)%mod+mod)%mod,(B+D)%mod};
    tagi[now]^=1;
}

最后感谢管理对格式问题的指出和粉兔的修改

求赞 qwq