-
Notifications
You must be signed in to change notification settings - Fork 30
/
Copy pathCount subsequences.cpp
219 lines (136 loc) · 45.8 KB
/
Count subsequences.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
/*
Solution By Rahul Surana
***********************************
<div class="problem-description assessment-problem-description no-select"><div class="algorithm" data-id="eb2fc1a964ef44e9900806e2918ba5a8"><div class="float-left width-100 padding-bottom-10 lighter-border-bottom margin-bottom-20 margin-top-24"><div class="content-heading inline-block semi-bold margin-right-10">Question <div class="serial-number content-heading inline-block serial-number-eb2fc1a964ef44e9900806e2918ba5a8">2 <div class="weight-600 black-333 float-right inline-block"><div private_url_hash="eb2fc1a964ef44e9900806e2918ba5a8" class="algorithm-start-flow project-start-flow float-right inline-block padding-left-10 tool-tip flow-div-algorithm" title="See how to attempt this question."><i class="flow-help fa fa-question-circle font-size-16 light"></i> <div class="problem-score max-marks inline-block max-marks-eb2fc1a964ef44e9900806e2918ba5a8">Max. score: 100.00 <div class="clear"> <div class="problem-statement problem-statement-eb2fc1a964ef44e9900806e2918ba5a8"><div class="semi-bold margin-bottom-20">Count subsequences <div class="algorithm-problem complete-problem-statement dark"> You are given the following:
An array A of length N
An integer X
Task
Determine the number of subsequences of array A such that the following condition is satisfied:
If <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>i</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>i</mi><mi>K</mi></msub></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="14.357ex" height="2.93ex" viewBox="0 -802.1 6181.4 1261.4" role="img" focusable="false" style="vertical-align: -1.067ex;" aria-hidden="true"><defs><path stroke-width="1" id="E4-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="1" id="E4-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="1" id="E4-MJMAIN-2C" d="M78 35T78 60T94 103T137 121Q165 121 187 96T210 8Q210 -27 201 -60T180 -117T154 -158T130 -185T117 -194Q113 -194 104 -185T95 -172Q95 -168 106 -156T131 -126T157 -76T173 -3V9L172 8Q170 7 167 6T161 3T152 1T140 0Q113 0 96 17Z"></path><path stroke-width="1" id="E4-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="1" id="E4-MJMAIN-2E" d="M78 60Q78 84 95 102T138 120Q162 120 180 104T199 61Q199 36 182 18T139 0T96 17T78 60Z"></path><path stroke-width="1" id="E4-MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E4-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E4-MJMAIN-31" x="377" y="-291"></use><use xlink:href="#E4-MJMAIN-2C" x="903" y="0"></use><g transform="translate(1348,0)"><use xlink:href="#E4-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E4-MJMAIN-32" x="377" y="-291"></use></g><use xlink:href="#E4-MJMAIN-2C" x="2251" y="0"></use><use xlink:href="#E4-MJMAIN-2E" x="2696" y="0"></use><use xlink:href="#E4-MJMAIN-2E" x="3141" y="0"></use><use xlink:href="#E4-MJMAIN-2E" x="3587" y="0"></use><use xlink:href="#E4-MJMAIN-2E" x="4032" y="0"></use><use xlink:href="#E4-MJMAIN-2C" x="4477" y="0"></use><g transform="translate(4922,0)"><use xlink:href="#E4-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E4-MJMATHI-4B" x="377" y="-308"></use></g></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>i</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>i</mi><mi>K</mi></msub></math></span></span><script type="math/tex" id="MathJax-Element-4">i_1, i_2, ... .,i_K</script></span> is the indices in the subsequence, then <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mn>1</mn></msub><mo stretchy="false">]</mo><mo>&#x2295;</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mn>2</mn></msub><mo stretchy="false">]</mo><mo>&#x2295;</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>&#x2295;</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mi>K</mi></msub><mo stretchy="false">]</mo><mo stretchy="false">)</mo><mi mathvariant="normal">&#x0026;</mi><mi>X</mi><mo>=</mo><mn>0</mn></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="35.647ex" height="3.195ex" viewBox="0 -916.5 15347.8 1375.7" role="img" focusable="false" style="vertical-align: -1.067ex;" aria-hidden="true"><defs><path stroke-width="1" id="E5-MJMAIN-28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path><path stroke-width="1" id="E5-MJMATHI-41" d="M208 74Q208 50 254 46Q272 46 272 35Q272 34 270 22Q267 8 264 4T251 0Q249 0 239 0T205 1T141 2Q70 2 50 0H42Q35 7 35 11Q37 38 48 46H62Q132 49 164 96Q170 102 345 401T523 704Q530 716 547 716H555H572Q578 707 578 706L606 383Q634 60 636 57Q641 46 701 46Q726 46 726 36Q726 34 723 22Q720 7 718 4T704 0Q701 0 690 0T651 1T578 2Q484 2 455 0H443Q437 6 437 9T439 27Q443 40 445 43L449 46H469Q523 49 533 63L521 213H283L249 155Q208 86 208 74ZM516 260Q516 271 504 416T490 562L463 519Q447 492 400 412L310 260L413 259Q516 259 516 260Z"></path><path stroke-width="1" id="E5-MJMAIN-5B" d="M118 -250V750H255V710H158V-210H255V-250H118Z"></path><path stroke-width="1" id="E5-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="1" id="E5-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="1" id="E5-MJMAIN-5D" d="M22 710V750H159V-250H22V-210H119V710H22Z"></path><path stroke-width="1" id="E5-MJMAIN-2295" d="M56 250Q56 394 156 488T384 583Q530 583 626 485T722 250Q722 110 625 14T390 -83Q249 -83 153 14T56 250ZM364 542Q308 539 251 509T148 418T96 278V270H369V542H364ZM681 278Q675 338 650 386T592 462T522 509T458 535T412 542H409V270H681V278ZM96 222Q104 150 139 95T219 12T302 -29T366 -42H369V230H96V222ZM681 222V230H409V-42H412Q429 -42 456 -36T521 -10T590 37T649 113T681 222Z"></path><path stroke-width="1" id="E5-MJMAIN-32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path><path stroke-width="1" id="E5-MJMAIN-2E" d="M78 60Q78 84 95 102T138 120Q162 120 180 104T199 61Q199 36 182 18T139 0T96 17T78 60Z"></path><path stroke-width="1" id="E5-MJMATHI-4B" d="M285 628Q285 635 228 637Q205 637 198 638T191 647Q191 649 193 661Q199 681 203 682Q205 683 214 683H219Q260 681 355 681Q389 681 418 681T463 682T483 682Q500 682 500 674Q500 669 497 660Q496 658 496 654T495 648T493 644T490 641T486 639T479 638T470 637T456 637Q416 636 405 634T387 623L306 305Q307 305 490 449T678 597Q692 611 692 620Q692 635 667 637Q651 637 651 648Q651 650 654 662T659 677Q662 682 676 682Q680 682 711 681T791 680Q814 680 839 681T869 682Q889 682 889 672Q889 650 881 642Q878 637 862 637Q787 632 726 586Q710 576 656 534T556 455L509 418L518 396Q527 374 546 329T581 244Q656 67 661 61Q663 59 666 57Q680 47 717 46H738Q744 38 744 37T741 19Q737 6 731 0H720Q680 3 625 3Q503 3 488 0H478Q472 6 472 9T474 27Q478 40 480 43T491 46H494Q544 46 544 71Q544 75 517 141T485 216L427 354L359 301L291 248L268 155Q245 63 245 58Q245 51 253 49T303 46H334Q340 37 340 35Q340 19 333 5Q328 0 317 0Q314 0 280 1T180 2Q118 2 85 2T49 1Q31 1 31 11Q31 13 34 25Q38 41 42 43T65 46Q92 46 125 49Q139 52 144 61Q147 65 216 339T285 628Z"></path><path stroke-width="1" id="E5-MJMAIN-29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path><path stroke-width="1" id="E5-MJMAIN-26" d="M156 540Q156 620 201 668T302 716Q354 716 377 671T401 578Q401 505 287 386L274 373Q309 285 416 148L429 132L437 142Q474 191 543 309L562 341V349Q562 368 541 376T498 385H493V431H502L626 428Q709 428 721 431H727V385H712Q688 384 669 379T639 369T618 354T603 337T591 316T578 295Q537 223 506 176T464 117T454 104Q454 102 471 85T497 62Q543 24 585 24Q618 24 648 48T682 113V121H722V112Q721 94 714 75T692 32T646 -7T574 -22Q491 -19 414 42L402 51L391 42Q312 -22 224 -22Q144 -22 93 25T42 135Q42 153 46 169T55 197T74 225T96 249T125 278T156 308L195 347L190 360Q185 372 182 382T174 411T165 448T159 491T156 540ZM361 576Q361 613 348 646T305 679Q272 679 252 649T232 572Q232 497 255 426L259 411L267 420Q361 519 361 576ZM140 164Q140 103 167 64T240 24Q271 24 304 36T356 61T374 77Q295 156 235 262L220 292L210 310L193 293Q177 277 169 268T151 229T140 164Z"></path><path stroke-width="1" id="E5-MJMATHI-58" d="M42 0H40Q26 0 26 11Q26 15 29 27Q33 41 36 43T55 46Q141 49 190 98Q200 108 306 224T411 342Q302 620 297 625Q288 636 234 637H206Q200 643 200 645T202 664Q206 677 212 683H226Q260 681 347 681Q380 681 408 681T453 682T473 682Q490 682 490 671Q490 670 488 658Q484 643 481 640T465 637Q434 634 411 620L488 426L541 485Q646 598 646 610Q646 628 622 635Q617 635 609 637Q594 637 594 648Q594 650 596 664Q600 677 606 683H618Q619 683 643 683T697 681T738 680Q828 680 837 683H845Q852 676 852 672Q850 647 840 637H824Q790 636 763 628T722 611T698 593L687 584Q687 585 592 480L505 384Q505 383 536 304T601 142T638 56Q648 47 699 46Q734 46 734 37Q734 35 732 23Q728 7 725 4T711 1Q708 1 678 1T589 2Q528 2 496 2T461 1Q444 1 444 10Q444 11 446 25Q448 35 450 39T455 44T464 46T480 47T506 54Q523 62 523 64Q522 64 476 181L429 299Q241 95 236 84Q232 76 232 72Q232 53 261 47Q262 47 267 47T273 46Q276 46 277 46T280 45T283 42T284 35Q284 26 282 19Q279 6 276 4T261 1Q258 1 243 1T201 2T142 2Q64 2 42 0Z"></path><path stroke-width="1" id="E5-MJMAIN-3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path><path stroke-width="1" id="E5-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E5-MJMAIN-28" x="0" y="0"></use><use xlink:href="#E5-MJMATHI-41" x="389" y="0"></use><use xlink:href="#E5-MJMAIN-5B" x="1140" y="0"></use><g transform="translate(1418,0)"><use xlink:href="#E5-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E5-MJMAIN-31" x="377" y="-291"></use></g><use xlink:href="#E5-MJMAIN-5D" x="2321" y="0"></use><use xlink:href="#E5-MJMAIN-2295" x="2822" y="0"></use><use xlink:href="#E5-MJMATHI-41" x="3823" y="0"></use><use xlink:href="#E5-MJMAIN-5B" x="4573" y="0"></use><g transform="translate(4852,0)"><use xlink:href="#E5-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E5-MJMAIN-32" x="377" y="-291"></use></g><use xlink:href="#E5-MJMAIN-5D" x="5755" y="0"></use><use xlink:href="#E5-MJMAIN-2295" x="6033" y="0"></use><use xlink:href="#E5-MJMAIN-2E" x="6812" y="0"></use><use xlink:href="#E5-MJMAIN-2E" x="7257" y="0"></use><use xlink:href="#E5-MJMAIN-2E" x="7702" y="0"></use><use xlink:href="#E5-MJMAIN-2295" x="8147" y="0"></use><use xlink:href="#E5-MJMATHI-41" x="8926" y="0"></use><use xlink:href="#E5-MJMAIN-5B" x="9676" y="0"></use><g transform="translate(9955,0)"><use xlink:href="#E5-MJMATHI-69" x="0" y="0"></use><use transform="scale(0.914)" xlink:href="#E5-MJMATHI-4B" x="377" y="-308"></use></g><use xlink:href="#E5-MJMAIN-5D" x="11214" y="0"></use><use xlink:href="#E5-MJMAIN-29" x="11492" y="0"></use><use xlink:href="#E5-MJMAIN-26" x="11882" y="0"></use><use xlink:href="#E5-MJMATHI-58" x="12660" y="0"></use><use xlink:href="#E5-MJMAIN-3D" x="13790" y="0"></use><use xlink:href="#E5-MJMAIN-30" x="14847" y="0"></use></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mn>1</mn></msub><mo stretchy="false">]</mo><mo>⊕</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mn>2</mn></msub><mo stretchy="false">]</mo><mo>⊕</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>⊕</mo><mi>A</mi><mo stretchy="false">[</mo><msub><mi>i</mi><mi>K</mi></msub><mo stretchy="false">]</mo><mo stretchy="false">)</mo><mi mathvariant="normal">&</mi><mi>X</mi><mo>=</mo><mn>0</mn></math></span></span><script type="math/tex" id="MathJax-Element-5">(A[i_1] \oplus A[i_2] \oplus... \oplus A[i_K]) \& X = 0</script></span>, where <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#x2295;</mo></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="1.808ex" height="2.399ex" viewBox="0 -802.1 778.5 1032.8" role="img" focusable="false" style="vertical-align: -0.536ex;" aria-hidden="true"><defs><path stroke-width="1" id="E6-MJMAIN-2295" d="M56 250Q56 394 156 488T384 583Q530 583 626 485T722 250Q722 110 625 14T390 -83Q249 -83 153 14T56 250ZM364 542Q308 539 251 509T148 418T96 278V270H369V542H364ZM681 278Q675 338 650 386T592 462T522 509T458 535T412 542H409V270H681V278ZM96 222Q104 150 139 95T219 12T302 -29T366 -42H369V230H96V222ZM681 222V230H409V-42H412Q429 -42 456 -36T521 -10T590 37T649 113T681 222Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E6-MJMAIN-2295" x="0" y="0"></use></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo>⊕</mo></math></span></span><script type="math/tex" id="MathJax-Element-6">\oplus</script></span> represents Bitwise XOR operator and <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#x0026;</mi></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="1.808ex" height="2.664ex" viewBox="0 -916.5 778.5 1147.1" role="img" focusable="false" style="vertical-align: -0.536ex;" aria-hidden="true"><defs><path stroke-width="1" id="E7-MJMAIN-26" d="M156 540Q156 620 201 668T302 716Q354 716 377 671T401 578Q401 505 287 386L274 373Q309 285 416 148L429 132L437 142Q474 191 543 309L562 341V349Q562 368 541 376T498 385H493V431H502L626 428Q709 428 721 431H727V385H712Q688 384 669 379T639 369T618 354T603 337T591 316T578 295Q537 223 506 176T464 117T454 104Q454 102 471 85T497 62Q543 24 585 24Q618 24 648 48T682 113V121H722V112Q721 94 714 75T692 32T646 -7T574 -22Q491 -19 414 42L402 51L391 42Q312 -22 224 -22Q144 -22 93 25T42 135Q42 153 46 169T55 197T74 225T96 249T125 278T156 308L195 347L190 360Q185 372 182 382T174 411T165 448T159 491T156 540ZM361 576Q361 613 348 646T305 679Q272 679 252 649T232 572Q232 497 255 426L259 411L267 420Q361 519 361 576ZM140 164Q140 103 167 64T240 24Q271 24 304 36T356 61T374 77Q295 156 235 262L220 292L210 310L193 293Q177 277 169 268T151 229T140 164Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E7-MJMAIN-26" x="0" y="0"></use></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&</mi></math></span></span><script type="math/tex" id="MathJax-Element-7">\&</script></span> represents Bitwise AND operator.
Since, the number of subsequences can be large enough, output it modulo <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>10</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="7.623ex" height="3.195ex" viewBox="0 -1145.1 3282.1 1375.7" role="img" focusable="false" style="vertical-align: -0.536ex;" aria-hidden="true"><defs><path stroke-width="1" id="E8-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="1" id="E8-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path stroke-width="1" id="E8-MJMAIN-39" d="M352 287Q304 211 232 211Q154 211 104 270T44 396Q42 412 42 436V444Q42 537 111 606Q171 666 243 666Q245 666 249 666T257 665H261Q273 665 286 663T323 651T370 619T413 560Q456 472 456 334Q456 194 396 97Q361 41 312 10T208 -22Q147 -22 108 7T68 93T121 149Q143 149 158 135T173 96Q173 78 164 65T148 49T135 44L131 43Q131 41 138 37T164 27T206 22H212Q272 22 313 86Q352 142 352 280V287ZM244 248Q292 248 321 297T351 430Q351 508 343 542Q341 552 337 562T323 588T293 615T246 625Q208 625 181 598Q160 576 154 546T147 441Q147 358 152 329T172 282Q197 248 244 248Z"></path><path stroke-width="1" id="E8-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="1" id="E8-MJMAIN-37" d="M55 458Q56 460 72 567L88 674Q88 676 108 676H128V672Q128 662 143 655T195 646T364 644H485V605L417 512Q408 500 387 472T360 435T339 403T319 367T305 330T292 284T284 230T278 162T275 80Q275 66 275 52T274 28V19Q270 2 255 -10T221 -22Q210 -22 200 -19T179 0T168 40Q168 198 265 368Q285 400 349 489L395 552H302Q128 552 119 546Q113 543 108 522T98 479L95 458V455H55V458Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E8-MJMAIN-31"></use><use xlink:href="#E8-MJMAIN-30" x="500" y="0"></use><use transform="scale(0.914)" xlink:href="#E8-MJMAIN-39" x="1094" y="396"></use><use xlink:href="#E8-MJMAIN-2B" x="1780" y="0"></use><use xlink:href="#E8-MJMAIN-37" x="2781" y="0"></use></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>10</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></math></span></span><script type="math/tex" id="MathJax-Element-8">10^9+7</script></span>.
Notes
Assume 1- based indexing.
An array b is a sub-sequence of an array a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subsequence of itself.
Empty subsequence always satisfies the given condition.
Example
Assumptions
N = 4
X = 7
A[] = [5, 2, 7, 6]
Approach
Following subsequences satisfy the conditions:
[5, 2, 7]
Empty subsequence
Thus, the required answer is 2.
Function description
Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the required answer:
N : Represents the value of N
X : Represents the value of X
A : Represents the elements in array A
Input format
Note : This is the input format that you must use to provide custom input (available above the Compile and Test button).
The first line contains a single integer T , which denotes the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
For each test case:
The first line contains an integer N .
The second line contains an integer X .
The third line contains N space-separated integers denoting the array A .
Output format
For each test case in a new line, print the number of subsequences that satisfy the given condition modulo <span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>10</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="7.623ex" height="3.195ex" viewBox="0 -1145.1 3282.1 1375.7" role="img" focusable="false" style="vertical-align: -0.536ex;" aria-hidden="true"><defs><path stroke-width="1" id="E9-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="1" id="E9-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path stroke-width="1" id="E9-MJMAIN-39" d="M352 287Q304 211 232 211Q154 211 104 270T44 396Q42 412 42 436V444Q42 537 111 606Q171 666 243 666Q245 666 249 666T257 665H261Q273 665 286 663T323 651T370 619T413 560Q456 472 456 334Q456 194 396 97Q361 41 312 10T208 -22Q147 -22 108 7T68 93T121 149Q143 149 158 135T173 96Q173 78 164 65T148 49T135 44L131 43Q131 41 138 37T164 27T206 22H212Q272 22 313 86Q352 142 352 280V287ZM244 248Q292 248 321 297T351 430Q351 508 343 542Q341 552 337 562T323 588T293 615T246 625Q208 625 181 598Q160 576 154 546T147 441Q147 358 152 329T172 282Q197 248 244 248Z"></path><path stroke-width="1" id="E9-MJMAIN-2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path><path stroke-width="1" id="E9-MJMAIN-37" d="M55 458Q56 460 72 567L88 674Q88 676 108 676H128V672Q128 662 143 655T195 646T364 644H485V605L417 512Q408 500 387 472T360 435T339 403T319 367T305 330T292 284T284 230T278 162T275 80Q275 66 275 52T274 28V19Q270 2 255 -10T221 -22Q210 -22 200 -19T179 0T168 40Q168 198 265 368Q285 400 349 489L395 552H302Q128 552 119 546Q113 543 108 522T98 479L95 458V455H55V458Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E9-MJMAIN-31"></use><use xlink:href="#E9-MJMAIN-30" x="500" y="0"></use><use transform="scale(0.914)" xlink:href="#E9-MJMAIN-39" x="1094" y="396"></use><use xlink:href="#E9-MJMAIN-2B" x="1780" y="0"></use><use xlink:href="#E9-MJMAIN-37" x="2781" y="0"></use></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mn>10</mn><mn>9</mn></msup><mo>+</mo><mn>7</mn></math></span></span><script type="math/tex" id="MathJax-Element-9">10^9+7</script></span>.
Constraints
<span class="mathjax-latex"><span class="MathJax_Preview" style="color: inherit;"></span><span class="MathJax_SVG" id="MathJax-Element-10-Frame" tabindex="0" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mo>&#x2264;</mo><mi>T</mi><mo>&#x2264;</mo><mn>10</mn><mspace linebreak="newline" /><mn>1</mn><mo>&#x2264;</mo><mi>N</mi><mo>&#x2264;</mo><msup><mn>10</mn><mn>3</mn></msup><mspace linebreak="newline" /><mn>1</mn><mo>&#x2264;</mo><mi>X</mi><mo>&#x2264;</mo><msup><mn>10</mn><mn>3</mn></msup><mspace linebreak="newline" /><mn>0</mn><mo>&#x2264;</mo><mi>A</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>&#x2264;</mo><msup><mn>10</mn><mn>3</mn></msup></math>" role="presentation" style="font-size: 175%; display: inline-block; position: relative;"><svg xmlns:xlink="http://www.w3.org/1999/xlink" width="14.819ex" height="13.549ex" viewBox="0 -802.1 6380.3 5833.6" role="img" focusable="false" style="vertical-align: -11.686ex;" aria-hidden="true"><defs><path stroke-width="1" id="E10-MJMAIN-31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path stroke-width="1" id="E10-MJMAIN-2264" d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z"></path><path stroke-width="1" id="E10-MJMATHI-54" d="M40 437Q21 437 21 445Q21 450 37 501T71 602L88 651Q93 669 101 677H569H659Q691 677 697 676T704 667Q704 661 687 553T668 444Q668 437 649 437Q640 437 637 437T631 442L629 445Q629 451 635 490T641 551Q641 586 628 604T573 629Q568 630 515 631Q469 631 457 630T439 622Q438 621 368 343T298 60Q298 48 386 46Q418 46 427 45T436 36Q436 31 433 22Q429 4 424 1L422 0Q419 0 415 0Q410 0 363 1T228 2Q99 2 64 0H49Q43 6 43 9T45 27Q49 40 55 46H83H94Q174 46 189 55Q190 56 191 56Q196 59 201 76T241 233Q258 301 269 344Q339 619 339 625Q339 630 310 630H279Q212 630 191 624Q146 614 121 583T67 467Q60 445 57 441T43 437H40Z"></path><path stroke-width="1" id="E10-MJMAIN-30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path><path stroke-width="1" id="E10-MJMATHI-4E" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path><path stroke-width="1" id="E10-MJMAIN-33" d="M127 463Q100 463 85 480T69 524Q69 579 117 622T233 665Q268 665 277 664Q351 652 390 611T430 522Q430 470 396 421T302 350L299 348Q299 347 308 345T337 336T375 315Q457 262 457 175Q457 96 395 37T238 -22Q158 -22 100 21T42 130Q42 158 60 175T105 193Q133 193 151 175T169 130Q169 119 166 110T159 94T148 82T136 74T126 70T118 67L114 66Q165 21 238 21Q293 21 321 74Q338 107 338 175V195Q338 290 274 322Q259 328 213 329L171 330L168 332Q166 335 166 348Q166 366 174 366Q202 366 232 371Q266 376 294 413T322 525V533Q322 590 287 612Q265 626 240 626Q208 626 181 615T143 592T132 580H135Q138 579 143 578T153 573T165 566T175 555T183 540T186 520Q186 498 172 481T127 463Z"></path><path stroke-width="1" id="E10-MJMATHI-58" d="M42 0H40Q26 0 26 11Q26 15 29 27Q33 41 36 43T55 46Q141 49 190 98Q200 108 306 224T411 342Q302 620 297 625Q288 636 234 637H206Q200 643 200 645T202 664Q206 677 212 683H226Q260 681 347 681Q380 681 408 681T453 682T473 682Q490 682 490 671Q490 670 488 658Q484 643 481 640T465 637Q434 634 411 620L488 426L541 485Q646 598 646 610Q646 628 622 635Q617 635 609 637Q594 637 594 648Q594 650 596 664Q600 677 606 683H618Q619 683 643 683T697 681T738 680Q828 680 837 683H845Q852 676 852 672Q850 647 840 637H824Q790 636 763 628T722 611T698 593L687 584Q687 585 592 480L505 384Q505 383 536 304T601 142T638 56Q648 47 699 46Q734 46 734 37Q734 35 732 23Q728 7 725 4T711 1Q708 1 678 1T589 2Q528 2 496 2T461 1Q444 1 444 10Q444 11 446 25Q448 35 450 39T455 44T464 46T480 47T506 54Q523 62 523 64Q522 64 476 181L429 299Q241 95 236 84Q232 76 232 72Q232 53 261 47Q262 47 267 47T273 46Q276 46 277 46T280 45T283 42T284 35Q284 26 282 19Q279 6 276 4T261 1Q258 1 243 1T201 2T142 2Q64 2 42 0Z"></path><path stroke-width="1" id="E10-MJMATHI-41" d="M208 74Q208 50 254 46Q272 46 272 35Q272 34 270 22Q267 8 264 4T251 0Q249 0 239 0T205 1T141 2Q70 2 50 0H42Q35 7 35 11Q37 38 48 46H62Q132 49 164 96Q170 102 345 401T523 704Q530 716 547 716H555H572Q578 707 578 706L606 383Q634 60 636 57Q641 46 701 46Q726 46 726 36Q726 34 723 22Q720 7 718 4T704 0Q701 0 690 0T651 1T578 2Q484 2 455 0H443Q437 6 437 9T439 27Q443 40 445 43L449 46H469Q523 49 533 63L521 213H283L249 155Q208 86 208 74ZM516 260Q516 271 504 416T490 562L463 519Q447 492 400 412L310 260L413 259Q516 259 516 260Z"></path><path stroke-width="1" id="E10-MJMAIN-5B" d="M118 -250V750H255V710H158V-210H255V-250H118Z"></path><path stroke-width="1" id="E10-MJMATHI-69" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path><path stroke-width="1" id="E10-MJMAIN-5D" d="M22 710V750H159V-250H22V-210H119V710H22Z"></path></defs><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="matrix(1 0 0 -1 0 0)"><use xlink:href="#E10-MJMAIN-31" x="0" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="778" y="0"></use><use xlink:href="#E10-MJMATHI-54" x="1834" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="2816" y="0"></use><g transform="translate(3873,0)"><use xlink:href="#E10-MJMAIN-31"></use><use xlink:href="#E10-MJMAIN-30" x="500" y="0"></use></g><g transform="translate(0,-1542)"><use xlink:href="#E10-MJMAIN-31" x="0" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="778" y="0"></use><use xlink:href="#E10-MJMATHI-4E" x="1834" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="3000" y="0"></use><g transform="translate(4057,0)"><use xlink:href="#E10-MJMAIN-31"></use><use xlink:href="#E10-MJMAIN-30" x="500" y="0"></use><use transform="scale(0.914)" xlink:href="#E10-MJMAIN-33" x="1094" y="396"></use></g></g><g transform="translate(0,-3083)"><use xlink:href="#E10-MJMAIN-31" x="0" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="778" y="0"></use><use xlink:href="#E10-MJMATHI-58" x="1834" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="2964" y="0"></use><g transform="translate(4021,0)"><use xlink:href="#E10-MJMAIN-31"></use><use xlink:href="#E10-MJMAIN-30" x="500" y="0"></use><use transform="scale(0.914)" xlink:href="#E10-MJMAIN-33" x="1094" y="396"></use></g></g><g transform="translate(0,-4625)"><use xlink:href="#E10-MJMAIN-30" x="0" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="778" y="0"></use><use xlink:href="#E10-MJMATHI-41" x="1834" y="0"></use><use xlink:href="#E10-MJMAIN-5B" x="2585" y="0"></use><use xlink:href="#E10-MJMATHI-69" x="2863" y="0"></use><use xlink:href="#E10-MJMAIN-5D" x="3209" y="0"></use><use xlink:href="#E10-MJMAIN-2264" x="3765" y="0"></use><g transform="translate(4821,0)"><use xlink:href="#E10-MJMAIN-31"></use><use xlink:href="#E10-MJMAIN-30" x="500" y="0"></use><use transform="scale(0.914)" xlink:href="#E10-MJMAIN-33" x="1094" y="396"></use></g></g></g></svg><span class="MJX_Assistive_MathML" role="presentation"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mo>≤</mo><mi>T</mi><mo>≤</mo><mn>10</mn><mspace linebreak="newline"></mspace><mn>1</mn><mo>≤</mo><mi>N</mi><mo>≤</mo><msup><mn>10</mn><mn>3</mn></msup><mspace linebreak="newline"></mspace><mn>1</mn><mo>≤</mo><mi>X</mi><mo>≤</mo><msup><mn>10</mn><mn>3</mn></msup><mspace linebreak="newline"></mspace><mn>0</mn><mo>≤</mo><mi>A</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>≤</mo><msup><mn>10</mn><mn>3</mn></msup></math></span></span><script type="math/tex" id="MathJax-Element-10">1 \le T \le 10 \\ 1 \le N \le 10^3 \\ 1 \le X \le 10^3 \\ 0 \le A[i] \le 10^3</script></span>
Code snippets (also called starter code/boilerplate code)
This question has code snippets for C, CPP, Java, and Python. <div class="clear"> <div class="clear"> <div id="input-output-box-eb2fc1a964ef44e9900806e2918ba5a8" class="margin-top-12"><div id="sample-test-case-1630753637532" class="sample-test-case"><div class="view-sample-test-case d-flex margin-bottom-12"><div class="padding-right-36 w-50"><div class="d-flex title-container"><div class="sample-title">Sample input 1 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 80px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">1
</pre><pre style="position: absolute; left: 0px; top: 20px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">3
</pre><pre style="position: absolute; left: 0px; top: 40px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">1
</pre><pre style="position: absolute; left: 0px; top: 60px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">5 7 1</pre> <div class="w-50"><div class="d-flex title-container"><div class="sample-title">Sample output 1 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 20px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">4</pre> <div class="margin-top-24"><div class="sample-title">Explanation <div class="explanation"> The first line contains the number of test cases, T = 1.
The first test case
Given
N = 3
X = 1
A[] = [5, 7, 1]
Approach
Following subsequences satisfy the given conditions:
[5, 7]
[5, 1]
[7, 1]
Empty subsequence
Thus, the required answer is 4. <textarea class="text-area-to-copy"></textarea> <div class="n-inline-message margin-top-24 sample-test-case-notification n-info-message"><span class="width-border"></span><div class="inline-message-content"><div class="inline-message-header"><div class="info-icon"><div class="vertical-align-middle inline-block type-icon"><i class="icon ui-exclamation-o" style="font-size: 12px;"></i> <div class="inline-message-header-content"><div class="inline-message-content">
The following test cases are the actual test cases of this question that may be used to evaluate your submission. <i class="empty-icon"></i> <div class="margin-top-24"><div id="sample-test-case-20819062" class="sample-test-case margin-top-24"><div class="view-sample-test-case d-flex margin-bottom-12"><div class="padding-right-36 w-50"><div class="d-flex title-container"><div class="sample-title">Sample input 2 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 80px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">1</pre><pre style="position: absolute; left: 0px; top: 20px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">9</pre><pre style="position: absolute; left: 0px; top: 40px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">88</pre><pre style="position: absolute; left: 0px; top: 60px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">8 25 4 30 2 8 32 32 28</pre> <div class="w-50"><div class="d-flex title-container"><div class="sample-title">Sample output 2 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 40px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">128</pre><pre style="position: absolute; left: 0px; top: 20px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;"></pre> <textarea class="text-area-to-copy"></textarea> <div id="sample-test-case-20819063" class="sample-test-case margin-top-24 highlight"><div class="view-sample-test-case d-flex margin-bottom-12"><div class="padding-right-36 w-50"><div class="d-flex title-container"><div class="sample-title">Sample input 3 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 80px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">1</pre><pre style="position: absolute; left: 0px; top: 20px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">10</pre><pre style="position: absolute; left: 0px; top: 40px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">34</pre><pre style="position: absolute; left: 0px; top: 60px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">20 2 29 9 5 9 16 15 12 40</pre> <div class="w-50"><div class="d-flex title-container"><div class="sample-title">Sample output 3 <span class="copy-text" role="presentation">Copy</span> <div class="margin-top-12"><div class="sample-data"><div style="position: relative; height: 220px; width: 100%; overflow: auto; will-change: transform; direction: ltr;"><div style="height: 40px; width: 100%;"><pre style="position: absolute; left: 0px; top: 0px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;">256</pre><pre style="position: absolute; left: 0px; top: 20px; height: 20px; width: 100%; padding-left: 16px; margin: 0px; white-space: pre; font-size: 12px;"></pre> <textarea class="text-area-to-copy"></textarea> <div class="small margin-bottom-4 margin-top-12"><span class="bold">Note: </span><span>Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.</span> <div class="margin-top-10 light small problem-solution-limits"><div class="margin-top-4">Time Limit: 1.0 sec(s) for each input file <div class="margin-top-4">Memory Limit: 256 MB <div class="margin-top-4">Source Limit: 1024 KB <div class="margin-top-4">Marking Scheme: Score is assigned if any testcase passes <div class="margin-top-4">Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic
*************************************/
#include<bits/stdc++.h>
using namespace std;
// vector<vector<int>> bit;
// void pre(vector<int> A, int n){
// for(int i = 0; i < 32; i++){
// bit[i][0]=0;
// for(int j = 0; j < n; j++){
// if(j>0){
// bit[i][j] = bit[i][j-1];
// }
// if(A[j] & (1<<i)) bit[i][j]++;
// }
// }
// }
// int mor(int l,int r){
// int ans = 0;
// int no;
// for(int i =0 ; i < 32; i++){
// no = bit[i][r] - l>0 ? bit[i][l-1] : 0;
// if((no & 1)) ans += (1<<i);
// }
// return ans;
// }
// void bin(unsigned n)
// {
// if (n > 1)
// bin(n >> 1);
// cout << (n & 1);
// }
long long c = 0;
void all(vector<int> A, int n, int i,int x,int X){
if(i == n){
return ;
}
else{
all(A,n,i+1,x,X);
// cout << x << " "; cout << A[i]<<" "; cout <<(x^A[i])<< " \n";
if(!(X&(x^A[i]))) c++;
// cout << "\n";
all(A,n,i+1,x^A[i],X);
}
}
long long solve (int N, int X, vector<int> A) {
// bit.resize(32,vector<int>(N));
// pre(A,N);
// long long ans=0;
// for(int i = 0; i < N; i++){
// for(int j = i; j<N;j++){
// if(!(X&mor(i,j))) ans++;
// }
// }
// return ans;
all(A,N,0,0,X);
return c + 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for(int t_i = 0; t_i < T; t_i++)
{
int N;
cin >> N;
int X;
cin >> X;
vector<int> A(N);
for(int i_A = 0; i_A < N; i_A++)
{
cin >> A[i_A];
}
long long out_;
out_ = solve(N, X, A);
cout << out_;
cout << "\n";
}
}