1708.md (17598B)
1 Source: https://codeforces.com/blog/entry/104930 2 3 [1708A - Разностные операции](/contest/1708/problem/A "Codeforces Round 808 (Div. 2)") 4 5 idea: [Imakf](/profile/Imakf "Мастер Imakf") 6 7 **Solution** 8 9 Tutorial is loading... 10 11 **Code** 12 13 By [Imakf](/profile/Imakf "Мастер Imakf") 14 15 ``` 16 #include <bits/stdc++.h> 17 18 #define debug(...) fprintf(stderr ,__VA_ARGS__) 19 #define LL long long 20 21 const LL MOD = 1e9 + 7; 22 const int MX = 1e5 + 23; 23 24 int read(){ 25 char k = getchar(); LL x = 0; 26 while(k < '0' || k > '9') k = getchar(); 27 while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar(); 28 return x; 29 } 30 31 int n ,a[MX]; 32 void solve(){ 33 n = read(); 34 for(int i = 1 ; i <= n ; ++i) a[i] = read(); 35 int ok = 1; 36 for(int i = 1 ; i <= n ; ++i){ 37 if(a[i] % a[1]) ok = false; 38 } 39 puts(ok ? "YES" : "NO"); 40 } 41 42 int main(){ 43 int T = read(); 44 while(T--) solve(); 45 return 0; 46 } 47 ``` 48 49 [1708B - Различие НОДов](/contest/1708/problem/B "Codeforces Round 808 (Div. 2)") 50 51 idea: [waaitg](/profile/waaitg "Мастер waaitg") 52 53 **Solution** 54 55 Tutorial is loading... 56 57 **Code** 58 59 By [Imakf](/profile/Imakf "Мастер Imakf") 60 61 ``` 62 #include <bits/stdc++.h> 63 64 #define debug(...) fprintf(stderr ,__VA_ARGS__) 65 #define __FILE(x)\ 66 freopen(#x".in" ,"r" ,stdin);\ 67 freopen(#x".out" ,"w" ,stdout) 68 #define LL long long 69 70 const int MX = 1e5 + 23; 71 const LL MOD = 998244353; 72 73 int read(){ 74 char k = getchar(); int x = 0; 75 while(k < '0' || k > '9') k = getchar(); 76 while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar(); 77 return x; 78 } 79 80 int a[MX]; 81 void solve(){ 82 int n = read() ,l = read() ,r = read(); 83 int ok = 1; 84 for(int i = 1 ; i <= n ; ++i){ 85 a[i] = ((l - 1) / i + 1) * i; 86 ok = ok && a[i] <= r; 87 } 88 if(ok){ 89 puts("YES"); 90 for(int i = 1 ; i <= n ; ++i) 91 printf("%d%c" ,a[i] ," \n"[i == n]); 92 } 93 else puts("NO"); 94 } 95 96 int main(){ 97 int T = read(); 98 for(int i = 1 ; i <= T ; ++i){ 99 solve(); 100 } 101 return 0; 102 } 103 ``` 104 105 [1707A - Дореми и её IQ](/contest/1707/problem/A "Codeforces Round 808 (Div. 1)") 106 107 idea: [Imakf](/profile/Imakf "Мастер Imakf") 108 109 **Solution** 110 111 Tutorial is loading... 112 113 **Code of solution 1** 114 115 By [Imakf](/profile/Imakf "Мастер Imakf") 116 117 ``` 118 #include <bits/stdc++.h> 119 120 #define debug(...) fprintf(stderr ,__VA_ARGS__) 121 #define __FILE(x)\ 122 freopen(#x".in" ,"r" ,stdin);\ 123 freopen(#x".out" ,"w" ,stdout) 124 #define LL long long 125 126 const int MX = 5e5 + 23; 127 const LL MOD = 998244353; 128 129 int read(){ 130 char k = getchar(); int x = 0; 131 while(k < '0' || k > '9') k = getchar(); 132 while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar(); 133 return x; 134 } 135 136 int n ,a[MX] ,q ,choose[MX]; 137 bool check(int mid){ 138 for(int i = 1 ; i <= n ; ++i) choose[i] = 0; 139 int iq = q; 140 for(int i = 1 ; i < mid ; ++i) 141 if(a[i] <= iq) choose[i] = 1; 142 for(int i = mid ; i <= n ; ++i){ 143 choose[i] = 1; 144 if(iq == 0) return 0; 145 if(a[i] > iq) --iq; 146 147 } 148 if(iq < 0) return 0; 149 return 1; 150 } 151 152 void solve(){ 153 n = read() ,q = read(); 154 for(int i = 1 ; i <= n ; ++i) 155 a[i] = read(); 156 int l = 1 ,r = n ,mid; 157 while(l <= r){ 158 mid = (l + r) >> 1; 159 if(check(mid)) r = mid - 1; 160 else l = mid + 1; 161 } 162 // [r + 1 ,n] is selected 163 check(r + 1); 164 for(int i = 1 ; i <= n ; ++i) 165 printf("%d" ,choose[i]); 166 puts(""); 167 } 168 169 int main(){ 170 int T = read(); 171 for(int i = 1 ; i <= T ; ++i){ 172 solve(); 173 } 174 return 0; 175 } 176 ``` 177 178 **Code of solution 2** 179 180 By [waaitg](/profile/waaitg "Мастер waaitg") 181 182 ``` 183 #include<cstdio> 184 int a[100005],b[100005]; 185 int main(){ 186 int T; 187 scanf("%d",&T); 188 while(T--){ 189 int n,iq; 190 scanf("%d%d",&n,&iq); 191 for(int i=1;i<=n;++i) 192 scanf("%d",&a[i]); 193 int sum=0,nq=0; 194 for(int i=n;i>=1;--i){ 195 if(a[i]<=nq)b[i]=1; 196 else if(nq<iq)++nq,b[i]=1; 197 else b[i]=0; 198 } 199 for(int i=1;i<=n;++i) 200 printf("%d",b[i]); 201 puts(""); 202 } 203 return 0; 204 } 205 ``` 206 207 [1707B - Разностный массив](/contest/1707/problem/B "Codeforces Round 808 (Div. 1)") 208 209 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg") 210 211 Unfortunately, a harder version of this problem has appeared in a codechef contest [here](https://www.codechef.com/START33B/problems/ARRAY_OPS). 212 213 In fact, this problem was come up with more than 1 year ago, earlier than the problem in that codechef contest. We are sorry again. 214 215 **Solution** 216 217 Tutorial is loading... 218 219 **Code** 220 221 By [waaitg](/profile/waaitg "Мастер waaitg") 222 223 ``` 224 #include<cstdio> 225 #include<cstring> 226 #include<iostream> 227 #include<algorithm> 228 #define ch() getchar() 229 #define pc(x) putchar(x) 230 using namespace std; 231 template<typename T>void read(T&x){ 232 static char c;static int f; 233 for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f; 234 for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f; 235 } 236 template<typename T>void write(T x){ 237 static char q[65];int cnt=0; 238 if(x<0)pc('-'),x=-x; 239 q[++cnt]=x%10,x/=10; 240 while(x) 241 q[++cnt]=x%10,x/=10; 242 while(cnt)pc(q[cnt--]+'0'); 243 } 244 const int maxn=100005; 245 int a[maxn]; 246 int main(){ 247 int T;read(T); 248 while(T--){ 249 int n;read(n); 250 for(int i=1;i<=n;++i)read(a[i]); 251 for(int i=n-1;i>=1;--i){ 252 int pre=a[i+1],ok=false; 253 for(int j=i;j>=1;--j){ 254 ok=(a[j]==0); 255 pre-=(a[j]=pre-a[j]); 256 if(ok){ 257 sort(a+j,a+i+1); 258 break; 259 } 260 } 261 if(!ok) 262 sort(a+1,a+i+1); 263 } 264 write(a[1]),pc('\n'); 265 } 266 return 0; 267 } 268 /* 269 _|_|_|_| _|_| _| _| _|_|_|_|_| _|_|_|_|_| _| 270 _| _| _| _| _|_| _| _| _| _| 271 _| _| _| _| _| _| _| _| _| _| 272 _| _| _|_|_|_|_| _| _| _| _| _|_|_|_|_| _| 273 _| _| _| _| _| _| _| _| _| _| 274 _| _| _| _| _| _|_| _| _| _| 275 _|_|_|_| _| _| _| _| _|_|_|_|_| _|_|_|_|_| _|_|_|_|_| 276 277 _|_|_|_|_| _| _| _|_|_|_| _| _| 278 _| _| _| _| _| _| _| 279 _| _| _| _| _| _| _| 280 _| _|_| _| _| _|_| 281 _| _| _| _| _| _| 282 _| _| _| _| _| _| 283 _| _| _| _|_|_|_| _| 284 285 _| _|_|_| _| _| _|_|_|_|_| 286 _| _| _| _| _| _| 287 _| _| _| _| _| _| 288 _| _| _| _| _| _|_|_|_|_| 289 _| _| _| _| _| _| 290 _| _| _| _|_| _| 291 _|_|_|_|_| _|_|_| _| _|_|_|_|_| 292 293 _|_|_|_|_| _| _| _|_|_|_|_| 294 _| _| _| _| 295 _| _| _| _| 296 _| _|_| _| 297 _| _| _| 298 _| _| _| 299 _| _| _| 300 301 Created by xiaolilsq. 302 */ 303 ``` 304 305 [1707C - Деревья поиска в глубину](/contest/1707/problem/C "Codeforces Round 808 (Div. 1)") 306 307 idea: [waaitg](/profile/waaitg "Мастер waaitg") 308 309 **Solution** 310 311 Tutorial is loading... 312 313 **Code** 314 315 By [waaitg](/profile/waaitg "Мастер waaitg") 316 317 ``` 318 #include<cstdio> 319 #include<cstring> 320 #include<iostream> 321 #include<algorithm> 322 #define ch() getchar() 323 #define pc(x) putchar(x) 324 using namespace std; 325 template<typename T>void read(T&x){ 326 static char c;static int f; 327 for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f; 328 for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f; 329 } 330 template<typename T>void write(T x){ 331 static char q[65];int cnt=0; 332 if(x<0)pc('-'),x=-x; 333 q[++cnt]=x%10,x/=10; 334 while(x) 335 q[++cnt]=x%10,x/=10; 336 while(cnt)pc(q[cnt--]+'0'); 337 } 338 const int maxn=100005,maxm=200005; 339 int par[maxn]; 340 int AC(int x){ 341 return par[x]==x?x:par[x]=AC(par[x]); 342 } 343 struct Edge{ 344 int v,nt; 345 Edge(int v=0,int nt=0): 346 v(v),nt(nt){} 347 }e[maxn*2],es[maxm]; 348 int hd[maxn],num; 349 void qwq(int u,int v){ 350 e[++num]=Edge(v,hd[u]),hd[u]=num; 351 } 352 int dp[maxn]; 353 int pa[maxn][20]; 354 void dfs(int u,int p){ 355 pa[u][0]=p; 356 for(int j=1;(1<<j)<=dp[u];++j) 357 pa[u][j]=pa[pa[u][j-1]][j-1]; 358 for(int i=hd[u];i;i=e[i].nt){ 359 int v=e[i].v; 360 if(v==p)continue; 361 dp[v]=dp[u]+1;dfs(v,u); 362 } 363 } 364 int jump(int x,int t){ 365 for(int cn=0;t;t>>=1,++cn) 366 if(t&1)x=pa[x][cn]; 367 return x; 368 } 369 int lca(int x,int y){ 370 if(dp[x]>dp[y])x=jump(x,dp[x]-dp[y]); 371 if(dp[y]>dp[x])y=jump(y,dp[y]-dp[x]); 372 if(x==y)return x; 373 for(int t=19;t>=0;--t) 374 if(pa[x][t]!=pa[y][t]) 375 x=pa[x][t],y=pa[y][t]; 376 return pa[x][0]; 377 } 378 int vis[maxn]; 379 char s[maxn]; 380 void pushdown(int u,int p){ 381 if(vis[u]==0)s[u]='1'; 382 else s[u]='0'; 383 for(int i=hd[u];i;i=e[i].nt){ 384 int v=e[i].v; 385 if(v==p)continue; 386 vis[v]+=vis[u]; 387 pushdown(v,u); 388 } 389 } 390 int main(){ 391 int n,m; 392 read(n),read(m); 393 for(int i=1;i<=n;++i) 394 par[i]=i; 395 int tp=0; 396 for(int i=1;i<=m;++i){ 397 int u,v; 398 read(u),read(v); 399 if(AC(u)==AC(v)){ 400 es[++tp]=Edge(u,v); 401 } 402 else{ 403 par[AC(u)]=AC(v); 404 qwq(u,v),qwq(v,u); 405 } 406 } 407 int root=1; 408 dfs(root,0); 409 for(int i=1;i<=tp;++i){ 410 int u=es[i].v,v=es[i].nt; 411 if(dp[u]>dp[v])u^=v^=u^=v; 412 int w=lca(u,v); 413 if(u==w){ 414 --vis[v]; 415 ++vis[jump(v,dp[v]-dp[u]-1)]; 416 } 417 else{ 418 ++vis[root]; 419 --vis[u]; 420 --vis[v]; 421 } 422 } 423 pushdown(root,0); 424 s[n+1]='\0'; 425 printf("%s\n",s+1); 426 return 0; 427 } 428 ``` 429 430 [1707D - Частичные виртуальные деревья](/contest/1707/problem/D "Codeforces Round 808 (Div. 1)") 431 432 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg") 433 434 **Solution** 435 436 Tutorial is loading... 437 438 **Code** 439 440 By [Imakf](/profile/Imakf "Мастер Imakf") 441 442 ``` 443 #include <bits/stdc++.h> 444 445 #define debug(...) fprintf(stderr ,__VA_ARGS__) 446 #define __FILE(x)\ 447 freopen(#x".in" ,"r" ,stdin);\ 448 freopen(#x".out" ,"w" ,stdout) 449 #define LL long long 450 451 const int MX = 2000 + 23; 452 453 LL MOD; 454 455 using namespace std; 456 457 int read(){ 458 char k = getchar(); int x = 0; 459 while(k < '0' || k > '9') k = getchar(); 460 while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar(); 461 return x; 462 } 463 464 int head[MX] ,tot = 1; 465 struct edge{ 466 int node ,next; 467 }h[MX << 1]; 468 void addedge(int u ,int v ,int flg = 1){ 469 // if(flg) debug("%d %d\n" ,u ,v); 470 h[++tot] = (edge){v ,head[u]} ,head[u] = tot; 471 if(flg) addedge(v ,u ,false); 472 } 473 474 int n ,dp[MX][MX] ,S[MX][MX] ,suf[MX][MX] ,pre[MX][MX]; 475 void dapai(int x ,int f){ 476 int ch = 0; 477 for(int i = head[x] ,d ; i ; i = h[i].next){ 478 if((d = h[i].node) == f) continue; 479 dapai(d ,x); 480 } 481 for(int i = head[x] ,d ; i ; i = h[i].next){ 482 if((d = h[i].node) == f) continue; 483 ++ch; 484 for(int j = 0 ; j <= n ; ++j){ 485 suf[ch][j] = pre[ch][j] = S[d][j]; 486 } 487 } 488 489 if(!ch){ 490 for(int i = 1 ; i <= n ; ++i){ 491 dp[x][i] = 1 % MOD; 492 S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD; 493 } 494 return ; 495 } 496 for(int j = 0 ; j <= n ; ++j){ 497 for(int i = 1 ; i <= ch ; ++i) 498 pre[i][j] = 1LL * pre[i][j] * pre[i - 1][j] % MOD; 499 for(int i = ch ; i >= 1 ; --i) 500 suf[i][j] = 1LL * suf[i][j] * suf[i + 1][j] % MOD; 501 } 502 for(int i = 1 ; i <= n ; ++i) dp[x][i] = pre[ch][i]; 503 if(x != 1) for(int i = head[x] ,d ,c = 0 ; i ; i = h[i].next){ 504 if((d = h[i].node) == f) continue; 505 ++c; 506 LL sum = 0; 507 for(int mx = 1 ; mx <= n ; ++mx){ 508 dp[x][mx] = (dp[x][mx] + sum * dp[d][mx]) % MOD; 509 sum = (sum + 1LL * pre[c - 1][mx] * suf[c + 1][mx]) % MOD; 510 } 511 } 512 for(int i = 1 ; i <= ch ; ++i) 513 for(int j = 0 ; j <= n ; ++j) 514 suf[i][j] = pre[i][j] = 1 % MOD; 515 for(int i = 1 ; i <= n ; ++i) 516 S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD; 517 } 518 519 int C[MX][MX]; 520 void init(){ 521 for(int i = 0 ; i < MX ; ++i) C[i][0] = 1 % MOD; 522 for(int i = 1 ; i < MX ; ++i) 523 for(int j = 1 ; j < MX ; ++j) 524 C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; 525 } 526 527 int main(){ 528 529 n = read() ,MOD = read(); 530 init(); 531 532 for(int i = 0 ; i < MX ; ++i) 533 for(int j = 0 ; j < MX ; ++j) 534 suf[i][j] = pre[i][j] = 1 % MOD; 535 536 537 538 for(int i = 2 ; i <= n ; ++i){ 539 addedge(read() ,read()); 540 // addedge(rand() % (i - 1) + 1 ,i); 541 } 542 543 dapai(1 ,0); 544 545 for(int i = 1 ; i < n ; ++i){ 546 LL ans = 0; 547 for(int j = 1 ; j <= i ; ++j){ 548 ans += ((i - j) & 1 ? -1LL : 1LL) * C[i][j] * dp[1][j] % MOD; 549 } 550 ans = (ans % MOD + MOD) % MOD; 551 printf("%lld%c" ,ans ," \n"[i == n]); 552 } 553 return 0; 554 } 555 ``` 556 557 [1707E - Замена](/contest/1707/problem/E "Codeforces Round 808 (Div. 1)") 558 559 idea: [Wolam](/profile/Wolam "Кандидат в мастера Wolam"), [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg") 560 561 **Solution** 562 563 Tutorial is loading... 564 565 **Code** 566 567 By [waaitg](/profile/waaitg "Мастер waaitg") 568 569 ``` 570 #include<cstdio> 571 #include<cstring> 572 #include<iostream> 573 #include<algorithm> 574 #define ch() getchar() 575 #define pc(x) putchar(x) 576 using namespace std; 577 template<typename T>void read(T&x){ 578 static char c;static int f; 579 for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f; 580 for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f; 581 } 582 template<typename T>void write(T x){ 583 static char q[64];int cnt=0; 584 if(x==0)return pc('0'),void(); 585 if(x<0)pc('-'),x=-x; 586 while(x)q[cnt++]=x%10+'0',x/=10; 587 while(cnt--)pc(q[cnt]); 588 } 589 const int maxn=100005,maxq=100005,maxt=34; 590 const int inf=0x3f3f3f3f; 591 int a[maxn]; 592 struct Segment{ 593 int l,r; 594 Segment(int l=inf,int r=-inf): 595 l(l),r(r){} 596 Segment operator * (const Segment o)const{ 597 return Segment(min(l,o.l),max(r,o.r)); 598 } 599 bool operator != (const Segment o)const{ 600 return l!=o.l||r!=o.r; 601 } 602 void input(void){ 603 read(l),read(r); 604 } 605 }sg[maxt][maxn],tr[maxn],qy[maxq]; 606 int n; 607 void res(void){ 608 for(int i=1;i<n;++i) 609 tr[i]=Segment(); 610 } 611 void add(int p,Segment v){ 612 while(p<n){ 613 tr[p]=tr[p]*v; 614 p+=(p&(-p)); 615 } 616 } 617 Segment ask(int p){ 618 Segment re; 619 while(p){ 620 re=re*tr[p]; 621 p^=(p&(-p)); 622 } 623 return re; 624 } 625 struct Edge{ 626 int v,w,nt; 627 Edge(int v=0,int w=0,int nt=0): 628 v(v),w(w),nt(nt){} 629 }e[maxn]; 630 int num,hd[maxn]; 631 void ins(int u,int v,int w){ 632 e[++num]=Edge(v,w,hd[u]),hd[u]=num; 633 } 634 int st[maxq],tp; 635 long long Ans[maxq]; 636 int main(){ 637 int q;read(n),read(q); 638 if(n==1){while(q--)puts("0");return 0;} 639 for(int i=1;i<=n;++i)read(a[i]); 640 for(int i=1;i<n;++i){ 641 if(a[i]<=a[i+1]) 642 sg[0][i]=Segment(a[i],a[i+1]); 643 else 644 sg[0][i]=Segment(a[i+1],a[i]); 645 } 646 for(int i=1;i<maxt;++i){ 647 for(int j=1;j<n;++j){ 648 if(sg[i-1][j].l>=sg[i-1][j].r)sg[i][j]=Segment(); 649 else ins(sg[i-1][j].l,sg[i-1][j].r-1,j); 650 } 651 res(); 652 for(int j=n-1;j>=1;--j){ 653 add(j,sg[i-1][j]); 654 for(int k=hd[j];k;k=e[k].nt){ 655 sg[i][e[k].w]=ask(e[k].v); 656 } 657 hd[j]=0; 658 } 659 num=0; 660 } 661 for(int i=1;i<=q;++i){ 662 qy[i].input(); 663 if(qy[i].l==qy[i].r)Ans[i]=-2; 664 else ins(qy[i].l,qy[i].r-1,i); 665 } 666 res(); 667 for(int i=n-1;i>=1;--i){ 668 add(i,sg[maxt-1][i]); 669 for(int j=hd[i];j;j=e[j].nt){ 670 if(i==1&&e[j].v==n-1) 671 Ans[e[j].w]=-1; 672 else if(ask(e[j].v)!=Segment(1,n)) 673 Ans[e[j].w]=-2; 674 else 675 st[++tp]=e[j].w; 676 } 677 hd[i]=0; 678 } 679 num=0; 680 for(int i=maxt-2;~i;--i){ 681 for(int j=1;j<=tp;++j){ 682 ins(qy[st[j]].l,qy[st[j]].r-1,st[j]); 683 } 684 res(); 685 for(int j=n-1;j>=1;--j){ 686 add(j,sg[i][j]); 687 for(int k=hd[j];k;k=e[k].nt){ 688 Segment tmp=ask(e[k].v); 689 int id=e[k].w; 690 if(tmp!=Segment(1,n)) 691 Ans[id]|=(1ll<<i),qy[id]=tmp; 692 } 693 hd[j]=0; 694 } 695 num=0; 696 } 697 for(int i=1;i<=q;++i) 698 write(++Ans[i]),pc('\n'); 699 return 0; 700 } 701 ``` 702 703 [1707F - Бугабу](/contest/1707/problem/F "Codeforces Round 808 (Div. 1)") 704 705 This is a noun almost one year ago when this problem came out. 706 707 idea: [Imakf](/profile/Imakf "Мастер Imakf") and [waaitg](/profile/waaitg "Мастер waaitg") 708 709 **Solution** 710 711 Tutorial is loading... 712 713 **Code** 714 715 By [waaitg](/profile/waaitg "Мастер waaitg") 716 717 ``` 718 #include<cstdio> 719 #include<cstring> 720 #include<iostream> 721 #include<algorithm> 722 #include<assert.h> 723 #define ch() getchar() 724 #define pc(x) putchar(x) 725 template<typename T>void read(T&x){ 726 static char c;static int f; 727 for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f; 728 for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f; 729 } 730 template<typename T>void write(T x){ 731 static char q[65];int cnt=0; 732 if(x<0)pc('-'),x=-x; 733 q[++cnt]=x%10,x/=10; 734 while(x) 735 q[++cnt]=x%10,x/=10; 736 while(cnt)pc(q[cnt--]+'0'); 737 } 738 const int maxn=20000005; 739 struct Count{ 740 int pos,val; 741 Count(int pos=-1,int val=-1): 742 pos(pos),val(val){} 743 }; 744 int plus(int x,int y){ 745 return (x<0||y<0)?-1:x+y; 746 } 747 Count operator + (const Count A,const Count B){ 748 int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val); 749 if(~Ap&&~Bp)return Ap^Bp?Count():Count(Ap|Bp,va); 750 if(~Ap||~Bp)return Count(Ap&Bp,va); 751 return Count(-1,va); 752 } 753 Count operator * (const Count A,const Count B){ 754 int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val); 755 if(~Ap&&~Bp)return Count(Ap^Bp,va); 756 if(~Ap||~Bp)return Count(-1,va); 757 return Count(-1,plus(va,1)); 758 } 759 int c[maxn]; 760 int tn,Op[maxn],Cn[maxn]; 761 Count dp[maxn]; 762 int t,hb[maxn],rev[maxn]; 763 void pushup(int p){ 764 int l=p<<1,r=l|1; 765 dp[p]=((t&hb[p])?(dp[l]+dp[r]):(dp[l]*dp[r])); 766 } 767 int va1,sum; 768 void ins(int i){ 769 int p=rev[(i&(tn-1))]; 770 if(~c[i])Op[p]^=c[i];else ++Cn[p]; 771 if(dp[p+tn].pos>0)--va1;else sum-=dp[p+tn].val; 772 dp[p+tn]=(Cn[p]?Count(-1,Cn[p]-1):Count(Op[p],0)); 773 if(dp[p+tn].pos>0)++va1;else sum+=dp[p+tn].val; 774 } 775 void del(int i){ 776 int p=rev[(i&(tn-1))]; 777 if(~c[i])Op[p]^=c[i];else --Cn[p]; 778 } 779 int power(int a,int x,int p){ 780 if(x==-1)return 0; 781 int re=1; 782 while(x){ 783 if(x&1)re=1ll*re*a%p; 784 a=1ll*a*a%p;x>>=1; 785 } 786 return re; 787 } 788 int main(){ 789 int n,m,w; 790 read(n),read(m),read(t),read(w); 791 memset(c,-1,sizeof c); 792 for(int i=1;i<=m;++i){ 793 int d;read(d);--d;read(c[d]); 794 } 795 tn=(n&(-n)); 796 hb[0]=0;hb[1]=1; 797 for(int i=2;i<tn*2;++i) 798 hb[i]=(hb[i>>1]<<1); 799 int cn=-1;for(;(1<<(cn+1))<tn;++cn); 800 for(int i=1;i<tn;++i) 801 rev[i]=(rev[i>>1]>>1)|((i&1)<<cn); 802 for(int i=0;i<tn;++i)dp[i+tn].val=0; 803 for(int i=0;i<n;++i)ins(i); 804 if(t<tn)for(int i=tn-1;i>=1;--i)pushup(i); 805 int q;read(q); 806 while(q--){ 807 int f;read(f);--f; 808 del(f);read(c[f]);ins(f); 809 int p;read(p); 810 if(t>=tn){ 811 write(va1?0:power((1<<w)%p,sum,p)); 812 } 813 else{ 814 int now=(rev[(f&(tn-1))]|tn);while(now>>=1)pushup(now); 815 write(power((1<<w)%p,plus(dp[1].val,dp[1].pos==-1),p)); 816 } 817 pc('\n'); 818 } 819 return 0; 820 } 821 ```