codeforces-scrape

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

805.md (33548B)


      1 Source: https://codeforces.com/blog/entry/51846
      2 
      3 We were waiting several weeks to setting this contest and hope the problem was good enough.
      4 
      5 #### Events
      6 
      7 There was a difficulty with [805E - Ice cream coloring](/contest/805/problem/E "Codeforces Round 411 (Div. 2)")/[804C - Ice cream coloring](/contest/804/problem/C "Codeforces Round 411 (Div. 1)"). A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this.
      8 
      9 For this sentence, `Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.` You can find the meaning of "connected subgraph" with [connected](http://mathworld.wolfram.com/ConnectedGraph.html) and [subgraph](http://www.edmath.org/MATtours/discrete/concepts/csubgr.html), thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement.
     10 
     11 I will write the full editorial in the few next days, now some hints and short solutions exist here.
     12 
     13 ## Hints
     14 
     15 [805A - Fake NP](/contest/805/problem/A "Codeforces Round 411 (Div. 2)")
     16 
     17 **hint1**
     18 
     19 Almost half of numbers are divisible by two.
     20 
     21 [805B - 3-palindrome](/contest/805/problem/B "Codeforces Round 411 (Div. 2)")
     22 
     23 **hint1**
     24 
     25 For the string shouldn't be any *i* ≤ *n* - 2, *s**i* = *s**i* + 2. Make some examples of little sizes.
     26 
     27 [805C - Find Amir](/contest/805/problem/C "Codeforces Round 411 (Div. 2)") / [804A - Find Amir](/contest/804/problem/A "Codeforces Round 411 (Div. 1)")
     28 
     29 **hint1**
     30 
     31 Find minimum weighted edges.
     32 
     33 **hint2**
     34 
     35 There is some edges with weight 0, try to connect them in a carefully way.
     36 
     37 [805D - Minimum number of steps](/contest/805/problem/D "Codeforces Round 411 (Div. 2)") / [804B - Minimum number of steps](/contest/804/problem/B "Codeforces Round 411 (Div. 1)")
     38 
     39 **hint1**
     40 
     41 The last situation is some '*a*' characters after some '*b*' ones.
     42 
     43 **hint2**
     44 
     45 The last situation is unique.
     46 
     47 **hint3**
     48 
     49 The number of steps is also unique.
     50 
     51 **hint4**
     52 
     53 Each '*b*' character makes a number of '*b*' characters in the last situation according to the number of '*a*' characters before it.
     54 
     55 [805E - Ice cream coloring](/contest/805/problem/E "Codeforces Round 411 (Div. 2)") / [804C - Ice cream coloring](/contest/804/problem/C "Codeforces Round 411 (Div. 1)")
     56 
     57 **hint1**
     58 
     59 We want to color the ice creams in a way that all of ice creams in a vertex would be different with this condition that if two vertices *u* and *v* have ice cream *i*, then all of vertices in the unique path of *u* and *v* would have it.
     60 
     61 **hint2**
     62 
     63 Let's have a trivial lower-bound for the answer.
     64 
     65 **answer**
     66 
     67 The trivial lower-bound should be maximum size of vertices' sets.
     68 
     69 **hint3**
     70 
     71 You can prove that by induction on leaves of the tree. And code it how you proved it.
     72 
     73 [805F - Expected diameter of a tree](/contest/805/problem/F "Codeforces Round 411 (Div. 2)") / [804D - Expected diameter of a tree](/contest/804/problem/D "Codeforces Round 411 (Div. 1)")
     74 
     75 **hint1**
     76 
     77 Let's solve the problem for just two tree.
     78 
     79 **Trivail solution**
     80 
     81 *d**t* is diameter of *t*-th tree and *f**i* is the maximum path starting from vertex *i*, for all valid *i* and *j*, assume that the edge is between them and find the diameter with *max*(*f**i* + *f**j* + 1, *max*(*d*1, *d*2)).
     82 
     83 consider this trivial ![](https://espresso.codeforces.com/c6b5efcfa6a58da30a590e54e2e774b5e0e75beb.png) solution and try to improve it to ![](https://espresso.codeforces.com/56f2ba50d8093bd1084452040e4d5eb62f1c060c.png).
     84 
     85 **hint2**
     86 
     87 ![](https://espresso.codeforces.com/8abee6833154735d3d739e003e123329cf549292.png)
     88 
     89 **Actually**
     90 
     91 seems SQRT.
     92 
     93 **How?**
     94 
     95 For every new query, try to do it with the complexity of ![](https://espresso.codeforces.com/1ae026fa4f23a365e16e8ff6ea84edc8048b1f28.png) , which *sz**i* means size of the components of *i*-th vertex. Prove its complexity is ![](https://espresso.codeforces.com/6945dc80216592cc8d05f37ae97a2bd57611f2e0.png).
     96 
     97 [804E - The same permutation](/contest/804/problem/E "Codeforces Round 411 (Div. 1)")
     98 
     99 **hint1**
    100 
    101 You can prove, we need even number of swaps to reach the same permutation. So ![](https://espresso.codeforces.com/4da883f26fff093432e518c5915d2ecf7ee7b399.png) and the answer for 4·*k* + 3 and 4·*k* + 4 is -1.
    102 
    103 **hint2**
    104 
    105 The solution almost is constructive.
    106 
    107 **Try to solve it for n = 4**
    108 
    109 And then solve *n* = 8 by *n* = 4.
    110 
    111 **hint3**
    112 
    113 Let's partition *n* = 4·*k* numbers to classes, each class contains a 4 consecutive numbers. And when *n* = 4·*k* + 1 there is a class with 5 consecutive numbers.
    114 
    115 [804F - Fake bullions](/contest/804/problem/F "Codeforces Round 411 (Div. 1)")
    116 
    117 **hint1**
    118 
    119 The problem consists two parts, the first part is to find *mn**i* and *mx**i*, the minimum and the maximum score *i*-th vertex may get after the score distribution. The second part is to finding the answer and all your need to solve this part is those two arrays. It is trivial *mn**i* is number of real bullion of golds in *i*-th vertex.
    120 
    121 **hint2**
    122 
    123 Let's find the scores for two vertices *u* and *v*, *u* have a directed edge to *v*.
    124 
    125 **u -> v**
    126 
    127 ![](https://espresso.codeforces.com/d05c10ef09ee67d890b591e443f768fbee032808.png)
    128 
    129 If *i*-th element from *u*-th vertex was painted and *j*-th element from *v*-th vertex was unpainted such that ![](https://espresso.codeforces.com/712bda89133736f78ee1b6a065383f793b00e00b.png) then *j*-th element from *v*-th vertex will be painted quickly. For two vertex, we can do it in complexity ![](https://espresso.codeforces.com/1e3aa4b6f52c9219aeab35e4cb69f6ad4e9fd768.png).
    130 
    131 **hint3**
    132 
    133 If we have this directed walk {*w*1, *w*2, ..., *w**k*}, you should affect *v*1 on *v**k* how I said in the previous hint with ![](https://espresso.codeforces.com/7d34dd0147754e3b90faed0c66995f389052e02d.png).
    134 
    135 **What about strogly connected components.**
    136 
    137 ![](https://espresso.codeforces.com/21b226ddd1e9afc185f622dc76656664a6314344.png)
    138 
    139 In this components if *i*-th element from *u*-th vertex was painted then for all of *j* such that ![](https://espresso.codeforces.com/712bda89133736f78ee1b6a065383f793b00e00b.png), *j*-th element from all vertices will be painted quickly. For this components, we can do it with complexity ![](https://espresso.codeforces.com/0971bf14c9a15b0942f6fb76f8697e4ac9a6a964.png). In the main problem, we can suppose all of a strongly conected component a vertex with size *g* in this way and we can calculate *mx**i* with answer of its component's vertex multiplied by ![](https://espresso.codeforces.com/ca0e98e484613a2eec434f45df4467b1cdb201c2.png).
    140 
    141 **hint4**
    142 
    143 SCC of the tournament yields a Hamiltonian path of strongly connected components( if we consider each component a vertex ). The problem decreased to solve this path. we can solve the path with the complexity of sum of vertices' sizes.
    144 
    145 **hint5**
    146 
    147 Now, for every vertex we have minimum and maximum score it may get. For B known vertices, to check if they can be the wanted set, we can assume their score be maximum possible and the other scores be minimum possible. If they were top, then they can be a sample of the wanted set.
    148 
    149 **hint6**
    150 
    151 Consider a sorted sequence of combination of two array *mn* and *mx*.
    152 
    153 For every vertex, consider the number of ways it(with its maximum score) can be the minimum score of the set of B vertices.
    154 
    155 # Solutions
    156 
    157 Tutorial is loading...
    158 
    159 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii")
    160 
    161 Time Complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    162 
    163 Memory complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    164 
    165 **python3**
    166 
    167 ```
    168 l,r=list(map(int,input().split()))
    169 print(2 if l<r else l)
    170 ```
    171 
    172 **C++**
    173 
    174 ```
    175 int main(){
    176     int l, r;
    177     scanf("%d%d", &l, &r);
    178     printf("%d", l == r ? l : 2);
    179 }
    180 ```
    181 
    182 Tutorial is loading...
    183 
    184 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii")
    185 
    186 Time Complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    187 
    188 Time Complexity: ![](https://espresso.codeforces.com/2677536d7d4670cf01e28975db45fa457981c8a1.png)
    189 
    190 Memory complexity: ![](https://espresso.codeforces.com/2677536d7d4670cf01e28975db45fa457981c8a1.png)
    191 
    192 **python3**
    193 
    194 ```
    195 print(("aabb" * 50000)[:int(input())])
    196 ```
    197 
    198 **C++**
    199 
    200 ```
    201 int N;
    202 int main()
    203 {
    204 	scanf("%d", &N);
    205 	for (int i = 0; i < N; i++)
    206 		putchar(i & 2 ? 'b' : 'a');
    207 	puts("");
    208 }
    209 ```
    210 
    211 Tutorial is loading...
    212 
    213 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii")
    214 
    215 Time Complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    216 
    217 Time Complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    218 
    219 Memory complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    220 
    221 **python3**
    222 
    223 ```
    224 print((int(input())-1)//2)
    225 ```
    226 
    227 **C++**
    228 
    229 ```
    230 int main(){
    231 	int n;
    232 	scanf("%d", &n);
    233 	printf("%d\n", (n-1)/2);
    234 }
    235 ```
    236 
    237 Tutorial is loading...
    238 
    239 From: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA"), Writer: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA")
    240 
    241 Time Complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    242 
    243 Time Complexity: ![](https://espresso.codeforces.com/2677536d7d4670cf01e28975db45fa457981c8a1.png)
    244 
    245 Memory complexity: ![](https://espresso.codeforces.com/2677536d7d4670cf01e28975db45fa457981c8a1.png)
    246 
    247 **python3**
    248 
    249 ```
    250 s = input()
    251 cnt = 0
    252 m=10**9 + 7
    253 t = 0
    254 
    255 for i in range(len(s)):
    256 	if s[~i] == 'a':
    257 		cnt = (cnt+t)%m
    258 		t = (t*2)%m
    259 	else:
    260 		t += 1
    261 print(cnt)
    262 ```
    263 
    264 **C++**
    265 
    266 ```
    267 int c,d,i,n,m,k,x,j=1000000007;
    268 string s;
    269 main(){
    270 	cin>>s;
    271 	for(i=s.size()-1;i>=0;i--){
    272 		if(s[i]=='b')c++;else{
    273 			k+=c;c*=2;k%=j;c%=j;
    274 		}
    275 	}
    276 	cout<<k;
    277 }
    278 ```
    279 
    280 Tutorial is loading...
    281 
    282 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii")
    283 
    284 Time Complexity: ![](https://espresso.codeforces.com/55d6782e50e4b107b6f984a3997c5a1951793b6c.png)
    285 
    286 Memory complexity: ![](https://espresso.codeforces.com/57ef0bd235bc9687085cbde72e95871fc04712a4.png)
    287 
    288 **C++**
    289 
    290 ```
    291 //              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\
    292 
    293 int const N = 3e5 + 10 ;
    294 int n , m , ans = 1 , res[N] ;
    295 vector <int> g[N] , vec[N] ;
    296 
    297 inline bool cmp (int a , int b) {
    298 	return res[a] < res[b] ;
    299 }
    300 
    301 void dfs (int v , int par = -1) {
    302 	int col = ans  , p = (int)vec[v].size() - 1 ;
    303 
    304 	sort(vec[v].begin() , vec[v].end() , cmp) ;
    305 
    306 	for (int x : vec[v]) {
    307 		if (res[x]) {
    308 			continue ;
    309 		}
    310 
    311 		while (p >= 0 && col == res[vec[v][p]]) {			
    312 			col -- ;
    313 			p -- ;
    314 		}
    315 
    316 		res[x] = col ;
    317 		col -- ;
    318 	
    319 	}
    320 	
    321 	for (int u : g[v]) {
    322 		if (u != par) {
    323 			dfs(u , v) ;
    324 		}
    325 	}
    326 }
    327 
    328 int main(){
    329 	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
    330 
    331 	cin >> n >> m ;
    332 	
    333 	for (int i = 0 ; i < n ; i ++) {
    334 		int sz ;
    335 		cin >> sz ;
    336 
    337 		ans = max(ans , sz) ;
    338 
    339 		while (sz --) {
    340 			int x ;
    341 			cin >> x ;
    342 			x -- ;
    343 			vec[i].push_back(x) ;
    344 		}
    345 	}
    346 
    347 	for (int i = 0 ; i < n - 1 ; i ++) {
    348 		int u , v ;
    349 		cin >> u >> v ;
    350 		u -- , v -- ;
    351 
    352 		g[u].push_back(v) ;
    353 		g[v].push_back(u) ;
    354 	}
    355 
    356 	dfs(0) ;
    357 
    358 	cout << ans << '\n' ;
    359 
    360 	for (int i = 0 ; i < m ; i ++) {
    361 		cout << max(res[i] , 1) << ' ' ;
    362 	}
    363 	cout << '\n' ;
    364 }
    365 ```
    366 
    367 Time Complexity: ![](https://espresso.codeforces.com/275cc471d094b65c3aac2b6d8128fb24757a0e31.png)
    368 
    369 Memory complexity: ![](https://espresso.codeforces.com/57ef0bd235bc9687085cbde72e95871fc04712a4.png)
    370 
    371 **C++**
    372 
    373 ```
    374 vector <int> Vs[300050];
    375 vector <int> conn[300050];
    376 
    377 int ans[300050];
    378 bool chk[500050];
    379 bool dchk[300050];
    380 vector <int> Vu;
    381 void DFS(int n) {
    382 	dchk[n] = true;
    383 
    384 	for (auto it : Vs[n]) {
    385 		if (ans[it]) chk[ans[it]] = true;
    386 		else Vu.push_back(it);
    387 	}
    388 
    389 	int a = 1;
    390 	for (auto it : Vu) {
    391 		while (chk[a]) a++;
    392 		ans[it] = a++;
    393 	}
    394 	for (auto it : Vs[n]) chk[ans[it]] = false;
    395 	Vu.clear();
    396 
    397 	for (auto it : conn[n]) {
    398 		if (dchk[it]) continue;
    399 		DFS(it);
    400 	}
    401 }
    402 int main() {
    403 	int N, M, i;
    404 	scanf("%d %d", &N, &M);
    405 	for (i = 1; i <= N; i++) {
    406 		int t1, t2;
    407 		scanf("%d", &t1);
    408 		while (t1--) {
    409 			scanf("%d", &t2);
    410 			Vs[i].push_back(t2);
    411 		}
    412 	}
    413 	for (i = 1; i < N; i++) {
    414 		int t1, t2;
    415 		scanf("%d %d", &t1, &t2);
    416 		conn[t1].push_back(t2);
    417 		conn[t2].push_back(t1);
    418 	}
    419 	DFS(1);
    420 
    421 	int mx = 0;
    422 	for (i = 1; i <= M; i++) {
    423 		mx = max(mx, ans[i]);
    424 		if (ans[i] == 0) ans[i] = 1;
    425 	}
    426 	mx = max(mx, 1);
    427 	printf("%d\n", mx);
    428 	for (i = 1; i <= M; i++) printf("%d ", ans[i]);
    429 	
    430 	return !printf("\n");
    431 }
    432 ```
    433 
    434 Tutorial is loading...
    435 
    436 From: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA"), Writer: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA")
    437 
    438 Time Complexity: ![](https://espresso.codeforces.com/999151cc0f2d5f5689f5b39a292f55e100b1920a.png)
    439 
    440 Memory complexity: ![](https://espresso.codeforces.com/2677536d7d4670cf01e28975db45fa457981c8a1.png)
    441 
    442 **C++**
    443 
    444 ```
    445 using namespace std ;
    446 
    447 #define int long long
    448 
    449 const int MAXN = 1e5 + 100 ;
    450 
    451 vector<int>ver[MAXN] , com[MAXN] , ps[MAXN] ; 
    452 int vis[MAXN] , dis[MAXN] ; 
    453 int mxr , mxid ; 
    454 void dfs(int v , int col = -1 , int h = 0 , int par = -1){
    455 	vis[v] = max(vis[v] , col) ; 
    456 	if(mxr < h)mxid = v , mxr = h ; 
    457 	dis[v] = max(h , dis[v]) ; 
    458 	if(col > 0)com[col] . push_back(dis[v]) ; 
    459 	for(auto u : ver[v]){
    460 		if(u == par)continue ; 
    461 		dfs(u , col , h + 1 , v) ; 
    462 	}
    463 }
    464 map<pair<int , int> , int> check ;
    465 int32_t main(){
    466     ios_base::sync_with_stdio(0) ;
    467     cin . tie(0) ; cout . tie(0) ;
    468     int n , m , q ; cin >> n >> m >> q ; 
    469     for(int i = 0 ; i < m ; i ++){
    470     	int x , y ; cin >> x >> y ; 
    471     	x -- , y -- ; 
    472     	ver[x] . push_back(y) ; 
    473     	ver[y] . push_back(x) ;
    474     }
    475     int cnt = 0 ; 
    476     for(int i = 0 ; i < n ; i ++){
    477     	if(vis[i])continue ; 
    478     	mxr = 0 , mxid = i ; 
    479     	dfs(i) ; 
    480     	mxr = 0 ; 
    481     	dfs(mxid) ;
    482     	dfs(mxid , ++ cnt) ; sort(com[cnt] . begin() , com[cnt] . end()) ; 
    483     	ps[cnt] . push_back(0) ; 
    484     	for(auto v : com[cnt])ps[cnt] . push_back(ps[cnt] . back() + v) ; 
    485     }
    486 	cout << fixed << setprecision(10) ;
    487     while(q --){
    488     	int x , y ; cin >> x >> y ; 
    489     	x -- , y -- ; x = vis[x] ; y = vis[y] ; 
    490     	if(com[x] . size() > com[y] . size())swap(x , y) ; 
    491     	if(x == y){cout << -1 << '\n' ; continue ; }
    492     	if(check[{x , y}] > 0){cout << double(check[{x , y}]) / (1ll * com[x] . size() * com[y] . size()) << '\n' ; continue ; }
    493     	int ans = 0 , mxd = max(com[x] . back() , com[y] . back()) ; 
    494     	for(auto v : com[x]){
    495     		int num = lower_bound(com[y] . begin() , com[y] . end() , mxd - v - 1) - com[y] . begin() ; 
    496     		ans += num * mxd + (com[y] . size() - num) *  (v + 1) + ps[y] . back() - ps[y][num] ; 
    497     	}
    498     	check[{x , y}] = ans ; 
    499     	cout << double(check[{x , y}]) / (1ll * com[x] . size() * com[y] . size()) << '\n' ; 
    500     }
    501 }
    502 ```
    503 
    504 Tutorial is loading...
    505 
    506 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii")
    507 
    508 Time Complexity: ![](https://espresso.codeforces.com/c6b5efcfa6a58da30a590e54e2e774b5e0e75beb.png)
    509 
    510 Memory complexity: ![](https://espresso.codeforces.com/e103a5f3a601f687f5bdaa09677d43b8ad375a1f.png)
    511 
    512 **C++**
    513 
    514 ```
    515 int n;
    516 
    517 int main()
    518 {
    519 	scanf("%d",&n);
    520 	if(n%4>1)return printf("NO\n"),0;
    521 	printf("YES\n");
    522 	for(int i=1;i<n;i+=4)
    523 	{
    524 		if(n%4)printf("%d %d\n%d %d\n%d %d\n",i+2,n,i+2,i+3,i+3,n);
    525 		else printf("%d %d\n",i+2,i+3);
    526 		printf("%d %d\n",i,i+2);
    527 		printf("%d %d\n",i+1,i+3);
    528 		printf("%d %d\n",i+1,i+2);
    529 		printf("%d %d\n",i,i+3);
    530 		if(n%4)printf("%d %d\n%d %d\n%d %d\n",i,n,i,i+1,i+1,n);
    531 		else printf("%d %d\n",i,i+1);
    532 	}
    533 	for(int i=1;i<n;i+=4)
    534 		for(int j=i+4;j<n;j+=4)
    535 		{
    536 			printf("%d %d\n",i+3,j+2);
    537 			printf("%d %d\n",i+2,j+2);
    538 			printf("%d %d\n",i+3,j+1);
    539 			printf("%d %d\n",i,j+1);
    540 			printf("%d %d\n",i+1,j+3);
    541 			printf("%d %d\n",i+2,j+3);
    542 			printf("%d %d\n",i+1,j+2);
    543 			printf("%d %d\n",i+1,j+1);
    544 			printf("%d %d\n",i+3,j);
    545 			printf("%d %d\n",i+3,j+3);
    546 			printf("%d %d\n",i,j+2);
    547 			printf("%d %d\n",i,j+3);
    548 			printf("%d %d\n",i+2,j);
    549 			printf("%d %d\n",i+2,j+1);
    550 			printf("%d %d\n",i+1,j);
    551 			printf("%d %d\n",i,j);
    552 		}
    553 	return 0;
    554 }
    555 ```
    556 
    557 Tutorial is loading...
    558 
    559 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [amsen](/profile/amsen "Candidate Master amsen")
    560 
    561 Time Complexity: ![](https://espresso.codeforces.com/b22244af0e609f6f77f671742f4fc36b47f24ccd.png)
    562 
    563 Memory complexity: ![](https://espresso.codeforces.com/9a5f3d3d29b06b787e6517d45d2c81fd99a7afc3.png)
    564 
    565 **Java8**
    566 
    567 ```
    568 import java.io.OutputStream;
    569 import java.io.IOException;
    570 import java.io.InputStream;
    571 import java.io.OutputStream;
    572 import java.io.PrintWriter;
    573 import java.io.BufferedWriter;
    574 import java.util.InputMismatchException;
    575 import java.io.IOException;
    576 import java.util.Stack;
    577 import java.util.ArrayList;
    578 import java.util.List;
    579 import java.util.stream.Stream;
    580 import java.util.Vector;
    581 import java.io.Writer;
    582 import java.io.OutputStreamWriter;
    583 import java.util.BitSet;
    584 import java.io.InputStream;
    585 
    586 /**
    587  * Built using CHelper plug-in
    588  * Actual solution is at the top
    589  */
    590 public class Main {
    591     public static void main(String[] args) {
    592         InputStream inputStream = System.in;
    593         OutputStream outputStream = System.out;
    594         InputReader in = new InputReader(inputStream);
    595         OutputWriter out = new OutputWriter(outputStream);
    596         TaskF solver = new TaskF();
    597         solver.solve(1, in, out);
    598         out.close();
    599     }
    600 
    601     static class TaskF {
    602         public int mod = 1000000007;
    603         public int n;
    604         public int a;
    605         public int b;
    606         public char[][] adj;
    607         public List<Integer>[] graph;
    608 
    609         public void solve(int testNumber, InputReader in, OutputWriter out) {
    610             n = in.nextInt();
    611             a = in.nextInt();
    612             b = in.nextInt();
    613             adj = new char[n][n];
    614             graph = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new);
    615             for (int i = 0; i < n; i++) adj[i] = in.next().toCharArray();
    616             for (int i = 0; i < n; i++) {
    617                 for (int j = 0; j < n; j++) {
    618                     if (adj[i][j] == '1') {
    619                         graph[i].add(j);
    620                     }
    621                 }
    622             }
    623             List<List<Integer>> comp = new SCCTarjan().scc(graph);
    624             boolean[][] can = new boolean[n][];
    625             int[] low = new int[n];
    626             for (int i = 0; i < n; i++) {
    627                 int q = in.nextInt();
    628                 char[] w = in.next().toCharArray();
    629                 can[i] = new boolean[q];
    630                 for (int j = 0; j < q; j++) {
    631                     can[i][j] = w[j] == '1';
    632                     if (can[i][j]) low[i]++;
    633                 }
    634             }
    635             int[] wcomp = new int[n];
    636             int idx = 0;
    637             List<BitSet> bb = new ArrayList<>();
    638             List<Integer> bs = new ArrayList<>();
    639             for (List<Integer> gg : comp) {
    640                 int gcd = 0;
    641                 for (int x : gg) {
    642                     gcd = Utils.gcd(gcd, can[x].length);
    643                     wcomp[x] = idx;
    644                 }
    645                 idx++;
    646                 BitSet d = new BitSet(gcd);
    647                 bs.add(gcd);
    648                 bb.add(d);
    649                 for (int x : gg) {
    650                     for (int i = 0; i < can[x].length; i++) {
    651                         if (can[x][i]) {
    652                             d.set(i % gcd, true);
    653                         }
    654                     }
    655                 }
    656             }
    657 
    658             for (int kk = comp.size() - 1; kk > 0; kk--) {
    659                 int g = Utils.gcd(bs.get(kk), bs.get(kk - 1));
    660                 BitSet ww = new BitSet(g);
    661                 for (int i = 0; i < bs.get(kk); i += g) {
    662                     ww.or(bb.get(kk).get(i, i + g));
    663                 }
    664                 for (int i = 0; i < bs.get(kk - 1); i++) {
    665                     if (ww.get(i % g)) {
    666                         bb.get(kk - 1).set(i, true);
    667                     }
    668                 }
    669             }
    670             int[] high = new int[n];
    671             for (int i = 0; i < n; i++) {
    672                 for (int j = 0; j < can[i].length; j++) {
    673                     if (bb.get(wcomp[i]).get(j % bs.get(wcomp[i])))
    674                         high[i]++;
    675                 }
    676             }
    677             long ret = 0;
    678             int[][] comb = Utils.getComb(n + 1, mod);
    679             for (int lowest = 0; lowest < n; lowest++) {
    680                 int countabove = 0;
    681                 for (int other = 0; other < n; other++) {
    682                     if (other == lowest) continue;
    683                     if (low[other] > high[lowest]) {
    684                         countabove++;
    685                     }
    686                 }
    687                 if (countabove >= a) {
    688                     continue;
    689                 }
    690                 int canbig = 0;
    691                 for (int other = 0; other < n; other++) {
    692                     if (other == lowest) continue;
    693                     if (low[other] <= high[lowest] && (high[other] > high[lowest] || (high[other] == high[lowest] && other > lowest))) {
    694                         canbig++;
    695                     }
    696                 }
    697 
    698                 for (int take = 0; take < b && take <= canbig && take + countabove < a; take++) {
    699                     ret = (ret + 1L * comb[canbig][take] * comb[countabove][b - take - 1]) % mod;
    700                 }
    701             }
    702             out.println(ret);
    703         }
    704 
    705     }
    706 
    707     static class OutputWriter {
    708         private final PrintWriter writer;
    709 
    710         public OutputWriter(OutputStream outputStream) {
    711             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    712         }
    713 
    714         public OutputWriter(Writer writer) {
    715             this.writer = new PrintWriter(writer);
    716         }
    717 
    718         public void close() {
    719             writer.close();
    720         }
    721 
    722         public void println(long i) {
    723             writer.println(i);
    724         }
    725 
    726     }
    727 
    728     static class Utils {
    729         public static int gcd(int a, int b) {
    730             return b == 0 ? a : gcd(b, a % b);
    731         }
    732 
    733         public static int[][] getComb(int sz, int mod) {
    734             int[][] comb = new int[sz][sz];
    735             for (int i = 0; i < sz; i++) {
    736                 comb[i][0] = 1;
    737                 for (int j = 1; j <= i; j++) {
    738                     comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    739                     if (comb[i][j] >= mod) comb[i][j] -= mod;
    740                 }
    741             }
    742             return comb;
    743         }
    744 
    745     }
    746 
    747     static class InputReader {
    748         private InputStream stream;
    749         private byte[] buf = new byte[1024];
    750         private int curChar;
    751         private int numChars;
    752 
    753         public InputReader(InputStream stream) {
    754             this.stream = stream;
    755         }
    756 
    757         public int read() {
    758             if (this.numChars == -1) {
    759                 throw new InputMismatchException();
    760             } else {
    761                 if (this.curChar >= this.numChars) {
    762                     this.curChar = 0;
    763 
    764                     try {
    765                         this.numChars = this.stream.read(this.buf);
    766                     } catch (IOException var2) {
    767                         throw new InputMismatchException();
    768                     }
    769 
    770                     if (this.numChars <= 0) {
    771                         return -1;
    772                     }
    773                 }
    774 
    775                 return this.buf[this.curChar++];
    776             }
    777         }
    778 
    779         public int nextInt() {
    780             int c;
    781             for (c = this.read(); isSpaceChar(c); c = this.read()) {
    782                 ;
    783             }
    784 
    785             byte sgn = 1;
    786             if (c == 45) {
    787                 sgn = -1;
    788                 c = this.read();
    789             }
    790 
    791             int res = 0;
    792 
    793             while (c >= 48 && c <= 57) {
    794                 res *= 10;
    795                 res += c - 48;
    796                 c = this.read();
    797                 if (isSpaceChar(c)) {
    798                     return res * sgn;
    799                 }
    800             }
    801 
    802             throw new InputMismatchException();
    803         }
    804 
    805         public String next() {
    806             int c;
    807             while (isSpaceChar(c = this.read())) {
    808                 ;
    809             }
    810 
    811             StringBuilder result = new StringBuilder();
    812             result.appendCodePoint(c);
    813 
    814             while (!isSpaceChar(c = this.read())) {
    815                 result.appendCodePoint(c);
    816             }
    817 
    818             return result.toString();
    819         }
    820 
    821         public static boolean isSpaceChar(int c) {
    822             return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    823         }
    824 
    825     }
    826 
    827     static class SCCTarjan {
    828         List<Integer>[] graph;
    829         boolean[] visited;
    830         Stack<Integer> stack;
    831         int time;
    832         int[] lowlink;
    833         List<List<Integer>> components;
    834 
    835         public List<List<Integer>> scc(List<Integer>[] graph) {
    836             int n = graph.length;
    837             this.graph = graph;
    838             visited = new boolean[n];
    839             stack = new Stack<>();
    840             time = 0;
    841             lowlink = new int[n];
    842             components = new ArrayList<>();
    843 
    844             for (int u = 0; u < n; u++)
    845                 if (!visited[u])
    846                     dfs(u);
    847 
    848             return components;
    849         }
    850 
    851         void dfs(int u) {
    852             lowlink[u] = time++;
    853             visited[u] = true;
    854             stack.add(u);
    855             boolean isComponentRoot = true;
    856 
    857             for (int v : graph[u]) {
    858                 if (!visited[v])
    859                     dfs(v);
    860                 if (lowlink[u] > lowlink[v]) {
    861                     lowlink[u] = lowlink[v];
    862                     isComponentRoot = false;
    863                 }
    864             }
    865 
    866             if (isComponentRoot) {
    867                 List<Integer> component = new ArrayList<>();
    868                 while (true) {
    869                     int x = stack.pop();
    870                     component.add(x);
    871                     lowlink[x] = Integer.MAX_VALUE;
    872                     if (x == u)
    873                         break;
    874                 }
    875                 components.add(component);
    876             }
    877         }
    878 
    879     }
    880 }
    881 ```
    882 
    883 **C++**
    884 
    885 ```
    886 #define pb push_back
    887 #define mp make_pair
    888 #define all(x) (x).begin(),(x).end()
    889 #define fi first
    890 #define se second
    891 
    892 const int maxn = 5005;
    893 const int maxelem = 2000006;
    894 const int MOD = 1000000007;
    895 
    896 char gr[maxn][maxn];
    897 string init[maxn];
    898 int mincnt[maxn], maxcnt[maxn];
    899 int c[maxn][maxn];
    900 int n, m, A, B;
    901 bool was[maxn];
    902 vector<int> order;
    903 vector<bool> can[maxn];
    904 bool nowcan[maxelem];
    905 char s[maxelem];
    906 int gcd[maxn];
    907 vector<int> comp[maxn];
    908 
    909 void preorder(int cur)
    910 {
    911     if (was[cur]) return;
    912     was[cur] = true;
    913     for (int i = 0; i < n; i++) if (gr[cur][i] == '1') preorder(i);
    914     order.pb(cur);
    915 }
    916 
    917 void color(int cur, int cc)
    918 {
    919     if (was[cur]) return;
    920     was[cur] = true;
    921     gcd[cc] = __gcd(gcd[cc], (int)init[cur].size());
    922     comp[cc].pb(cur);
    923     for (int i = 0; i < n; i++) if (gr[i][cur] == '1') color(i, cc);
    924 }
    925 
    926 int getc(int n, int k)
    927 {
    928     if (k < 0 || k > n) return 0;
    929     return c[n][k];
    930 }
    931 
    932 int main()
    933 {
    934     scanf("%d%d%d", &n, &A, &B);
    935     for (int i = 0; i < n; i++)
    936     {
    937         scanf("%s", gr[i]);
    938     }
    939     for (int i = 0; i < n; i++)
    940     {
    941         scanf("%*d");
    942         scanf("%s", s);
    943         init[i] = string(s);
    944         for (int j = 0; j < (int)init[i].size(); j++) mincnt[i] += init[i][j] == '1';
    945         maxcnt[i] = mincnt[i];
    946     }
    947     for (int i = 0; i < n; i++) if (!was[i]) preorder(i);
    948     memset(was, 0, sizeof(was));
    949     int cc = 0;
    950     reverse(all(order));
    951     for (auto t : order) if (!was[t])
    952     {
    953         color(t, cc);
    954         cc++;
    955     }
    956     for (int i = 0; i < cc; i++)
    957     {
    958         can[i].resize(gcd[i]);
    959         for (int j = 0; j < gcd[i]; j++) can[i][j] = false;
    960         for (auto t : comp[i])
    961         {
    962             for (int j = 0; j < (int)init[t].size(); j++) if (init[t][j] == '1') can[i][j % gcd[i]] = true;
    963         }
    964     }
    965     for (int i = 0; i < cc - 1; i++)
    966     {
    967         int g = __gcd(gcd[i], gcd[i + 1]);
    968         for (int j = 0; j < g; j++) nowcan[j] = false;
    969         for (int j = 0; j < gcd[i]; j++) nowcan[j % g] |= can[i][j];
    970         for (int j = 0; j < gcd[i + 1]; j++) can[i  + 1][j] = (can[i  + 1][j] | nowcan[j % g]);
    971     }
    972     for (int i = 0; i < cc; i++)
    973     {
    974         for (auto t : comp[i])
    975         {
    976             for (int j = 0; j < (int)init[t].size(); j++) if (init[t][j] == '0' && can[i][j % gcd[i]]) maxcnt[t]++;
    977         }
    978     }
    979     
    980     c[0][0] = 1;
    981     for (int i = 1; i <= n; i++)
    982     {
    983         c[i][0] = 1;
    984         for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
    985     }
    986     int answer = 0;
    987     for (int i = 0; i < n; i++)
    988     {
    989         int cntbigger = 0;
    990         int cntupper = 0;
    991         for (int j = 0; j < n; j++) if (i != j)
    992         {
    993             if (mincnt[j] > maxcnt[i]) cntbigger++;
    994             else if (maxcnt[j] > maxcnt[i] || (maxcnt[j] == maxcnt[i] && j > i)) cntupper++;
    995         }
    996         if (cntbigger >= A) continue;
    997         for (int j = max(0, B - 1 - cntbigger); j <= cntupper && j + cntbigger + 1 <= A && j + 1 <= B; j++)
    998         {
    999             answer = (answer + (ll)getc(cntupper, j) * getc(cntbigger, B - 1 - j)) % MOD;
   1000         }
   1001     }
   1002     cout << answer << endl;
   1003     return 0;
   1004 }	
   1005 ```
   1006 
   1007 **C++**
   1008 
   1009 ```
   1010 #include <bits/stdc++.h>
   1011 #define xx first
   1012 #define yy second
   1013 #define mp make_pair
   1014 #define pb push_back
   1015 #define fill( x, y ) memset( x, y, sizeof x )
   1016 #define copy( x, y ) memcpy( x, y, sizeof x )
   1017 using namespace std;
   1018 
   1019 typedef long long LL;
   1020 typedef pair < int, int > pa;
   1021 
   1022 inline int read()
   1023 {
   1024 	int sc = 0, f = 1; char ch = getchar();
   1025 	while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }
   1026 	while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();
   1027 	return sc * f;
   1028 }
   1029 
   1030 const int MAXN = 5005;
   1031 const int MAXM = 2000005;
   1032 const int mod = 1e9 + 7;
   1033 
   1034 int n, a, b, len[MAXN], can[MAXM], id_cnt, L[MAXN], R[MAXN], C[MAXN][MAXN];
   1035 int dfn[MAXN], scc[MAXN], low[MAXN], tim, num, st[MAXN], top, w[MAXN], ans;
   1036 vector < int > G[MAXN], id[MAXN], scc_bit[MAXN], v[MAXN];
   1037 char ch[MAXM];
   1038 
   1039 inline void inc(int &x, int y) { x += y; if( x >= mod ) x -= mod; }
   1040 
   1041 inline void dfs(int x)
   1042 {
   1043 	dfn[ x ] = low[ x ] = ++tim; st[ ++top ] = x;
   1044 	for( auto y : G[ x ] )
   1045 		if( !dfn[ y ] ) dfs( y ), low[ x ] = min( low[ x ], low[ y ] );
   1046 		else if( !scc[ y ] ) low[ x ] = min( low[ x ], dfn[ y ] );
   1047 	if( dfn[ x ] == low[ x ] )
   1048 	{
   1049 		num++; int t = 0;
   1050 		while( t ^ x )
   1051 		{
   1052 			scc[ t = st[ top-- ] ] = num;
   1053 			w[ num ] = __gcd( w[ num ], len[ t ] );
   1054 			v[ num ].pb( t );
   1055 		}
   1056 		scc_bit[ num ].resize( w[ num ] );
   1057 		for( auto y : v[ num ] )
   1058 			for( int d = 0 ; d < len[ y ] ; d++ ) if( can[ id[ y ][ d ] ] ) scc_bit[ num ][ d % w[ num ] ] = 1;
   1059 	}
   1060 }
   1061 
   1062 int main()
   1063 {
   1064 #ifdef wxh010910
   1065 	freopen( "data.in", "r", stdin );
   1066 #endif
   1067 	n = read(), a = read(), b = read();
   1068 	for( int i = 0 ; i <= n ; i++ )
   1069 	{
   1070 		C[ i ][ 0 ] = 1;
   1071 		for( int j = 1 ; j <= i ; j++ ) inc( C[ i ][ j ] = C[ i - 1 ][ j ], C[ i - 1 ][ j - 1 ] );
   1072 	}
   1073 	for( int i = 1 ; i <= n ; i++ )
   1074 	{
   1075 		scanf( "%s", ch + 1 );
   1076 		for( int j = 1 ; j <= n ; j++ ) if( ch[ j ] == '1' ) G[ i ].pb( j );
   1077 	}
   1078 	for( int i = 1 ; i <= n ; i++ )
   1079 	{
   1080 		len[ i ] = read(); scanf( "%s", ch );
   1081 		for( int j = 0 ; j < len[ i ] ; j++ ) id[ i ].pb( ++id_cnt ), can[ id_cnt ] = ch[ j ] == '1', L[ i ] += can[ id_cnt ];
   1082 	}
   1083 	for( int i = 1 ; i <= n ; i++ ) if( !dfn[ i ] ) dfs( i );
   1084 	for( int i = num ; i > 1 ; i-- )
   1085 	{
   1086 		int g = __gcd( w[ i ], w[ i - 1 ] );
   1087 		w[ i - 1 ] = g;
   1088 		for( int j = 0 ; j < w[ i ] ; j++ )	scc_bit[ i - 1 ][ j % g ] |= scc_bit[ i ][ j ];
   1089 	}
   1090 	for( int i = 1 ; i <= n ; i++ )
   1091 	{
   1092 		int x = scc[ i ];
   1093 		for( int j = 0 ; j < len[ i ] ; j++ )
   1094 			R[ i ] += scc_bit[ x ][ j % w[ x ] ];
   1095 	}
   1096 	for( int i = 1 ; i <= n ; i++ )
   1097 	{
   1098 		int t1 = 0, t2 = 0;
   1099 		for( int j = 1 ; j <= n ; j++ ) if( L[ j ] > R[ i ] ) t1++;
   1100 		if( t1 >= a ) continue;
   1101 		for( int j = 1 ; j <= n ; j++ ) if( L[ j ] <= R[ i ] && mp( R[ j ], j ) > mp( R[ i ], i ) ) t2++;
   1102 		for( int j = 0 ; j < b && j <= t2 && j + t1 < a ; j++ )
   1103 		   inc( ans, 1LL * C[ t2 ][ j ] * C[ t1 ][ b - j - 1 ] % mod );	
   1104 	}
   1105 	return printf( "%d\n", ans ), 0;
   1106 }
   1107 ```
   1108 
   1109 As my good friend, [Arpa](/profile/Arpa "Candidate Master Arpa"), did, let me share with you a perfect poem of one of our best poet you might know, Molavi:
   1110 
   1111 .......................................................................................بند بگسل، باش آزاد ای پسر ** چند باشی بند سیم و بند زر
   1112 
   1113 *O* *son*,  *burst* *thy* *chains* *and* *be* *free*! *How* *long* *wilt* *thou* *be* *a* *bondsman* *to* *silver* *and* *gold*?
   1114 
   1115 .......................................................................................گر بریزی بحر را در کوزه‌‌ای ** چند گنجد قسمت یک روزه‌‌ای‌‌
   1116 
   1117 *If* *thou* *pour* *the* *sea* *into* *a* *pitcher*,  *how* *much* *will* *it* *hold*? *One* *day*'*s* *store*.
   1118 
   1119 ..................................................................................... کوزه‌‌ی چشم حریصان پر نشد ** تا صدف قانع نشد پر در نشد
   1120 
   1121 *The* *pitcher*,  *the* *eye* *of* *the* *covetous*,  *never* *becomes* *full*:  *the* *oyster* - *shell* *is* *not* *filled* *with* *pearls* *until* *it* *is* *contented*.
   1122 
   1123 .............................................................................. هر که را جامه ز عشقی چاک شد ** او ز حرص و عیب کلی پاک شد
   1124 
   1125 *He* (*alone*) *whose* *garment* *is* *rent* *by* *a* (*mighty*) *love* *is* *purged* *entirely* *of* *covetousness* *and* *defect*.