家具网站建设规划书,手机网站 方案,企业网站制作方法,手机微信网站怎么做的好处正题
题目链接:https://www.luogu.com.cn/problem/P7739 题目描述
懒得概括#xff0c;摸了。
Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中#xff0c;他发掘出了一个远古时期的密码箱。经过周密而严谨的考证#xff0c;Yelekastee 得知密码箱的密码和某一…正题
题目链接:https://www.luogu.com.cn/problem/P7739 题目描述
懒得概括摸了。
Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中他发掘出了一个远古时期的密码箱。经过周密而严谨的考证Yelekastee 得知密码箱的密码和某一个数列 {an}\{ a_n \}{an} 相关。数列 {an}\{ a_n \}{an} 可以用如下方式构造出来
初始时数列长度为 222 且有 a00,a11a_0 0, a_1 1a00,a11对数列依次进行若干次操作其中每次操作是以下两种类型之一
W 类型给数列的最后一项加 111。E 类型若数列的最后一项为 111则给倒数第二项加 111否则先给数列的最后一项减 111接着在数列尾再加两项两项的值都是 111。
受到技术限制密码箱并没有办法完整检查整个数列因此密码箱的密码设定为数列 {an}\{ a_n \}{an} 经过函数 fff 作用后的值其中 fff 的定义如下
f(a0,…,ak−1,ak){a0,amp;k0f(a0,a1,…,ak−2,ak−11ak),amp;k≥1f(a_0, \ldots , a_{k - 1}, a_k) \begin{cases} a_0, amp; k 0 \\ f \! \left( a_0, a_1, \ldots , a_{k - 2}, a_{k - 1} \frac{1}{a_k} \right) \! , amp; k \ge 1 \end{cases} f(a0,…,ak−1,ak){a0,f(a0,a1,…,ak−2,ak−1ak1),amp;k0amp;k≥1
Yelekastee 并不擅长运算因此他找到了你希望你能根据他提供的操作序列计算出密码箱的密码。不幸的是他的记性并不是很好因此他会随时对提供的操作序列做出一些修改这些修改包括以下三种
APPEND c在现有操作序列后追加一次 c 类型操作其中 c 为字符 W 或 E。FLIP l r反转现有操作序列中第 lll 个至第 rrr 个下标从 111 开始修改包含端点 lll 和 rrr下同操作即所有 W 变为 E所有 E 变为 W。REVERSE l r翻转现有操作序列中第 lll 个至第 rrr 个操作也就是将这个区间中的操作逆序。
1≤n,q≤1051\leq n,q\leq 10^51≤n,q≤105 解题思路
先考虑知道aaa序列怎么求答案假设上一个传下来的是xy\frac{x}{y}yx那么新的那个就是x′y′akxyyakxx\frac{x}{y}a_k\frac{x}{y}\frac{ya_kx}{x}y′x′akyxxyakx那么有x′yakx,y′xxya_kx,yxx′yakx,y′x。
显然如果我们只是动态修改每一个aaa那么上面这个转移可以用矩阵乘法维护。
但是我们现在的操作可能是让一些数111和在数列后面111。麻烦的是让一些数111这个操作我们考虑如果我们在末尾加入了一个111那么转移x′xy,y′xxxy,yxx′xy,y′x如果让末尾的一个数加111那么x′xy,y′yxxy,yyx′xy,y′y。这样就可以直接考虑矩阵维护EWEWEW操作了我们分别设上面两个操作的矩阵为HA,HBH_A,H_BHA,HB我们求出一个GA×HA1,GB×HB1G_A\times H_A1,G_B\times H_B1GA×HA1,GB×HB1这样就可以取消掉前面的一些操作了。
然后考虑一下下面的操作怎么实现设目前的矩阵乘积为MMM
让末尾111M′HA×HB×GA×MMH_A\times H_B\times G_A\times MM′HA×HB×GA×M让倒数第二个111注意到此时最后一个数字肯定是111所以M′HA×HA×HB×GA×GA×MMH_A\times H_A\times H_B\times G_A\times G_A\times MM′HA×HA×HB×GA×GA×M让最后一个数−1-1−1然后在末尾加入两个111M′HA×HA×HA×GB×GA×MMH_A\times H_A\times H_A\times G_B \times G_A\times MM′HA×HA×HA×GB×GA×M
然后我们会愉快的发现后两个和EEE有关的操作有HA×HA×HB×GA×GAHA×HA×HA×GB×GAH_A\times H_A\times H_B\times G_A\times G_AH_A\times H_A\times H_A\times G_B \times G_AHA×HA×HB×GA×GAHA×HA×HA×GB×GA。
也就是其实EEE两种情况的操作乘上的都是同一个矩阵那么用Splay维护即可区间翻转和区间取反操作可以直接维护四个值表示是否取反/翻转后的矩阵就行了。
至于输出x%P,y%Px\%P,y\%Px%P,y%P的gcd(x,y)gcd(x,y)gcd(x,y)为111的要求我们不用担心因为上面的操作中x,yx,yx,y的gcdgcdgcd都是不会变的因为gcd(xy,x)gcd(x,y)gcd(xy,x)gcd(x,y)gcd(xy,x)gcd(x,y)所以无论怎样操作x,yx,yx,y都是互质的。
时间复杂度O((nq)logn)O((nq)\log n)O((nq)logn) code
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int N2e510,S2,P998244353;
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void print(int x)
{if(x9)print(x/10);putchar(0x%10);}
struct Matrix{int a[S][S];
}Ha,Hb,Ga,Gb,HA,HB,HC,O,c;
void add(int x,int y)
{x(xyP)?(xy-P):(xy);}
Matrix operator*(const Matrix a,const Matrix b){memset(c.a,0,sizeof(c.a));for(int i0;iS;i)for(int j0;jS;j)for(int k0;kS;k)add(c.a[i][j],1ll*a.a[i][k]*b.a[k][j]%P);return c;
}
struct node{Matrix M,N;void flp(){swap(M,N);return;}
}W,E,tmp;
int n,q,cnt,root;
char s[N];
struct PeTree{node w[N],v[N],a[N];int t[N][2],fa[N],siz[N];bool r[N],u[N];void PushUp(int x){w[x]v[x]a[x];if(t[x][1]){w[x].Mw[t[x][1]].M*w[x].M;v[x].Mv[x].M*v[t[x][1]].M;w[x].Nw[t[x][1]].N*w[x].N;v[x].Nv[x].N*v[t[x][1]].N;}if(t[x][0]){w[x].Mw[x].M*w[t[x][0]].M;v[x].Mv[t[x][0]].M*v[x].M;w[x].Nw[x].N*w[t[x][0]].N;v[x].Nv[t[x][0]].N*v[x].N;}siz[x]siz[t[x][0]]siz[t[x][1]]1;return;}void PushR(int x){swap(t[x][0],t[x][1]);swap(w[x],v[x]);r[x]^1;return;}void PushU(int x){w[x].flp();v[x].flp();a[x].flp();u[x]^1;return;}void PushDown(int x){if(r[x])PushR(t[x][0]),PushR(t[x][1]),r[x]0;if(u[x])PushU(t[x][0]),PushU(t[x][1]),u[x]0;return;}bool Direct(int x){return t[fa[x]][1]x;}void Rotate(int x){int yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[x][xs^1];if(z)t[z][ys]x;t[x][xs^1]y;t[y][xs]w;if(w)fa[w]y;fa[y]x;fa[x]z;PushUp(y);PushUp(x);return;}void Downdata(int x,int f){if(xf)return;Downdata(fa[x],f);PushDown(x);return;} void Splay(int x,int f){if(!f)rootx;Downdata(x,f);while(fa[x]!f){int yfa[x];if(fa[y]f)Rotate(x);else if(Direct(x)Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}int Find(int val,int xroot){PushDown(x);if(siz[t[x][0]]val)return Find(val,t[x][0]);if(siz[t[x][0]]1val)return x;return Find(val-siz[t[x][0]]-1,t[x][1]);}
}T;
int power(int x,int b){int ans1;while(b){if(b1)ans1ll*ans*x%P;x1ll*x*x%P;b1;}return ans;
}
void Query(){T.Splay(1,0);T.Splay(n2,1);Matrix ansT.w[T.t[n2][0]].M;int aans.a[0][0];int bans.a[0][1];swap(a,b);ab;a(a%PP)%P;b(bP)%P;print(b);putchar( );print(a);putchar(\n);
}
signed main()
{nread();qread();O.a[0][0]1;O.a[1][0]0;O.a[1][0]0;O.a[1][1]1;Ha.a[0][0]1;Ha.a[1][0]1;Ha.a[0][1]0;Ha.a[1][1]1;Ga.a[0][0]1;Ga.a[1][0]P-1;Ga.a[0][1]0;Ga.a[1][1]1;Hb.a[0][0]1;Hb.a[1][0]1;Hb.a[0][1]1;Hb.a[1][1]0;Gb.a[0][0]0;Gb.a[1][0]1;Gb.a[0][1]1;Gb.a[1][1]P-1;HAHb*Ha*Gb;HBHb*Hb*Ha*Gb*Gb;HCHb*Hb*Hb*Ga*Gb;W(node){HA,HB};E(node){HB,HA};scanf(%s,s1);cntn2;T.t[1][1]2;T.fa[n2]n1;for(int i2;in1;i){if(s[i-1]W)T.a[i]W;else T.a[i]E;T.t[i][1]i1;T.fa[i]i-1;}for(int in2;i1;i--)T.PushUp(i);Query();int mn;while(q--){char op[10];scanf(%s,op);if(op[0]A){scanf(%s,op);cnt;if(op[0]W)T.a[cnt]W;else T.a[cnt]E;int pT.Find(m1);T.Splay(p,0);pn2;T.fa[cnt]p;T.t[p][0]cnt;T.PushUp(cnt);T.PushUp(p);m;}else if(op[0]F){int lread(),rread();lT.Find(l);rT.Find(r2);T.Splay(l,0);T.Splay(r,l);T.PushU(T.t[r][0]);T.Splay(T.t[r][0],0);}else if(op[0]R){int lread(),rread();lT.Find(l);rT.Find(r2);T.Splay(l,0);T.Splay(r,l);T.PushR(T.t[r][0]);T.Splay(T.t[r][0],0);}Query();}return 0;
}
