2006.md (35929B)
1 Source: https://codeforces.com/blog/entry/133382 2 3 [2007A - Dora's Set](/contest/2007/problem/A "Codeforces Round 969 (Div. 2)") 4 5 **Hint 1** 6 7 How many odd integers are there in a pair $(a, b, c)$? 8 9 **Answer** 10 11 At least 2. 12 13 **Hint 2** 14 15 It's always better to put **exactly $2$** odd integers and **exactly $1$** even integer in one pair of $(a, b, c)$. Is there a way to always choose optimal $(a, b, c)$? 16 17 **Hint 3** 18 19 Try consecutive integers. 20 21 **Tutorial** 22 23 Tutorial is loading... 24 25 **Implementation** 26 27 ``` 28 T = int(input()) 29 30 for _ in range(T) : 31 l, r = map(int, input().split()) 32 print(((r + 1) // 2 - l // 2) // 2) 33 ``` 34 35 [2007B - Index and Maximum Value](/contest/2007/problem/B "Codeforces Round 969 (Div. 2)") 36 37 **Hint** 38 39 Consider the position of the maximum value in one array. If there's multiple maximum values, choose any. What can you observe? 40 41 **Answer** 42 43 The position of the maximum value never changes. That is, if one element is the maximum value in the beginning, it will always be. 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Implementation** 50 51 ``` 52 T = int(input()) 53 54 for _ in range(T) : 55 n, m = map(int, input().split()) 56 v = max(map(int, input().split())) 57 for __ in range(m) : 58 c, l, r = input().split() 59 l = int(l) 60 r = int(r) 61 if (l <= v <= r) : 62 if (c == '+') : 63 v = v + 1 64 else : 65 v = v - 1 66 print(v, end = ' ' if __ != m - 1 else '\n') 67 ``` 68 69 [2007C - Dora and C++](/contest/2007/problem/C "Codeforces Round 969 (Div. 2)") 70 71 **Hint1** 72 73 If you can perform an operation that decreases $a$ or $b$ from an element, will it be different? 74 75 **Answer** 76 77 No. Decrease an element by $a$ is the same as increasing all other elements by $a$, as it does not affect the range. 78 79 **Hint2** 80 81 If $a = b$, can you solve the problem? 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Implementation** 88 89 ``` 90 import math 91 92 T = int(input()) 93 for _ in range(T) : 94 n, a, b = map(int, input().split()) 95 d = math.gcd(a, b) 96 a = list(map(int, input().split())) 97 a = [x % d for x in a] 98 a.sort() 99 res = a[n - 1] - a[0] 100 for i in range(1, n) : 101 res = min(res, a[i - 1] + d - a[i]) 102 print(res) 103 ``` 104 105 [2006A - Iris and Game on the Tree](/contest/2006/problem/A "Codeforces Round 969 (Div. 1)") 106 107 **Hint1** 108 109 How to calulate the weight of a leaf quickly? 110 111 **Hint2** 112 113 Consider a formed string. Let's delete useless part that won't contribute to the count of $\tt{01}$ and $\tt{10}$ substrings. What will be the rest? 114 115 **Answer** 116 117 A string with each pair of adjacent bits different. For example, $\tt{110001}\rightarrow\tt{101}$. Then what decides whether the weight is zero or not? 118 119 **Hint3** 120 121 The root is somehow important. When to fill $s_1$? 122 123 **Tutorial** 124 125 Tutorial is loading... 126 127 **Implementation** 128 129 ``` 130 T = int(input()) 131 132 for _ in range(T) : 133 n = int(input()) 134 x, y, z, w = 0, 0, 0, 0 135 deg = [0] * (n + 1) 136 for __ in range(n - 1) : 137 u, v = map(int, input().split()) 138 deg[u] += 1 139 deg[v] += 1 140 s = " " + input() 141 for i in range(2, n + 1) : 142 if deg[i] == 1 : 143 if s[i] == '?' : 144 z += 1 145 elif s[i] == '0' : 146 x += 1 147 else : 148 y += 1 149 elif s[i] == '?' : 150 w += 1 151 if s[1] == '0' : 152 print(y + (z + 1) // 2) 153 elif s[1] == '1' : 154 print(x + (z + 1) // 2) 155 else : 156 print(max(x, y) + (z + (w % 2 if x == y else 0)) // 2) 157 ``` 158 159 [2006B - Iris and the Tree](/contest/2006/problem/B "Codeforces Round 969 (Div. 1)") 160 161 **Titbits** 162 163 The previous statement of the problem did not directly tell you that the vertices are numbered by dfs order. It was changed to make the statement more readable. Can you prove that the following property is the same as telling you the vertices are numbered by dfs order? 164 165 **previous version** 166 167 For any three nodes $i,j,k$ that $1\le i \lt j \lt k\le n$, if $i$ is not an ancestor of $j$, then $i$ won't be an ancestor of $k$. 168 169 **proof** 170 171 Let's still focus on "the vertex numbers in one subtree are consecutive". Suppose it's not consecutive: Let the minimum vertex number be $i$(the root, for $p_i \lt i$), the maximum vertex number be $k$, and one of the lost vertex number be $j$, you can see that $i$ is an ancestor of $k$ but not an ancestor of $j$. So the conslusion is proved. 172 173 **Hint1** 174 175 On a tree with nodes numbered with dfs order, we have to find the distance between two consecutive nodes. What can you think of? 176 177 **Answer** 178 179 Each edge is passed by exactly two of the paths. 180 181 **Hint2** 182 183 How to calculate the maximum value of $\text{dist}(i,(i\bmod n)+1)$? Is it different when the weight of all of its edges are known? 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Implementation** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 namespace FastIO { 195 template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; } 196 template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); } 197 template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); } 198 template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); } 199 }; using namespace FastIO; 200 201 #define MAXN 200001 202 int fa[MAXN], dep[MAXN]; 203 int c1[MAXN], c2[MAXN], len[MAXN]; 204 205 void solve() { 206 int N = read<int>(); long long w = read<long long>(); 207 for (int i = 2; i <= N; ++i) fa[i] = read<int>(); 208 for (int i = 2; i <= N; ++i) dep[i] = dep[fa[i]] + 1; 209 for (int i = 1; i <= N; ++i) len[i] = c1[i] = 0; 210 for (int i = 1, x, y; i <= N; ++i) { 211 x = i, y = (i == N ? 1 : i + 1); 212 while (x != y) { 213 if (dep[x] < dep[y]) std::swap(x, y); 214 (c1[x] ? c2[x] : c1[x]) = i, x = fa[x], ++len[i]; 215 } 216 } 217 long long sum = 0, sur = N; 218 for (int i = 1, x; i < N; ++i) { 219 x = read<int>(), sum += read<long long>(); 220 if ((--len[c1[x]]) == 0) --sur; 221 if ((--len[c2[x]]) == 0) --sur; 222 print<long long>(sum * 2 + sur * (w - sum), " \n"[i == N - 1]); 223 } 224 } 225 226 int main() { int T = read<int>(); while (T--) solve(); return 0; } 227 ``` 228 229 **Bonus** 230 231 Can you solve the problem if the nodes are not numbered by dfs order? 232 233 [2006C - Eri and Expanded Sets](/contest/2006/problem/C "Codeforces Round 969 (Div. 1)") 234 235 **Hint1** 236 237 Let's try to judge whether an array is brilliant, and try to sort it first. What happens if we minus $1$ from each element? 238 239 **Answer** 240 241 Nothing will change. 242 243 **Hint2** 244 245 We only care about the relative positions between the elements. Let's consider the difference array $b$ of array $a$: $b_i=a_i-a_{i-1}(i\ge 2)$. 246 247 **Hint3** 248 249 What will the difference array look like after no more operations can be done? 250 251 **Tutorial** 252 253 Tutorial is loading... 254 255 **Implementation - two pointers** 256 257 ``` 258 #include<bits/stdc++.h> 259 using namespace std; 260 #define int long long 261 #define pii pair<int,int> 262 #define all(v) v.begin(),v.end() 263 #define pb push_back 264 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 265 #define over(x) {cout<<x<<endl;return;} 266 #define cntbit(x) __buitin_popcount(x) 267 int n; 268 int a[400005],lsteq[400005]; 269 struct two_pointers{ 270 int l,r,mid; 271 int val[400005],rt; 272 void init(){ 273 l=r=mid=rt=0; 274 val[0]=a[0]; 275 } 276 inline void addr(){++r;rt=__gcd(rt,a[r]);} 277 inline void addl(){if(l+1>r)addr();++l;if(l>mid){rt=0,mid=r;val[mid]=a[mid]; 278 for(int i=mid-1;i>=l;--i)val[i]=__gcd(val[i+1],a[i]);}} 279 inline int query(){return __gcd(val[l],rt);} 280 }; 281 void Main() { 282 cin>>n; 283 REP(i,0,n)cin>>a[i]; 284 REP(i,1,n)a[n-i]-=a[n-i-1]; 285 REP(i,1,n)a[i-1]=llabs(a[i]); 286 --n; 287 lsteq[n]=n; 288 for(int i=n-1;i>=0;--i)lsteq[i]=(a[i]? i:lsteq[i+1]); 289 two_pointers p;p.init(); 290 int ans=1,cnt=1; 291 REP(i,0,n)if(lsteq[i]==i){ 292 while(p.l<i)p.addl(); 293 while(p.r<n&&cntbit(p.query())>1)p.addr(); 294 ans+=(n-p.r)*cnt+1;cnt=1; 295 }else ans+=lsteq[i]-i+1,++cnt; 296 cout<<ans<<endl; 297 } 298 void TC() { 299 int tc=1; 300 cin>>tc; 301 while(tc--){ 302 Main(); 303 cout.flush(); 304 } 305 } 306 signed main() { 307 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 308 } 309 ``` 310 311 **Implementation - sparse table** 312 313 ``` 314 #include<bits/stdc++.h> 315 using namespace std; 316 #define int long long 317 #define pii pair<int,int> 318 #define all(v) v.begin(),v.end() 319 #define pb push_back 320 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 321 #define over(x) {cout<<x<<endl;return;} 322 #define cntbit(x) __buitin_popcount(x) 323 int n; 324 int a[400005],res[400005],lsteq[400005]; 325 int st[400005][20]; 326 int query(int l,int r){ 327 int s=__lg(r-l+1); 328 return __gcd(st[l][s],st[r-(1<<s)+1][s]); 329 } 330 void Main() { 331 cin>>n; 332 REP(i,0,n)cin>>a[i]; 333 --n; 334 if(!n)over(1) 335 REP(i,0,n)st[i][0]=llabs(a[i]-a[i+1]); 336 REP(j,0,__lg(n)){ 337 REP(i,0,n-(1<<(j+1))+1){ 338 st[i][j+1]=__gcd(st[i][j],st[i+(1<<j)][j]); 339 } 340 } 341 lsteq[n]=n; 342 for(int i=n-1;i>=0;--i)lsteq[i]=(a[i]==a[i+1]? lsteq[i+1]:i); 343 int ans=1; 344 int l=0,r=0; 345 REP(i,0,n){ 346 l=max(l,lsteq[i]);r=max(r,l); 347 while(r<n&&cntbit(query(l,r))>1)++r; 348 ans+=n-r;ans+=lsteq[i]-i+1; 349 } 350 cout<<ans<<endl; 351 } 352 void TC() { 353 int tc=1; 354 cin>>tc; 355 while(tc--){ 356 Main(); 357 cout.flush(); 358 } 359 } 360 signed main() { 361 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 362 } 363 ``` 364 365 **Bonus** 366 367 There's a harder but similar version of the problem. Can you solve it? 368 369 There're $q$ queries: $L,R,k$. Find the number of pairs $(l,r)$ that $L\le l\le r\le R$, and $(\lvert Q({a_l\dots a_r}) \rvert-1) \cdot k\ge \max(a_l\dots a_r) - \min(a_l\dots a_r) $, where $Q(array)$ means the result of putting the array into the set. 370 371 [2006D - Iris and Adjacent Products](/contest/2006/problem/D "Codeforces Round 969 (Div. 1)") 372 373 **Hint1** 374 375 Let's use another way to describe the problem. Let's define an array good, that it can be reordered to satisfy the condition. How many numbers do we have to change to make it good? 376 377 To handle this, we need to know what is the optimal way to reorder an array. 378 379 **Hint2** 380 381 Sort the array. Suppose $a_1$ is the minimum and $a_n$ is the maximum. Where to place the two elements? Can you prove this is optimal? 382 383 **Hint3** 384 385 How to maintain the answer better using the properties? 386 387 **Tutorial** 388 389 Tutorial is loading... 390 391 **Implementation** 392 393 ``` 394 #include<bits/stdc++.h> 395 using namespace std; 396 #define all(v) v.begin(),v.end() 397 #define pb push_back 398 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 399 #define over(x) {cout<<(x)<<endl;return;} 400 int n,q,r; 401 int a[300005]; 402 int sum[300005]; 403 int ql[300005],qr[300005]; 404 int ans[300005]; 405 int cnt[300005],cnt2[300005]; 406 void Main() { 407 cin>>n>>q>>r; 408 REP(i,0,n)cin>>a[i]; 409 sum[0]=0; 410 int B=sqrt(r); 411 REP(i,0,n)sum[i+1]=sum[i]+(a[i]<=B); 412 REP(i,0,q){ 413 int x,y; 414 cin>>x>>y; 415 --x,--y; 416 ql[i]=x;qr[i]=y; 417 ans[i]=0; 418 if(sum[y+1]-sum[x]<(y-x+1)/2)ans[i]=(y-x+1)/2-sum[y+1]+sum[x]; 419 } 420 REP(i,0,B){ 421 REP(j,0,n+1)cnt[j]=cnt2[j]=0; 422 REP(j,0,n){ 423 cnt[j+1]=cnt[j]+(a[j]<=i); 424 cnt2[j+1]=cnt2[j]+(a[j]<=r/(i+1)); 425 } 426 REP(j,0,q){ 427 int x=ql[j],y=qr[j],l=y-x+1; 428 int c1=cnt2[y+1]-cnt2[x],c2=cnt[y+1]-cnt[x]; 429 ans[j]=max(ans[j],min((l-c1-c2+1)/2,l/2-c2)); 430 } 431 } 432 REP(i,0,q)cout<<ans[i]<<' '; 433 cout<<endl; 434 } 435 void TC() { 436 int tc=1; 437 cin>>tc; 438 while(tc--){ 439 Main(); 440 cout.flush(); 441 } 442 } 443 signed main() { 444 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 445 } 446 /* 447 1. CLEAR the arrays (ESPECIALLY multitests) 448 2. DELETE useless output 449 */ 450 ``` 451 452 [2006E - Iris's Full Binary Tree](/contest/2006/problem/E "Codeforces Round 969 (Div. 1)") 453 454 **Hint1** 455 456 Consider the degress of vertices in a binary tree. What can you observe? 457 458 **Answer** 459 460 The root has degree $2$, the non-leaf nodes different from the root have degree $3$, the leaf nodes have degree $1$. The degree of every node is not greater than $3$. 461 462 **Hint2** 463 464 Choose a root. It should have degree $\le 2$. Is it always possible to build a binary tree on the initial tree if all nodes have degree $\le 3$? What will be the depth of the binary tree with the given root? 465 466 **Answer** 467 468 It's always possible to build the binary tree, and the depth of the tree is the maximum distance from the root to any nodes in the tree. 469 470 **Hint3** 471 472 Consider the binary depth of the full tree. We should to go over every possible root, but how to find the maximum distance from the root to other nodes? Are there any special nodes? 473 474 **Hint4** 475 476 Diameter. 477 478 **Hint5** 479 480 Is it possible to maintain the answer for all the roots when adding a leaf to the tree? 481 482 **Tutorial** 483 484 Tutorial is loading... 485 486 **Implementation** 487 488 ``` 489 #include<bits/stdc++.h> 490 using namespace std; 491 #define int long long 492 #define pii pair<int,int> 493 #define all(v) v.begin(),v.end() 494 #define pb push_back 495 #define REP(i,b,e) for(int i=(b);i<(int)(e);++i) 496 #define over(x) {cout<<(x)<<endl;return;} 497 struct ds{ 498 int seg[2000005],tag[2000005]; 499 void build(int l,int r,int p){ 500 seg[p]=(l==0? 0:1e18),tag[p]=0; 501 if(l==r)return; 502 int m=(l+r)>>1; 503 build(l,m,p*2+1);build(m+1,r,p*2+2); 504 } 505 void pushdown(int p){ 506 if(!tag[p])return; 507 tag[p*2+1]+=tag[p];tag[p*2+2]+=tag[p]; 508 seg[p*2+1]+=tag[p];seg[p*2+2]+=tag[p]; 509 tag[p]=0; 510 } 511 void add(int l,int r,int s,int t,int p,int val){ 512 if(l<=s&&t<=r){ 513 seg[p]+=val;tag[p]+=val; 514 return; 515 } 516 int m=(s+t)>>1;pushdown(p); 517 if(m>=l)add(l,r,s,m,p*2+1,val); 518 if(m<r)add(l,r,m+1,t,p*2+2,val); 519 seg[p]=min(seg[p*2+1],seg[p*2+2]); 520 } 521 void update(int pos,int l,int r,int p,int val){ 522 if(l==r){ 523 seg[p]=val; 524 return; 525 } 526 int m=(l+r)>>1;pushdown(p); 527 if(m>=pos)update(pos,l,m,p*2+1,val); 528 else update(pos,m+1,r,p*2+2,val); 529 seg[p]=min(seg[p*2+1],seg[p*2+2]); 530 } 531 }seg; 532 int n; 533 vector<int>v[500005]; 534 int fa[500005],an[500005][21]; 535 int dep[500005],dfn[500005],rev[500005]; 536 int tot,deg[500005],ls[500005]; 537 void dfs(int x,int pre,int d){ 538 dep[x]=d;fa[x]=pre;an[x][0]=fa[x];ls[x]=1; 539 REP(i,0,__lg(n+1))if(an[x][i]==-1)an[x][i+1]=-1;else an[x][i+1]=an[an[x][i]][i]; 540 rev[tot]=x;dfn[x]=tot++; 541 for(auto i:v[x])dfs(i,x,d+1),ls[x]+=ls[i]; 542 } 543 int getlca(int x,int y){ 544 if(dep[x]<dep[y])swap(x,y); 545 int d=dep[x]-dep[y]; 546 for(int i=__lg(d);i>=0;--i)if((d>>i)&1)x=an[x][i]; 547 if(x==y)return x; 548 d=dep[x]; 549 for(int i=__lg(d);i>=0;--i)if((1<<i)<=dep[x]&&an[x][i]!=an[y][i])x=an[x][i],y=an[y][i]; 550 return fa[x]; 551 } 552 int getan(int x,int y){ 553 if(dfn[y]>=dfn[x]&&dfn[y]<=ls[x]){ 554 int d=dep[y]-dep[x]-1; 555 for(int i=0;(1<<i)<=d;++i)if((d>>i)&1)y=an[y][i]; 556 return y; 557 }else return fa[x]; 558 } 559 void updside(int x,int y){ 560 if(dfn[y]>=dfn[x]&&dfn[y]<=ls[x]){ 561 seg.add(0,n-1,0,n-1,0,1); 562 x=getan(x,y); 563 seg.add(dfn[x],ls[x],0,n-1,0,-1); 564 }else seg.add(dfn[x],ls[x],0,n-1,0,1); 565 } 566 int getdist(int x,int y){return dep[x]+dep[y]-2*dep[getlca(x,y)];} 567 struct diameter{ 568 int x,y,len; 569 int update(int z){ 570 if(x==y){ 571 int d=getdist(x,z); 572 if(d<=len)return d+len; 573 updside(y,z); 574 y=getan(y,z); 575 return d+len; 576 }else{ 577 int d1=getdist(x,z),d2=getdist(y,z),d3=min(d1,d2); 578 if(d3<=len)return d3+len+1; 579 if(d1>d2)swap(x,y); 580 updside(y,z); 581 y=x;++len;return len*2; 582 } 583 } 584 int query(int z){ 585 if(x==y)return len+getdist(x,z); 586 else return len+min(getdist(x,z),getdist(y,z))+1; 587 } 588 }; 589 void Main() { 590 cin>>n; 591 REP(i,0,n)v[i].clear(); 592 REP(i,1,n){ 593 cin>>fa[i];--fa[i]; 594 v[fa[i]].pb(i); 595 } 596 tot=0;dfs(0,-1,0);seg.build(0,n-1,0); 597 REP(i,0,n)deg[i]=0,ls[i]+=dfn[i]-1; 598 diameter d={0,0,0}; 599 cout<<"1 "; 600 REP(i,1,n){ 601 ++deg[fa[i]];++deg[i]; 602 if(deg[fa[i]]==4){ 603 REP(j,i,n)cout<<-1<<' '; 604 cout<<endl;return; 605 } 606 if(deg[fa[i]]==3)seg.update(dfn[fa[i]],0,n-1,0,1e18); 607 seg.update(dfn[i],0,n-1,0,d.update(i)); 608 cout<<seg.seg[0]+1<<' '; 609 } 610 cout<<endl; 611 } 612 void TC() { 613 int tc=1; 614 cin>>tc; 615 while(tc--){ 616 Main(); 617 cout.flush(); 618 } 619 } 620 signed main() { 621 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 622 } 623 /* 624 1. CLEAR the arrays (ESPECIALLY multitests) 625 2. DELETE useless output 626 */ 627 ``` 628 629 [2006F - Dora's Paint](/contest/2006/problem/F "Codeforces Round 969 (Div. 1)") 630 631 Here're two methods. Method $1$ is my method, and method $2$ is some testers' method. 632 633 Method 1: 634 635 **Hint1** 636 637 Each column or row should be painted at most once. Suppose we paint each column and row exactly once. Then what does the number on one position tell us? 638 639 **Answer** 640 641 It tells us whether the row was painted first of the column was painted first. Try to build a graph. 642 643 **Hint2** 644 645 We can build a directed bipartite graph. How to judge whether it is possible to paint the graph? How to calculate the beauty of one single grid? 646 647 **Answer** 648 649 Do topological sort on the graph. A cycle means it is impossible. Otherwise, the topo sort splits the graph into several layers. The beauty is the product of factorials of number of nodes in the layers (except the first layer, for we needn't do those operations). 650 651 **Hint3** 652 653 How to solve the original problem when the initial grid has positive beauty? How to optimize? Consider adjacent layers. 654 655 **Hint4** 656 657 How to solve the original problem when the initial grid is impossible to be painted out? Are there too many ways to flip a block? 658 659 **Hint5** 660 661 How to optimize the process of building the graph and doing topological sort? 662 663 **Tutorial** 664 665 Tutorial is loading... 666 667 **Implementation - method 1** 668 669 ``` 670 #include<bits/stdc++.h> 671 using namespace std; 672 #define MOD 998244353 673 #define speMOD 2933256077ll 674 #define int long long 675 #define pii pair<int,int> 676 #define all(v) v.begin(),v.end() 677 #define pb push_back 678 #define REP(i,b,e) for(int i=(b);i<(e);++i) 679 #define over(x) {cout<<x<<endl;return;} 680 #define lowbit(x) ((x)&(-(x))) 681 #define cntbit(x) __builtin_popcount(x) 682 #define rf(v) shuffle(all(v),sd); 683 mt19937 sd(std::random_device{}()); 684 int qpow (int a,int b,int m=MOD,int res=1){ 685 a%=m; 686 while(b>0)res=(b&1)?(res*a%m):(res),a=a*a%m,b>>=1; 687 return res; 688 } 689 int fac[2000005],inv[2000005],si[2000005]; 690 void init(int n){ 691 fac[0]=inv[0]=si[0]=1; 692 REP(i,1,n+1)fac[i]=fac[i-1]*i%MOD; 693 inv[n]=qpow(fac[n],MOD-2); 694 for(int i=n-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%MOD; 695 REP(i,1,n+1)si[i]=inv[i]*fac[i-1]%MOD; 696 } 697 int binom(int x,int y){ 698 return x<y||y<0? 0:fac[x]*inv[y]%MOD*inv[x-y]%MOD; 699 } 700 namespace fastIO { 701 #define BUF_SIZE 6000010 702 bool IOerror = 0; 703 inline char nc() { 704 static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE; 705 if(p1 == pend) { 706 p1 = buf; 707 pend = buf + fread(buf, 1, BUF_SIZE, stdin); 708 if(pend == p1) { 709 IOerror = 1; 710 return -1; 711 } 712 } 713 return *p1++; 714 } 715 inline bool blank(char ch) { 716 return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; 717 } 718 inline void read(int &x) { 719 char ch; 720 while(blank(ch = nc())); 721 if(IOerror) 722 return; 723 for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0'); 724 } 725 #undef BUF_SIZE 726 }; 727 using namespace fastIO; 728 int n,m; 729 int a[200005],b[200005]; 730 vector<pii>c; 731 int d1[200005],d2[200005]; 732 int visa[200005],visb[200005]; 733 vector<int>h[200005],nodes[200005],buc[200005]; 734 int X,Y; 735 int id1[200005],id2[200005],cnt[400005]; 736 int solve(){ 737 REP(i,0,n+1)buc[i].clear(); 738 REP(i,0,n)buc[a[i]].pb(i); 739 int num=0; 740 REP(i,0,n+1)for(auto j:buc[i])id1[num++]=j; 741 REP(i,0,n+1)buc[i].clear(); 742 REP(i,0,n)buc[b[i]].pb(i); 743 num=0; 744 REP(i,0,n+1)for(auto j:buc[i])id2[num++]=j; 745 REP(i,0,n)d1[i]=d2[i]=-1; 746 int ans=1,x=0,y=0,cur=0; 747 while(x<n||y<n){ 748 if(x<n&&a[id1[x]]<=y){ 749 int sum=0; 750 while(x<n&&a[id1[x]]<=y)++sum,d1[id1[x++]]=cur; 751 if(cur)(ans*=fac[sum])%=MOD; 752 }else if(y<n&&b[id2[y]]<=x){ 753 int sum=0; 754 while(y<n&&b[id2[y]]<=x)++sum,d2[id2[y++]]=cur; 755 if(cur)(ans*=fac[sum])%=MOD; 756 }else return X=x,Y=y,0; 757 ++cur; 758 } 759 return ans; 760 } 761 int updater(int x,int y){ 762 int f=0,ret; 763 for(auto i:c)if(i==make_pair(x,y))f=1; 764 if(f)--b[y],++a[x],ret=solve(),++b[y],--a[x]; 765 else ++b[y],--a[x],ret=solve(),--b[y],++a[x]; 766 return ret; 767 } 768 void Main() { 769 fastIO::read(n);fastIO::read(m); 770 c.clear(); 771 REP(i,0,n)a[i]=b[i]=0; 772 REP(i,0,n*2+2)cnt[i]=0; 773 REP(i,0,n)visa[i]=visb[i]=0,h[i].clear(),nodes[i].clear(); 774 REP(i,0,m){ 775 int x,y; 776 fastIO::read(x);fastIO::read(y); 777 --x,--y; 778 c.pb({x,y}); 779 ++b[y];--a[x]; 780 } 781 REP(i,0,n)a[i]+=n; 782 int ans=solve(); 783 if(!ans){ 784 if(X==n-1||Y==n-1)over(0) 785 int x=id1[X],y=id2[Y],f=0; 786 for(auto i:c)if(i==make_pair(x,y)){f=1;break;} 787 if(f){ 788 for(auto i:c)if(i.first==x)visb[i.second]=1; 789 for(auto i:c)if(i.second==y)visa[i.first]=1; 790 X=Y=-1; 791 for(auto i:c)if(i.first!=x&&i.second!=y){ 792 if(!visa[i.first]&&!visb[i.second]){X=i.first,Y=i.second;break;} 793 } 794 if(X==-1)over(0); 795 }else{ 796 X=Y=-1; 797 for(auto i:c)h[i.first].pb(i.second); 798 int sum=0; 799 for(auto i:h[x])visa[i]=1,++sum; 800 REP(i,0,n){ 801 int found=0; 802 for(auto j:h[i])if(j==y){found=1;break;} 803 if(!found)continue; 804 vector<int>z; 805 for(auto j:h[i])if(visa[j])visa[j]=0,--sum,z.pb(j); 806 if(sum){ 807 X=i; 808 REP(j,0,n)if(visa[j])Y=j; 809 break; 810 } 811 for(auto j:z)++sum,visa[j]=1; 812 } 813 if(X==-1)over(0); 814 } 815 int x2=X,y2=Y; 816 int ans=updater(x,y)+updater(x,y2)+updater(x2,y)+updater(x2,y2); 817 cout<<(ans%MOD*qpow(n*n%MOD,MOD-2))%MOD<<endl; 818 return; 819 } 820 REP(i,0,n)++cnt[d1[i]],++cnt[d2[i]]; 821 int res=0; 822 (res+=ans*cnt[0]%MOD*(cnt[1]==1? cnt[2]+1:1))%=MOD; 823 if(cnt[2]&&cnt[1])(res+=ans*(cnt[2]==1? cnt[3]+1:1))%=MOD; 824 REP(i,2,2*n-1)if(cnt[i]&&cnt[i+1]){ 825 (res+=ans*(cnt[i+1]==1? cnt[i+2]+1:1)%MOD*(cnt[i]==1? cnt[i-1]+1:1))%=MOD; 826 } 827 cout<<res*qpow(n*n%MOD,MOD-2)%MOD<<endl; 828 } 829 void TC() { 830 init(1000000); 831 int tc=1; 832 fastIO::read(tc); 833 while(tc--) { 834 Main(); 835 cout.flush(); 836 } 837 } 838 signed main() { 839 return cin.tie(0),cout.tie(0),ios::sync_with_stdio(0),TC(),0; 840 } 841 /* 842 1. CLEAR the arrays (ESPECIALLY multitests) 843 2. DELETE useless output 844 */ 845 ``` 846 847 Method 2: 848 849 **Hint1** 850 851 Try to find some way to "sort" the grid, for swapping different rows and different columns doesn't matter. How? 852 853 **Answer** 854 855 Sort by the number of $1$. 856 857 **Hint2** 858 859 How to calculate the beauty? 860 861 **Answer** 862 863 The beauty is the product of factorials of number of equal rows and equal columns. 864 865 **Hint3** 866 867 How to solve the original problem when the initial grid has positive beauty? How to optimize? 868 869 **Hint4** 870 871 How to solve the original problem when the initial grid is impossible to be painted out? Are there too many ways to flip a block? 872 873 **Tutorial** 874 875 Read the hints. 876 877 Let's sort the rows and columns in some way, which means you should swap two rows or two columns each time to make them ordered. Let's sort by the number of $1$ in each row and column. For example, the result of sorting the left part is shown in the right part: 878 879 $ \left[\begin{matrix}2&1&1&1\\2&2&1&2\\1&1&1&1\\2&2&1&2\end{matrix}\right]\Rightarrow\left[\begin{matrix}1&1&1&1\\1&1&1&2\\1&2&2&2\\1&2&2&2\end{matrix}\right] $ 880 881 We claim that the grid is solvealbe if and only if the later rows are "included" by previous rows, and so for the columns. For example, if a position in any row is filled with $1$, then the position in any previous row must also be $1$. This is correct because you'll notice that any submatrices of the following two types cannot appear in a solveable grid. To check that, you'll only need to check adjacent rows and columns. 882 883 $\left[\begin{matrix}1&2\\2&1\end{matrix}\right],\left[\begin{matrix}2&1\\1&2\end{matrix}\right]$ 884 885 After you sort all of that, the number of ways to paint it is easy to think about. It's similar to the product of factorials of the number of each kind of rows(for example, the last two rows in the right above). The only to notice is the first step of painting shouldn't be counted. 886 887 Consider modifying one block. If the initial grid is solveable, there're only $O(n)$ types of changing(in each row, all the $1$ and $2$ can be considered the same). Each type of changing can be done in $O(1)$ using simple discussion. 888 889 If the initial grid is unsolveable, we should find the two adjacent rows **and** columns that starts the problem. We claim that the block to change must belong to one of the four blocks in the intersection of the rows and columns. Just try every possible situation and do brute force on it. 890 891 For example, consider the following matrix: The first two columns and the last two rows went wrong. So let's try to change blocks $(3,1),(3,2),(4,1),(4,2)$ to judge whether it is possible. 892 893 $\left[\begin{matrix}1&1&1&1\\1&1&1&2\\1&2&2&2\\2&1&2&2\end{matrix}\right]$ 894 895 The time complexity is $O((n+m)\log n)$, and if you implement carefully enough you can solve it in $O(n+m)$. 896 897 **Implementation - method 2** 898 899 ``` 900 #if defined(LOCAL) or not defined(LUOGU) 901 #pragma GCC optimize(3) 902 #pragma GCC optimize("Ofast,unroll-loops") 903 #endif 904 #include<bits/stdc++.h> 905 using namespace std; 906 struct time_helper 907 { 908 #ifdef LOCAL 909 clock_t time_last; 910 #endif 911 time_helper() 912 { 913 #ifdef LOCAL 914 time_last=clock(); 915 #endif 916 } 917 void test() 918 { 919 #ifdef LOCAL 920 auto time_now=clock(); 921 std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl; 922 time_last=time_now; 923 #endif 924 } 925 ~time_helper() 926 { 927 test(); 928 } 929 }time_helper; 930 #ifdef LOCAL 931 #include"dbg.h" 932 #else 933 #define dbg(...) (__VA_ARGS__) 934 #endif 935 namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;} 936 #define getchar Fread::getchar 937 #define putchar Fwrite::putchar 938 #define Setprecision 10 939 #define between '\n' 940 #define __int128 long long 941 template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(T x){for(auto &y:x)*this<<y<<between;*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-Setprecision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(T c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(std::string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;} 942 #define cin Fastio::cin 943 #define cout Fastio::cout 944 #define endl Fastio::endl 945 946 void solve(); 947 main() 948 { 949 int t=1; 950 cin>>t; 951 while(t--)solve(); 952 } 953 template <uint32_t mod> 954 struct LazyMontgomeryModInt { 955 using mint = LazyMontgomeryModInt; 956 using i32 = int32_t; 957 using u32 = uint32_t; 958 using u64 = uint64_t; 959 static constexpr u32 get_r() { 960 u32 ret = mod; 961 for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; 962 return ret; 963 } 964 static constexpr u32 r = get_r(); 965 static constexpr u32 n2 = -u64(mod) % mod; 966 static_assert(r * mod == 1, "invalid, r * mod != 1"); 967 static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); 968 static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); 969 u32 a; 970 constexpr LazyMontgomeryModInt() : a(0) {} 971 constexpr LazyMontgomeryModInt(const int64_t &b) 972 : a(reduce(u64(b % mod + mod) * n2)){}; 973 static constexpr u32 reduce(const u64 &b) { 974 return (b + u64(u32(b) * u32(-r)) * mod) >> 32; 975 } 976 constexpr mint &operator+=(const mint &b) { 977 if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; 978 return *this; 979 } 980 constexpr mint &operator-=(const mint &b) { 981 if (i32(a -= b.a) < 0) a += 2 * mod; 982 return *this; 983 } 984 constexpr mint &operator*=(const mint &b) { 985 a = reduce(u64(a) * b.a); 986 return *this; 987 } 988 constexpr mint &operator/=(const mint &b) { 989 *this *= b.inverse(); 990 return *this; 991 } 992 constexpr mint operator+(const mint &b) const { return mint(*this) += b; } 993 constexpr mint operator-(const mint &b) const { return mint(*this) -= b; } 994 constexpr mint operator*(const mint &b) const { return mint(*this) *= b; } 995 constexpr mint operator/(const mint &b) const { return mint(*this) /= b; } 996 constexpr bool operator==(const mint &b) const { 997 return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); 998 } 999 constexpr bool operator!=(const mint &b) const { 1000 return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); 1001 } 1002 constexpr mint operator-() const { return mint() - mint(*this); } 1003 constexpr mint pow(u64 n) const { 1004 mint ret(1), mul(*this); 1005 while (n > 0) { 1006 if (n & 1) ret *= mul; 1007 mul *= mul; 1008 n >>= 1; 1009 } 1010 return ret; 1011 } 1012 constexpr mint inverse() const { return pow(mod - 2); } 1013 friend ostream &operator<<(ostream &os, const mint &b) { 1014 return os << b.get(); 1015 } 1016 friend istream &operator>>(istream &is, mint &b) { 1017 int64_t t; 1018 is >> t; 1019 b = LazyMontgomeryModInt<mod>(t); 1020 return (is); 1021 } 1022 constexpr u32 get() const { 1023 u32 ret = reduce(a); 1024 return ret >= mod ? ret - mod : ret; 1025 } 1026 static constexpr u32 get_mod() { return mod; } 1027 explicit operator u32() const {return get();} 1028 }; 1029 #define modint LazyMontgomeryModInt 1030 #define mint modint<p> 1031 constexpr int p=998244353; 1032 std::pmr::monotonic_buffer_resource pool(100000000); 1033 void solve() 1034 { 1035 int n,m; 1036 cin>>n>>m; 1037 vector<std::pmr::vector<int>>a(n,std::pmr::vector<int>{&pool}); 1038 time_helper.test(); 1039 while(m--) 1040 { 1041 int u,v; 1042 cin>>u>>v; 1043 u--,v--; 1044 a[u].emplace_back(v); 1045 } 1046 time_helper.test(); 1047 std::pmr::vector<mint>inv{&pool},fac{&pool},ifac{&pool}; 1048 inv.resize(n+1),fac.resize(n+1),ifac.resize(n+1); 1049 std::pmr::vector<int>arr_cnt{&pool}; 1050 arr_cnt.resize(n+2); 1051 auto arr_sort=[&](const auto&a) 1052 { 1053 for(int i=0;i<n;i++) 1054 arr_cnt[a[i].size()+1]++; 1055 for(int x=1;x<=n;x++) 1056 arr_cnt[x]+=arr_cnt[x-1]; 1057 vector<std::pmr::vector<int>>b(n,std::pmr::vector<int>{&pool}); 1058 for(int i=0;i<n;i++) 1059 b[arr_cnt[a[i].size()]++]=move(a[i]); 1060 for(int x=0;x<=n+1;x++) 1061 arr_cnt[x]=0; 1062 return b; 1063 }; 1064 a=move(arr_sort(a)); 1065 auto arr_eq=[&](const auto&a,const auto&b) 1066 { 1067 if(a.size()!=b.size())return false; 1068 bool res=1; 1069 for(auto q:a)arr_cnt[q]=1; 1070 for(auto q:b)if(!arr_cnt[q]){res=0;break;} 1071 for(auto q:a)arr_cnt[q]=0; 1072 return res; 1073 }; 1074 auto arr_includes=[&](const auto&a,const auto&b) 1075 { 1076 bool res=1; 1077 for(auto q:a)arr_cnt[q]=1; 1078 for(auto q:b)if(!arr_cnt[q]){res=0;break;} 1079 for(auto q:a)arr_cnt[q]=0; 1080 return res; 1081 }; 1082 auto arr_set_difference=[&](const auto&a,const auto&b,auto &diff) 1083 { 1084 for(auto q:b)arr_cnt[q]=1; 1085 for(auto q:a) 1086 if(!arr_cnt[q]) 1087 { 1088 diff.emplace_back(q); 1089 if(diff.size()>2)break; 1090 } 1091 for(auto q:b)arr_cnt[q]=0; 1092 }; 1093 { 1094 fac[0]=1; 1095 for(int x=1;x<=n;x++) 1096 fac[x]=fac[x-1]*x; 1097 ifac[n]=fac[n].inverse(); 1098 for(int x=n;x>=1;x--) 1099 ifac[x-1]=ifac[x]*x,inv[x]=ifac[x]*fac[x-1]; 1100 } 1101 int failcnt=0; 1102 for(int x=1;x<n;x++) 1103 failcnt+=!(arr_includes(a[x],a[x-1])); 1104 if(failcnt==0) 1105 { 1106 int nc=0; 1107 mint ansbas=fac[a[0].size()],ans=0; 1108 std::pmr::vector<int>tnc{&pool},tmc{&pool}; 1109 tmc.emplace_back(a[0].size()); 1110 int ct=0; 1111 for(int x=0;x<n;x++) 1112 if(x==n-1||!arr_eq(a[x],a[x+1])) 1113 { 1114 nc++; 1115 if(a[x].size()!=n) 1116 ansbas*=fac[nc]; 1117 int mc=0; 1118 if(x==n-1)mc=n-a[x].size(); 1119 else mc=a[x+1].size()-a[x].size(); 1120 if(x!=n-1) 1121 ansbas*=fac[mc]; 1122 tnc.emplace_back(nc); 1123 tmc.emplace_back(mc); 1124 nc=0; 1125 ct++; 1126 } 1127 else nc++; 1128 for(int x=0;x<ct;x++) 1129 { 1130 int nc=tnc[x],mc=tmc[x+1]; 1131 if(mc==0)continue; 1132 mint fix=ansbas; 1133 if(x==ct-1) 1134 { 1135 fix*=mc; 1136 } 1137 if(x==ct-2&&mc==1&&tmc[x+2]==0) 1138 { 1139 fix*=inv[tnc[x+1]+1]; 1140 } 1141 if(x==ct-1||mc!=1) 1142 { 1143 if(mc) 1144 { 1145 if(nc>1)ans+=fix; 1146 else ans+=fix*(tmc[x]+1); 1147 } 1148 } 1149 else if(nc>1)ans+=fix*(tnc[x+1]+1); 1150 else ans+=fix*(tnc[x+1]+1)*(tmc[x]+1); 1151 } 1152 for(int x=0;x<ct;x++) 1153 { 1154 int nc=tnc[x],mc=tmc[x]; 1155 if(mc==0)continue; 1156 mint fix=ansbas; 1157 if(x==ct-1) 1158 { 1159 if(tmc[x+1]==0)fix*=nc; 1160 if(nc==1)fix*=inv[tmc[x+1]+1]; 1161 } 1162 if(x==0||mc!=1) 1163 { 1164 if(mc) 1165 { 1166 if(nc>1)ans+=fix; 1167 else ans+=fix*(tmc[x+1]+1); 1168 } 1169 } 1170 else if(nc>1)ans+=fix*(tnc[x-1]+1); 1171 else ans+=fix*(tnc[x-1]+1)*(tmc[x+1]+1); 1172 } 1173 cout<<(ans*inv[n]*inv[n]).get()<<endl; 1174 return; 1175 } 1176 if(failcnt>2){cout<<0<<endl;return;} 1177 mint ans=0; 1178 auto calc=[&](vector<std::pmr::vector<int>>&a)->mint 1179 { 1180 a=move(arr_sort(a)); 1181 for(int x=1;x<n;x++) 1182 if(!arr_includes(a[x],a[x-1]))return 0; 1183 int nc=0; 1184 mint ansbas=fac[a[0].size()]; 1185 for(int x=0;x<n;x++) 1186 if(x==n-1||!arr_eq(a[x],a[x+1])) 1187 { 1188 nc++; 1189 if(a[x].size()!=n) 1190 ansbas=ansbas*fac[nc]; 1191 int mc=0; 1192 if(x==n-1)mc=n-a[x].size(); 1193 else mc=a[x+1].size()-a[x].size(); 1194 if(x!=n-1) 1195 ansbas=ansbas*fac[mc]; 1196 nc=0; 1197 } 1198 else nc++; 1199 return ansbas; 1200 }; 1201 std::pmr::set<pair<int,int>>st{&pool}; 1202 std::pmr::vector<int>diff{&pool}; 1203 vector<std::pmr::vector<int>>b(n,std::pmr::vector<int>{&pool}); 1204 time_helper.test(); 1205 for(int x=1;x<n;x++) 1206 if(!arr_includes(a[x],a[x-1])) 1207 { 1208 for(int y=x+2;y<n;y++) 1209 if(!arr_includes(a[y],a[y-1]))goto fail; 1210 { 1211 diff.clear(); 1212 arr_set_difference(a[x],a[x-1],diff); 1213 if(diff.size()<=1) 1214 { 1215 if(!st.count({x-1,diff[0]})) 1216 { 1217 b=a; 1218 b[x-1].emplace_back(diff[0]); 1219 ans+=calc(b),st.insert({x-1,diff[0]}); 1220 } 1221 if(!st.count({x,diff[0]})) 1222 { 1223 b=a; 1224 b[x].erase(find(b[x].begin(),b[x].end(),diff[0])); 1225 ans+=calc(b),st.insert({x,diff[0]}); 1226 } 1227 } 1228 } 1229 { 1230 diff.clear(); 1231 arr_set_difference(a[x-1],a[x],diff); 1232 if(diff.size()<=1) 1233 { 1234 if(!st.count({x,diff[0]})) 1235 { 1236 b=a; 1237 b[x].emplace_back(diff[0]); 1238 ans+=calc(b),st.insert({x,diff[0]}); 1239 } 1240 if(!st.count({x-1,diff[0]})) 1241 { 1242 b=a; 1243 b[x-1].erase(find(b[x-1].begin(),b[x-1].end(),diff[0])); 1244 ans+=calc(b),st.insert({x-1,diff[0]}); 1245 } 1246 } 1247 } 1248 fail: 1249 break; 1250 } 1251 cout<<(ans*inv[n]*inv[n]).get()<<endl; 1252 } 1253 ```