codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1439.md (19970B)


      1 Source: https://codeforces.com/blog/entry/84731
      2 
      3 We want to mention [BamiTorabi](/profile/BamiTorabi "Expert BamiTorabi") who we thank for helping us with translating the problems and writing the tutorials, and also we apologize for div1 A2 and B hopefully you will forgive us :( .
      4 
      5 Tutorial is loading...
      6 
      7 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi")
      8 
      9 **official solution**
     10 
     11 ```
     12 //                                In The Name Of Allah
     13 #include <bits/stdc++.h>
     14 #define	ss second
     15 #define ff first
     16 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
     17 #define ret(n) return cout << n, 0
     18 #define se(n) cout << setprecision(n) << fixed
     19 #define pb push_back
     20 #define ll long long
     21 #define ld long double
     22 //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
     23 //#pragma GCC optimize("no-stack-protector,fast-math")
     24 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
     25 using namespace std; 
     26 
     27 const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
     28 typedef pair <int, int> pii;
     29 
     30 void solve() {
     31 	int n, c0, c1, t;
     32 	string s;
     33 	cin >> n >> c0 >> c1 >> t >> s;
     34 	int ans = 0;
     35 	for(auto u : s) {
     36 		if(u == '0') 
     37 			ans += min(c0, c1 + t);
     38 		else 
     39 			ans += min(c1, c0 + t);
     40 	}
     41 	cout << ans << endl;
     42 }
     43 
     44 int32_t main() {
     45 	int t;
     46 	cin >> t;
     47 	while(t--)
     48 		solve();
     49 	return 0;
     50 }
     51 ```
     52 
     53 Tutorial is loading...
     54 
     55 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi")
     56 
     57 **official solution**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 typedef long long int ll;
     62 typedef long double ld;
     63 #define pb push_back
     64 #define pii pair < int , int >
     65 #define F first
     66 #define S second
     67 #define endl '\n'
     68 #define int long long
     69 #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
     70 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
     71 #define kill(x) return cout<<x<<'\n', 0;
     72 using namespace std;
     73 const int N=2e5+100;
     74 ll a[N];
     75 int Main(){
     76     ll n, k;
     77     cin >> k >> n;
     78     for (int i=1;i<=n*k;i++){
     79         cin >> a[i];
     80     }
     81     ll x=(k+1)/2 - 1;
     82     x = k - x;
     83     ll z=n*k+1;
     84     ll ans=0;
     85     while(n--){
     86         z-=x;
     87         if (z<=0) break;
     88         ans+=a[z];
     89     }
     90     cout << ans << endl;
     91 }
     92 int32_t main(){
     93     ll t;
     94     cin >> t;
     95     while(t--){
     96         Main();
     97     }
     98 }
     99 ```
    100 
    101 Tutorial is loading...
    102 
    103 Prepared by [Mohammad.H915](/profile/Mohammad.H915 "Master Mohammad.H915") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi")
    104 
    105 **official solution**
    106 
    107 ```
    108 //                             In The Name Of Allah
    109 #include <bits/stdc++.h>
    110 #define	ss second
    111 #define ff first
    112 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    113 #define ret(n) return cout << n, 0
    114 #define se(n) cout << setprecision(n) << fixed
    115 #define pb push_back
    116 #define ll long long
    117 #define ld long double
    118 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
    119 #pragma GCC optimize("no-stack-protector,fast-math")
    120 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    121 using namespace std; 
    122 
    123 const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;
    124 typedef pair <int, int> pii;
    125 char c[N][N];
    126 bool cnt[N][N];
    127 
    128 struct node {int x1, y1, x2, y2, x3, y3;} p[5];
    129 vector <node> v;
    130 
    131 void upd(int x, int y, int tp, bool is) {
    132     if(is)
    133         v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});
    134     else 
    135         cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;
    136 }
    137 
    138 void solve() {
    139 	int n, m, od = 0;
    140 	v.clear();
    141 	cin >> n >> m;
    142 	for(int i = 1; i <= n; i++) {
    143 		for(int j = 1; j <= m; j++) {
    144 			cin >> c[i][j];
    145 			if(c[i][j] == '1')
    146 				od++, cnt[i][j] = true;
    147 			else
    148 			    cnt[i][j] = false;
    149 		}
    150 	}
    151 	if(od == 0) {
    152 		cout << 0 << endl;
    153 		return;
    154 	}
    155 	if(n == 1 || m == 1) {
    156 		cout << -1 << endl;
    157 		return;
    158 	}
    159     for(int i = 1; i <= n - 2; i++) {
    160 		for(int j = 1; j <= m; j++) {
    161 			if(cnt[i][j]) {
    162 			    if(j != m) {
    163 			        v.pb({i, j, i + 1, j, i + 1, j + 1});
    164 			        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;
    165 			    } 
    166 			    else {
    167 			        v.pb({i, j, i + 1, j, i + 1, j - 1});
    168 			        cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;
    169 			    }
    170 			}
    171 		}
    172 	}
    173 	for(int i = 1; i <= m - 2; i++) {
    174 	    if(cnt[n - 1][i]) {
    175 	        v.pb({n - 1, i, n - 1, i + 1, n, i + 1});
    176 	        cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 
    177 	    }
    178 	    if(cnt[n][i]) {
    179 	        v.pb({n, i, n - 1, i + 1, n, i + 1});
    180 	        cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; 
    181 	    }
    182 	}
    183 	for(int msk = 0; msk < (1 << 4); msk++) {
    184 	    for(int j = 0; j < 4; j++) 
    185 	       if(msk & (1 << j))
    186 	           upd(n - 1, m - 1, j, 0);
    187 	    if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {
    188 	        for(int j = 0; j < 4; j++) 
    189 	            if(msk & (1 << j))
    190 	                upd(n - 1, m - 1, j, 1);
    191 	        break;
    192 	    }
    193 	    for(int j = 0; j < 4; j++)
    194 	        if(msk & (1 << j))
    195 	            upd(n - 1, m - 1, j, 0);
    196 	}
    197 	cout << (int)v.size() << endl;
    198 	for(auto u : v)
    199         cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;
    200 }
    201 
    202 int32_t main(){
    203 	use_fast;
    204     p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};
    205 	int t;
    206 	cin >> t;
    207 	while(t--)
    208 		solve();
    209 	return 0;
    210 }
    211 ```
    212 
    213 Tutorial is loading...
    214 
    215 Prepared by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") Editorial by [Amoo_Safar](/profile/Amoo_Safar "International Grandmaster Amoo_Safar")
    216 
    217 **official solution**
    218 
    219 ```
    220 //                             In The Name Of Allah                                           
    221 #include <bits/stdc++.h>
    222 #define	ss second
    223 #define ff first
    224 #define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    225 #define se(n) cout << setprecision(n) << fixed
    226 #define pb push_back
    227 //#define int long long
    228 #define ld long double
    229 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
    230 #pragma GCC optimize("no-stack-protector,fast-math")
    231 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    232 using namespace std; 
    233 const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;
    234 typedef pair <int, int> pii;
    235 int mark[N], deg[N], ct[N];
    236 bool ans[N], can[N];
    237 vector <int> v[N], A;
    238 vector <pii> ch[N];
    239 bool cmp(int x, int y) {
    240 	return mark[x] < mark[y];
    241 }
    242 
    243 void solve() {
    244 	int n, m, k;
    245 	cin >> n >> m >> k;
    246 	A.clear();
    247 	for(int i = 0; i <= n; i++)
    248 	    v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;
    249 	for(int i = 0; i < m; i++) {
    250 		int x, y;
    251 		cin >> x >> y;
    252 		v[x].pb(y);
    253 		v[y].pb(x);
    254 	}
    255 	if(k > 500) {
    256 	   cout << -1 << endl;
    257 	   return;
    258 	}
    259 	set <pii> st;
    260 	for(int i = 1; i <= n; i++)
    261 		st.insert({deg[i] = (int)v[i].size(), i});
    262 	int cnt = 1;
    263 	while((int)st.size()) {
    264 		pii p = *st.begin();
    265 		if(p.ff >= k) {
    266 			cout << 1 << " " << (int)st.size() << endl;
    267 			for(auto u : st)
    268 				cout << u.ss << " ";
    269 			cout << endl;
    270 			return;
    271 		}
    272 		else {
    273 			st.erase(p);
    274 			mark[p.ss] = cnt;
    275 			for(auto u : v[p.ss])
    276 				if(!mark[u])
    277 					st.erase({deg[u], u}), st.insert({--deg[u], u});
    278 			A.pb(p.ss);
    279 		}
    280 		cnt++;
    281 	}
    282 	for(auto i : A) {
    283 		int nxt = 0;
    284 		for(auto u : v[i]) 
    285 			if(mark[u] > mark[i])
    286 				ct[nxt++] = u, can[u] = true;
    287 		for(auto u : ch[i]) 
    288 			if(!can[u.ff])
    289 				ans[u.ss] = false;
    290 		for(int j = 0; j < nxt; j++)
    291 			can[ct[j]] = false;
    292 		if(nxt != k - 1)
    293 			continue;
    294 		ans[i] = true;
    295 		sort(ct, ct + nxt, cmp);
    296 		for(int j = 0; j < nxt; j++)
    297 			for(int k = j + 1; k < nxt; k++)
    298 				ch[ct[j]].pb({ct[k], i});
    299 	}
    300 	for(auto i : A) {
    301 		if(!ans[i])
    302 			continue;
    303 		cout << 2 << endl;
    304 		cout << i << " ";
    305 		for(auto u : v[i])
    306 			if(mark[u] > mark[i])
    307 				cout << u << " ";
    308 		cout << endl;
    309 		return;
    310 	}
    311 	cout << -1 << endl;
    312 	return;
    313 }
    314 
    315 int32_t main() {
    316 	use_fast;
    317 	int t;
    318     cin >> t;
    319     while(t--)
    320         solve();
    321 	return 0;
    322 }
    323 ```
    324 
    325 Tutorial is loading...
    326 
    327 prepared by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi")
    328 
    329 **official solution**
    330 
    331 ```
    332 #include <bits/stdc++.h>
    333 #pragma GCC optimize ("O2,unroll-loops")
    334 #pragma GCC optimize("no-stack-protector,fast-math")
    335 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    336 
    337 using namespace std;
    338 typedef long long ll;
    339 typedef long double ld;
    340 typedef pair<int, int> pii;
    341 typedef pair<pii, int> piii;
    342 typedef pair<ll, ll> pll;
    343 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    344 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    345 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    346 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    347 #define all(x) x.begin(), x.end()
    348 #define pb push_back
    349 #define kill(x) return cout<<x<<'\n', 0;
    350 
    351 const int inf=1000000010;
    352 const ll INF=10000000000000010LL;
    353 const int mod=1000000007;
    354 const int MAXN=200010, LOG=20;
    355 
    356 ll n, m, k, u, v, x, y, t, a, b, ans;
    357 ll A[MAXN];
    358 ll seg[MAXN<<2], lazy[MAXN<<2];
    359 int Mn[MAXN<<2], Mx[MAXN<<2];
    360 
    361 void Build(int id, int tl, int tr){
    362 	if (tr-tl==1){
    363 		Mn[id]=Mx[id]=seg[id]=A[tl];
    364 		return ;
    365 	}
    366 	int mid=(tl+tr)>>1;
    367 	Build(id<<1, tl, mid);
    368 	Build(id<<1 | 1, mid, tr);
    369 	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
    370 	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
    371 	seg[id]=seg[id<<1] + seg[id<<1 | 1];	
    372 }
    373 inline void add_lazy(int id, int len, ll val){
    374 	Mn[id]=val;
    375 	Mx[id]=val;
    376 	lazy[id]=val;
    377 	seg[id]=len*val;
    378 }
    379 inline void shift(int id, int tl, int tr){
    380 	if (!lazy[id]) return ;
    381 	int mid=(tl+tr)>>1;
    382 	add_lazy(id<<1, mid-tl, lazy[id]);
    383 	add_lazy(id<<1 | 1, tr-mid, lazy[id]);
    384 	lazy[id]=0;
    385 }
    386 void Maximize(int id, int tl, int tr, int pos, ll val){
    387 	if (pos<=tl || val<=Mn[id]) return ;
    388 	if (tr<=pos && Mx[id]<=val){
    389 		add_lazy(id, tr-tl, val);
    390 		return ;
    391 	}
    392 	shift(id, tl, tr);
    393 	int mid=(tl+tr)>>1;
    394 	Maximize(id<<1, tl, mid, pos, val);
    395 	Maximize(id<<1 | 1, mid, tr, pos, val);
    396 	Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);
    397 	Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);
    398 	seg[id]=seg[id<<1] + seg[id<<1 | 1];
    399 }
    400 int BS1(int id, int tl, int tr, int pos, ll val){
    401 	if (tr<=pos || val<Mn[id]) return tr;
    402 	if (tr-tl==1) return tl;
    403 	shift(id, tl, tr);
    404 	int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);
    405 	if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);
    406 	return tmp;
    407 }
    408 int BS2(int id, int tl, int tr, ll val){
    409 	if (seg[id]<=val) return tr;
    410 	if (tr-tl==1) return tl;
    411 	shift(id, tl, tr);
    412 	int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);
    413 	if (tmp<mid) return tmp;
    414 	return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);
    415 }
    416 ll Get(int id, int tl, int tr, int l, int r){
    417 	if (r<=tl || tr<=l) return 0;
    418 	if (l<=tl && tr<=r) return seg[id];
    419 	shift(id, tl, tr);
    420 	int mid=(tl+tr)>>1;
    421 	return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);
    422 }
    423 
    424 int main(){
    425 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    426 	//freopen("input.txt", "r", stdin);
    427 	//freopen("output.txt", "w", stdout);
    428 	cin>>n>>m;
    429 	for (int i=1; i<=n; i++) cin>>A[i];
    430 	Build(1, 1, n+1);
    431 	while (m--){
    432 		cin>>t>>x>>y;
    433 		if (t==1) Maximize(1, 1, n+1, x+1, y);
    434 		else{
    435 			ans=0;
    436 			while (1){
    437 				x=BS1(1, 1, n+1, x, y);
    438 				if (x==n+1) break ;
    439 				ll val=y+Get(1, 1, n+1, 1, x);
    440 				int xx=BS2(1, 1, n+1, val);
    441 				// buy [x, xx)
    442 				ans+=xx-x;
    443 				y-=Get(1, 1, n+1, x, xx);
    444 				x=xx;
    445 			}
    446 			cout<<ans<<"\n";
    447 		}
    448 	}
    449 	
    450 	return 0;
    451 }
    452 ```
    453 
    454 Tutorial is loading...
    455 
    456 prepared by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi") Editorial by [Mehrdad_Sohrabi](/profile/Mehrdad_Sohrabi "Grandmaster Mehrdad_Sohrabi")
    457 
    458 **official solution**
    459 
    460 ```
    461 #include <bits/stdc++.h>
    462 #pragma GCC optimize ("O2,unroll-loops")
    463 //#pragma GCC optimize("no-stack-protector,fast-math")
    464 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    465 
    466 using namespace std;
    467 typedef long long ll;
    468 typedef long double ld;
    469 typedef pair<int, int> pii;
    470 typedef pair<pii, int> piii;
    471 typedef pair<ll, ll> pll;
    472 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    473 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    474 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    475 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    476 #define all(x) x.begin(), x.end()
    477 #define pb push_back
    478 #define kill(x) return cout<<x<<'\n', 0;
    479 
    480 const ld eps=1e-7;
    481 const int inf=1000000010;
    482 const ll INF=10000000000000010LL;
    483 const int MAXN=505, LOG=20;
    484 
    485 ll n, m, k, u, v, x, y, t, a, b, ans, mod;
    486 ll dp1[MAXN], dp2[MAXN];
    487 ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];
    488 ll C[MAXN][MAXN];
    489 
    490 int main(){
    491 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    492 	//freopen("input.txt", "r", stdin);
    493 	//freopen("output.txt", "w", stdout);
    494 	cin>>n>>m>>mod;
    495 	
    496 	for (int i=0; i<MAXN; i++){
    497 		C[i][0]=C[i][i]=1;
    498 		for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;
    499 	}
    500 	dp1[0]=1;
    501 	for (int n=1; n<MAXN; n++){
    502 		for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;
    503 		dp1[n]=(n+1)*dp1[n]%mod;
    504 		for (int i=1; i<=n; i++){
    505 			dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;
    506 			dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;
    507 		}
    508 	}
    509 	
    510 	dp3[0][0]=1;
    511 	for (int n=1; n<MAXN; n++){
    512 		for (int m=0; m<n; m++){
    513 			dp3[n][m]=dp3[n-1][m];
    514 			dp4[n][m]=dp4[n-1][m];
    515 			for (int i=1; i<=m; i++){
    516 				dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
    517 				dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;
    518 				dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;
    519 			}
    520 		}
    521 		dp3[n][n]=dp1[n];
    522 		dp4[n][n]=dp2[n];
    523 	}
    524 
    525 	cout<<dp4[n][m]<<"\n";	
    526 	
    527 	return 0;
    528 }
    529 ```
    530 
    531 **O(n2) solution**
    532 
    533 ```
    534 // And you curse yourself for things you never done
    535 // Shayan.P  2020-08-29
    536 
    537 #include<bits/stdc++.h>
    538 
    539 #define F first
    540 #define S second
    541 #define PB push_back
    542 #define sz(s) int((s).size())
    543 #define bit(n,k) (((n)>>(k))&1)
    544 
    545 using namespace std;
    546 
    547 typedef long long ll;
    548 typedef pair<int,int> pii;
    549 
    550 const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;
    551 
    552 ll n, m;
    553 
    554 ll Pow(ll a, ll b){
    555     b = (b + (mod-1)) % (mod-1); // to handle b == -1
    556     int ans=1;
    557     for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;
    558     return ans;
    559 }
    560 inline void add(ll &a, ll b){
    561     a = (a + b) % mod;
    562 }
    563     
    564 ll fac[maxn], ifac[maxn];
    565 
    566 ll C(ll n, ll k){
    567 	if (n<k || k<0) return 0;
    568 	return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
    569 }
    570 
    571 int main(){
    572     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    573     
    574     fac[0] = 1;
    575     for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;
    576     ifac[maxn-1] = Pow(fac[maxn-1], mod-2);
    577     for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;
    578     
    579     cin >> n >> m;
    580     ++n; //!
    581     
    582 	int ans = 0;
    583     for(ll bef = 0; bef < m; bef++){
    584 		for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0
    585 			ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;
    586 			ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;
    587 			ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;
    588 			ll score=w*(w+1)%mod*n%mod;
    589 			ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;
    590 			ans=(ans + cnt*score%mod*after) % mod;
    591 		}
    592     }    
    593     cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";
    594     return 0;
    595 }
    596 ```
    597 
    598 Tutorial is loading...
    599 
    600 Prepared by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") Editorial by [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382")
    601 
    602 **official solution**
    603 
    604 ```
    605 #include <bits/stdc++.h>
    606 #pragma GCC optimize ("O2,unroll-loops")
    607 //#pragma GCC optimize("no-stack-protector,fast-math")
    608 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    609 
    610 using namespace std;
    611 typedef long long ll;
    612 typedef long double ld;
    613 typedef pair<int, int> pii;
    614 typedef pair<pii, int> piii;
    615 typedef pair<ll, ll> pll;
    616 #define debug(x) cerr<<#x<<'='<<(x)<<endl;
    617 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
    618 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
    619 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
    620 #define all(x) x.begin(), x.end()
    621 #define pb push_back
    622 #define kill(x) return cout<<x<<'\n', 0;
    623 
    624 const ld eps=1e-7;
    625 const int inf=1000000010;
    626 const ll INF=10000000000000010LL;
    627 const int mod=1000000007;
    628 const int MAXN=400010, LOG=30;
    629 
    630 int n, m, k, u, v, x, y, t, a, b, root, ans;
    631 pii A[MAXN], V[MAXN];
    632 int par[MAXN], sum[MAXN];
    633 bool is[MAXN];
    634 vector<int> G[MAXN], grundy;
    635 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    636 
    637 inline int GetH(pii p){ return p.first+p.second;}
    638 inline pii GetPar(pii p, int k){
    639 	int x=p.first, y=p.second;
    640 	while (k){
    641 		int xx=(x&-x), yy=(y&-y);
    642 		if (!xx) xx=2*inf;
    643 		if (!yy) yy=2*inf;
    644 		int tmp=min(k, min(xx, yy));
    645 		k-=tmp;
    646 		if (xx<yy) x-=tmp;
    647 		else y-=tmp;
    648 	}
    649 	return {x, y};
    650 }
    651 inline int Zone(pii p, int n){
    652     if (p.first&(1<<(n-1))) return 2;
    653     if (p.second&(1<<(n-1))) return 1;
    654     return 0;
    655 }
    656 void dfs_order(vector<pii> &vec, int n=LOG) {
    657 	if (n==0 || vec.size()==0) return ;
    658 	vector<pii> v[3];
    659 	for (pii p:vec) {
    660 		int z=Zone(p, n);
    661 		p.first&=(1<<(n-1))-1;
    662 		p.second&=(1<<(n-1))-1;
    663 		v[z].pb(p);
    664     }
    665 	vec.clear();
    666 	for (int i:{0, 1, 2}) dfs_order(v[i], n-1);
    667 	for (pii p:v[0]) if (!p.first) vec.pb(p);
    668     for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});
    669     for (pii p:v[0]) if (p.first) vec.pb(p);
    670     for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});
    671 }
    672 pii Lca(pii u, pii v, int n=LOG) {
    673 	if (n==0) return {0, 0};
    674 	int zu = Zone(u, n), zv = Zone(v, n);
    675 	if (zu > zv) swap(u, v), swap(zu, zv);
    676 	u.first&=(1<<(n-1))-1;
    677 	u.second&=(1<<(n-1))-1;
    678 	v.first&=(1<<(n-1))-1;
    679 	v.second&=(1<<(n-1))-1;
    680 	if (zu == 1 && zv == 2) return {0, 0};
    681 	if (zu == 2 && zv == 2){
    682 		pii A = Lca(u, v, n-1);
    683 		return {A.first+(1<<(n-1)), A.second};
    684 	}
    685 	if (zu == 1 && zv == 1) {
    686 		pii A = Lca(u, v, n-1);
    687 		return {A.first, A.second+(1<<(n-1))};
    688 	}
    689 	if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);
    690 	if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);
    691 	return Lca(u, v, n-1);
    692 }
    693 inline int GetId(pii p){
    694 	return lower_bound(V, V+n, p)-V;
    695 }
    696 inline bool IsPar(pii u, pii v){
    697 	if (GetH(u)>GetH(v)) return 0;
    698 	return GetPar(v, GetH(v)-GetH(u))==u;
    699 }
    700 int dfs(int node){
    701 	for (int v:G[node]) sum[node]+=dfs(v);
    702 	return sum[node];
    703 }
    704 
    705 int main(){
    706 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    707 	//freopen("input.txt", "r", stdin);
    708 	//freopen("output.txt", "w", stdout);
    709 	vector<pii> vec;
    710 	cin>>m;
    711 	for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);
    712 	sort(all(vec));
    713 	vec.resize(unique(all(vec))-vec.begin());
    714 	dfs_order(vec);
    715 	for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));
    716 	sort(all(vec));
    717 	vec.resize(unique(all(vec))-vec.begin());
    718 	dfs_order(vec);
    719 	n=vec.size();
    720 	
    721 	debug("sorted")
    722 	
    723 	for (int i=0; i<n; i++) V[i]=vec[i];
    724 	sort(V, V+n);
    725 	vector<int> stk={root=GetId(vec[0])};
    726 	for (int i=1; i<n; i++){
    727 		int v=GetId(vec[i]);
    728 		while (!IsPar(V[stk.back()], V[v])) stk.pop_back();
    729 		par[v]=stk.back();
    730 		G[stk.back()].pb(v);
    731 		stk.pb(v);		
    732 	}
    733 	
    734 	for (int i=0; i<2*m; i+=2){
    735 		int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));
    736 		sum[u]++;
    737 		sum[v]++;
    738 		sum[lca]-=2;
    739 		is[lca]=1;
    740 	}
    741 	dfs(root);
    742 	for (int v=0; v<n; v++){
    743 		if (sum[v]){
    744 			grundy.pb(GetH(V[par[v]])+1);
    745 			grundy.pb(GetH(V[v])+1);
    746 		}
    747 		else if (is[v]){
    748 			grundy.pb(GetH(V[v]));
    749 			grundy.pb(GetH(V[v])+1);
    750 		}
    751 	}
    752 	sort(all(grundy));
    753 	vec.clear();
    754 	int last=-1;
    755 	for (int x:grundy){
    756 		if (last==-1){
    757 			if (vec.empty() || vec.back().second<x) last=x;
    758 			else{
    759 				last=vec.back().first;
    760 				vec.pop_back();
    761 			}
    762 		}
    763 		else{
    764 			if (last<x) vec.pb({last, x});
    765 			last=-1;
    766 		}
    767 	}
    768 	ans=2*vec.size();
    769 	if (ans && vec[0].first==0) ans--;
    770 	cout<<ans<<"\n";
    771 	
    772 	return 0;
    773 }
    774 ```