Koishi in Wetland Park

The Wetland Park in SUSTech has long been a mysterious and fascinating place to visit. Satori's little sister Koishi was attracted but unfortunately lost her way inside the park, so she called Satori for help.

There are $N(2\leq N\leq 100)$ viewing decks in the park, which are connected by $M(N-1\leq M\leq \frac{N\times(N-1)}{2} )$ plank roads build in the wetland park with some magical lychee trees growing alongside.

Initially the fruits along the $i^{th}$ road can be described by a pair $(A_i,B_i) (1\leq A_i,B_i\leq 10^8)$ , and Koishi will eat $A_i$ juicy lychees when she passes through the $i^{th}$ road.

Yet, each time Koishi passes through one road, the lychee trees along every road will change from $(A_j,B_j)$ to $(B_j,A_j \bmod B_j)$ unless its original $B_j=0$ (If $B_j=0$ , the pair $(A_j,B_j)$ will not change).

The sad truth is that Koishi is completely lost. Thus, she will randomly choose to start her journey from viewing deck $i(1\leq i\leq N-1)$ with probability $\frac{P_i}{\sum _{i=1} ^{N-1} P_i} (1\leq P_i\leq 10^6)$ . When she is at viewing deck $i$ , she will choose to walk through one plank road connecting it with equal probability. Satori is waiting for her at viewing deck $N$ . Boring as she is, she starts to calculate the expected number of lychees her little sister would eat before she reaches viewing deck $N$ .

As Satori is a master in Probability, she would change some of $P_i$ or pair $(A_j,B_j)$ . Formally, she will perform $Q (0\leq Q\leq 10^5)$ changes, for the $k^{th}$ one, she would first tell you the operation type $opt_k$ , then

If $opt_k=1$ , Satori will choose a viewing deck $x$ and change $P_x$ to $val(1\leq x\leq N,1\leq val\leq 10^6)$

If $opt_k=2$ , Satori will choose a road $u$ and change $(A_u,B_u)$ to $(a, b) (1\leq u\leq M, 1\leq a, b\leq 10^8)$

As Satori is quite lazy, the total number of the first operation will not exceed 100.

Also, as Satori is a master in Cryptology, she would make her problem even more difficult by performing $\oplus$ operation on her previous answer. Formally, if the answer after her last change is $res$ , then

If $opt_k=1$ and you receive $x,val$ , her actual changes will be: $x=((x\oplus res) \bmod (N-1)) +1$ and $val=((val \oplus res) \bmod 10^6)+1$

If $opt_k=2$ and you receive $u,a,b$ , her actual changes will be $u=((u\oplus res) \bmod M)+1,a=((a\oplus res) \bmod 10^8)+1 ,b=((b\oplus res) \bmod 10^8)+1$

Here $\bmod$ means module operator and $\oplus$ means exclusive or (XOR) operator.

Note that before Satori's first change $res=0$ , and the changes Satori made are accumulative.

The first line contains three integers $N,M,Q$ .
The second line contains $N-1$ integers $P_1,P_2,\dots,P_{N-1}$ .
The next $M$ lines each contain four integers $x_i,y_i,A_i,B_i$ , indicating the $i^{th}$ road connects deck $x_i$ and $y_i$ and has pair $(A_i,B_i)$ . Note that the roads are numbered from 1 to $M$ .
The next $Q$ lines each has one of the two following formats:
$1\; x \; val$
$2\; u\; a\; b$
Note that the graph is connected, and the total number of the first operation will not exceed 100.

#include <bits/stdc++.h> #define LL long long const int maxn=107; const int mod=998244353; using namespace std; int n,m,q,lim,res,ans; int p[maxn],deg[maxn],invd[maxn],a[maxn][maxn],b[maxn],E[maxn],f[47][maxn]; int from[maxn*maxn],to[maxn*maxn]; struct rec{ int a,b; }d[maxn][maxn]; int add(int x,int y) { if (x+y>=mod) return x+y-mod; return x+y; } int dec(int x,int y) { if (x>=y) return x-y; return x+mod-y; } int mul(int x,int y) { return (LL)x*y%mod; } int ksm(int x,int y) { if (!y) return 1; int c=ksm(x,y/2); c=mul(c,c); if (y&1) c=mul(c,x); return c; } void guass(int n) { for (int i=1;i<=n;i++) { for (int j=i+1;j<=n;j++) { if (a[j][i]>a[i][i]) { for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]); swap(b[i],b[j]); } } int inv=ksm(a[i][i],mod-2); for (int j=1;j<=n;j++) { if (i==j) continue; int rate=mul(a[j][i],inv)%mod; for (int k=i;k<=n;k++) a[j][k]=dec(a[j][k],mul(a[i][k],rate)); b[j]=dec(b[j],mul(b[i],rate)); } } for (int i=1;i<=n;i++) E[i]=mul(b[i],ksm(a[i][i],mod-2)); } void calc(int x,int y,int op) { if (x==n) return; int A=d[x][y].a,B=d[x][y].b; for (int k=1;k<=lim;k++) { if (op) ans=add(ans,mul(mul(f[k-1][x],invd[x]),A)); else ans=dec(ans,mul(mul(f[k-1][x],invd[x]),A)); if (B!=0) { int R=A%B; A=B; B=R; } } if (op) ans=add(ans,mul(mul(E[x],invd[x]),A)); else ans=dec(ans,mul(mul(E[x],invd[x]),A)); } void solve() { int sum=0; for (int i=1;i<=n-1;i++) sum=add(sum,p[i]); sum=ksm(sum,mod-2); for (int i=1;i<=lim;i++) { for (int j=1;j<=n;j++) f[i][j]=0; } for (int i=1;i<=n-1;i++) f[0][i]=mul(sum,p[i]); for (int i=1;i<=lim;i++) { for (int j=1;j<=n;j++) { for (int k=1;k<n;k++) { if (d[k][j].a) { f[i][j]=add(f[i][j],mul(f[i-1][k],invd[k])); } } } } for (int i=1;i<n;i++) { for (int j=1;j<n;j++) { if (i==j) a[i][j]=1; else if (d[i][j].a) a[i][j]=dec(0,invd[j]); } } for (int i=1;i<=n-1;i++) b[i]=f[lim][i]; guass(n-1); E[n]=1; ans=0; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (d[i][j].a) calc(i,j,1); } } } int main() { scanf("%d%d%d",&n,&m,&q); for (int i=1;i<=n-1;i++) scanf("%d",&p[i]); for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) d[i][j]=(rec){0,0}; } lim=40; for (int i=1;i<=m;i++) { scanf("%d%d",&from[i],&to[i]); scanf("%d%d",&d[from[i]][to[i]].a,&d[from[i]][to[i]].b); d[to[i]][from[i]]=d[from[i]][to[i]]; deg[from[i]]++; deg[to[i]]++; } for (int i=1;i<=n;i++) invd[i]=ksm(deg[i],mod-2); solve(); res=0; for (int i=1;i<=q;i++) { int opt; scanf("%d",&opt); if (opt==1) { int x,val; scanf("%d%d",&x,&val); x=((x^res)%(n-1))+1; val=((val^res)%1000000)+1; p[x]=val; solve(); } else { int u,x,y; scanf("%d%d%d",&u,&x,&y); u=((u^res)%m)+1; x=((x^res)%100000000)+1; y=((y^res)%100000000)+1; calc(from[u],to[u],0); calc(to[u],from[u],0); d[from[u]][to[u]].a=x; d[from[u]][to[u]].b=y; d[to[u]][from[u]]=d[from[u]][to[u]]; calc(from[u],to[u],1); calc(to[u],from[u],1); } printf("%d\n",ans); res=ans; } }

详情