codeforces-scrape

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

1392.md (36818B)


      1 Source: https://codeforces.com/blog/entry/81565
      2 
      3 We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)
      4 
      5 We have to apologize to [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") a bit here -- the rejection count mentioned in the [editorial](https://codeforces.com/blog/entry/79974) for [Codeforces Round 655 (Div. 2)](/contest/1372 "Codeforces Round 655 (Div. 2)") actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:
      6 
      7 **Rejection Counts**
      8 
      9 * A: 12
     10 * B: 16
     11 * C: **6**
     12 * D: 19
     13 * E: 18
     14 * F: 2
     15 
     16 Total: **73**
     17 
     18 Without further ado, here are the tutorials for each of the problems:
     19 
     20 Tutorial is loading...
     21 
     22 **Solution (Kotlin) by golions**
     23 
     24 ```
     25 import java.io.*
     26 import java.util.*
     27 import kotlin.math.*
     28 
     29 fun main(){
     30 	val f = BufferedReader(InputStreamReader(System.`in`))
     31 
     32 	for(q in 1..f.readLine().toInt()){
     33 		val n = f.readLine().toInt()
     34 		val array = f.readLine().split(" ").map{it.toInt()}.toHashSet()
     35 
     36 		if(array.size == 1){
     37 			println(n)
     38 		} else {
     39 			println(1)
     40 		}
     41 	}
     42 }
     43 ```
     44 
     45 **Solution (Java) by MagentaCobra**
     46 
     47 ```
     48 /*
     49 Omkar orz
     50 */
     51 import java.util.*;
     52 import java.io.*;
     53 import java.math.*;
     54 
     55    public class ModelPasswordA
     56    {
     57       public static void main(String omkar[]) throws Exception
     58       {
     59          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
     60          StringTokenizer st = new StringTokenizer(infile.readLine());
     61          int T = Integer.parseInt(st.nextToken());
     62          StringBuilder sb = new StringBuilder();
     63          while(T-->0)
     64          {
     65             int N = Integer.parseInt(infile.readLine());
     66             int[] arr = new int[N];
     67             st = new StringTokenizer(infile.readLine());
     68             for(int i=0; i < N; i++)
     69                arr[i] = Integer.parseInt(st.nextToken());
     70             int res = N;
     71             for(int i=1; i < N; i++)
     72                if(arr[i] != arr[i-1])
     73                   res = 1;
     74             sb.append(res+"\n");
     75          }
     76          System.out.print(sb);
     77       }
     78    }
     79 ```
     80 
     81 **Solution (C++) by hugopm**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85 #define len(v) ((int)((v).size()))
     86 #define all(v) (v).begin(), (v).end()
     87 #define rall(v) (v).rbegin(), (v).rend()
     88 #define chmax(x, v) x = max((x), (v))
     89 #define chmin(x, v) x = min((x), (v))
     90 using namespace std;
     91 using ll = long long;
     92 
     93 void solve() {
     94 	int n; cin >> n;
     95 	vector<int> vec(n);
     96 	for (int i = 0; i < n; ++i) {
     97 		cin >> vec[i];
     98 	}
     99 	sort(all(vec));
    100 	if (vec.front() == vec.back()) cout << n << "\n";
    101 	else cout << "1\n";
    102 }
    103 
    104 int main() {
    105 	ios::sync_with_stdio(false);
    106 	cin.tie(0);
    107 
    108 	int nbTests;
    109 	cin >> nbTests;
    110 	for (int iTest = 0; iTest < nbTests; ++iTest) {
    111 		solve();
    112 	}
    113 }
    114 ```
    115 
    116 Idea: [gotexans](/profile/gotexans "Master gotexans") and [qlf9](/profile/qlf9 "Expert qlf9")
    117 
    118 Preparation: [gotexans](/profile/gotexans "Master gotexans")
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (Kotlin) by Tlatoani**
    123 
    124 ```
    125 import java.io.BufferedReader
    126 import java.io.InputStreamReader
    127 
    128 fun main() {
    129     val jin = BufferedReader(InputStreamReader(System.`in`))
    130     val out = StringBuilder()
    131     for (c in 1..jin.readLine().toInt()) {
    132         val line = jin.readLine().split(" ")
    133         val n = line[0].toInt()
    134         val k = line[1].last().toString().toInt() % 2
    135         val array = jin.readLine().split(" ").map { it.toLong() }.toLongArray()
    136         var m = array.max()!!
    137         for (j in 0 until n) {
    138             array[j] = m - array[j]
    139         }
    140         if (k == 0) {
    141             m = array.max()!!
    142             for (j in 0 until n) {
    143                 array[j] = m - array[j]
    144             }
    145         }
    146         out.appendln(array.joinToString(" "))
    147     }
    148     print(out)
    149 }
    150 ```
    151 
    152 **Solution (Java) by MagentaCobra**
    153 
    154 ```
    155 //Omkar, Holy Light
    156 import java.util.*;
    157 import java.io.*;
    158 import java.math.*;
    159 
    160    public class ModelB
    161    {
    162       public static void main(String omkar[]) throws Exception
    163       {
    164          //query based
    165          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
    166          StringTokenizer st = new StringTokenizer(infile.readLine());
    167          int T = Integer.parseInt(st.nextToken());
    168          StringBuilder sb = new StringBuilder();
    169          while(T-->0)
    170          {
    171             st = new StringTokenizer(infile.readLine());
    172             int N = Integer.parseInt(st.nextToken());
    173             long K = Long.parseLong(st.nextToken())%2;
    174             if(K == 0)  K = 2;
    175             int[] arr = new int[N];
    176             st = new StringTokenizer(infile.readLine());
    177             for(int i=0; i < N; i++)
    178                arr[i] = Integer.parseInt(st.nextToken());
    179             for(int turns=0; turns < K; turns++)
    180             {
    181                int max = arr[0];
    182                for(int x: arr)
    183                   max = Math.max(max, x);
    184                for(int i=0; i < N; i++)
    185                   arr[i] = max-arr[i];
    186             }
    187             for(int i=0; i < N; i++)
    188             {
    189                sb.append(arr[i]);
    190                if(i+1 < N)
    191                   sb.append(" ");
    192             }
    193             sb.append("\n");
    194          }
    195          System.out.print(sb);
    196       }
    197    }
    198 ```
    199 
    200 **Solution (C++) by tfg**
    201 
    202 ```
    203 #include <iostream>
    204 #include <vector>
    205 #include <chrono>
    206 #include <random>
    207 #include <cassert>
    208 
    209 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
    210 
    211 int main() {
    212 	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    213 	int t;
    214 	std::cin >> t;
    215 	while(t--) {
    216 		int n;
    217 		long long k;
    218 		std::cin >> n >> k;
    219 		std::vector<int> a(n);
    220 		for(int i = 0; i < n; i++) {
    221 			std::cin >> a[i];
    222 		}
    223 		if(k > 1) {
    224 			k = 2 + k % 2;
    225 		}
    226 		while(k--) {
    227 			int mx = -1000000000;
    228 			for(int i = 0; i < n; i++) {
    229 				mx = std::max(mx, a[i]);
    230 			}
    231 			for(int i = 0; i < n; i++) {
    232 				a[i] = mx - a[i];
    233 			}
    234 		}
    235 		for(int i = 0; i < n; i++) {
    236 			std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    237 		}
    238 	}
    239 }
    240 ```
    241 
    242 Idea: [gotexans](/profile/gotexans "Master gotexans")
    243 
    244 Preparation: [gotexans](/profile/gotexans "Master gotexans")
    245 
    246 Tutorial is loading...
    247 
    248 **Solution (Kotlin) by Tlatoani**
    249 
    250 ```
    251 import kotlin.math.max
    252 
    253 fun main() {
    254     for (c in 1..readLine()!!.toInt()) {
    255         val n = readLine()!!.toInt()
    256         val hs = readLine()!!.split(" ").map { it.toLong() }
    257         var answer = 0L
    258         for (j in 1 until n) {
    259             answer += max(0L, hs[j - 1] - hs[j])
    260         }
    261         println(answer)
    262     }
    263 }
    264 ```
    265 
    266 **Solution (Java) by qlf9**
    267 
    268 ```
    269 import java.util.*;
    270 import java.io.*;
    271 
    272 public class OmkarAndWaterslide {
    273     public static void main(String[] args) throws IOException{
    274         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
    275         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    276         int t = Integer.parseInt(f.readLine());
    277         while(t-->0){
    278             int n = Integer.parseInt(f.readLine());
    279             long[] arr = new long[n];
    280             StringTokenizer st = new StringTokenizer(f.readLine());
    281             for(int i = 0; i < n; i++){
    282                 arr[i] = Integer.parseInt(st.nextToken());
    283             }
    284             long ans = 0;
    285             for(int i = 0; i < n-1; i++){
    286                 ans+=Math.max(0, arr[i]-arr[i+1]);
    287             }
    288             out.println(ans);
    289         }
    290         out.close();
    291     }
    292 }
    293 ```
    294 
    295 **Solution (C++) by tfg**
    296 
    297 ```
    298 #include <iostream>
    299 #include <vector>
    300 #include <chrono>
    301 #include <random>
    302 #include <cassert>
    303 
    304 std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
    305 
    306 int main() {
    307 	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    308 	int t;
    309 	std::cin >> t;
    310 	while(t--) {
    311 		int n;
    312 		std::cin >> n;
    313 		long long last = 0;
    314 		long long ans = 0;
    315 		while(n--) {
    316 			long long x;
    317 			std::cin >> x;
    318 			x += ans;
    319 			if(x >= last) {
    320 				last = x;
    321 			} else {
    322 				ans += last &mdash; x;
    323 			}
    324 		}
    325 		std::cout << ans << '\n';
    326 	}
    327 }
    328 ```
    329 
    330 Idea: [qlf9](/profile/qlf9 "Expert qlf9")
    331 
    332 Preparation: [qlf9](/profile/qlf9 "Expert qlf9")
    333 
    334 Tutorial is loading...
    335 
    336 **Solution (Kotlin) by Tlatoani**
    337 
    338 ```
    339 import java.io.BufferedReader
    340 import java.io.InputStreamReader
    341 
    342 fun main() {
    343     val jin = BufferedReader(InputStreamReader(System.`in`))
    344     val out = StringBuilder()
    345     for (c in 1..jin.readLine().toInt()) {
    346         val n = jin.readLine().toInt()
    347         val s = jin.readLine()
    348         if (s.all { it == s[0] }) {
    349             out.appendln((n + 2) / 3)
    350         } else {
    351             var k = 0
    352             while (s[k] == s[0]) {
    353                 k++
    354             }
    355             var answer = 0
    356             var curr = 0
    357             var chara = s[k]
    358             for (j in k until k + n) {
    359                 if (s[j % n] == chara) {
    360                     curr++
    361                 } else {
    362                     answer += curr / 3
    363                     curr = 1
    364                     chara = s[j % n]
    365                 }
    366             }
    367             answer += curr / 3
    368             out.appendln(answer)
    369         }
    370     }
    371     print(out)
    372 }
    373 ```
    374 
    375 **Solution (Java) by qlf9**
    376 
    377 ```
    378 import java.util.*;
    379 import java.io.*;
    380 
    381 public class OmkarAndBedWars {
    382     public static void main(String[] args) throws IOException{
    383         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
    384         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    385         int t = Integer.parseInt(f.readLine());
    386         while(t-->0){
    387             int n = Integer.parseInt(f.readLine());
    388             String str = f.readLine();
    389             boolean same = true;
    390             for(int i = 1; i < n; i++){
    391                 if(str.charAt(i) != str.charAt(0)){
    392                     same = false;
    393                     break;
    394                 }
    395             }
    396             if(same){
    397                 out.println((n+2)/3);
    398                 continue;
    399             }
    400             ArrayList<Integer> count = new ArrayList<Integer>();
    401             int last = 0;
    402             int cnt = 1;
    403             for(int i = 1; i < n; i++){
    404                 if(str.charAt(i) == str.charAt(last)){
    405                     cnt++;
    406                 }else{
    407                     count.add(cnt);
    408                     last = i;
    409                     cnt = 1;
    410                 }
    411             }
    412             if(str.charAt(n-1) == str.charAt(0)){
    413                 count.set(0, count.get(0)+cnt);
    414             }else{
    415                 count.add(cnt);
    416             }
    417             int sum = 0;
    418             for(int i: count) sum+=(i/3);
    419             out.println(sum);
    420 
    421         }
    422         out.close();
    423     }
    424 
    425 }
    426 ```
    427 
    428 **Solution (C++) by Ari**
    429 
    430 ```
    431 #include <bits/stdc++.h>
    432 using namespace std;
    433 
    434 void solve() {
    435     int n, ans = 0;
    436     cin >> n;
    437     string s;
    438     cin >> s;
    439     int cnt = 0;
    440     while(s.size() && s[0] == s.back()) {
    441         cnt++;
    442         s.pop_back();
    443     }
    444     if(s.empty()) {
    445         if(cnt <= 2) {
    446             cout << "0\n";
    447             return;
    448         }
    449         if(cnt == 3) {
    450             cout << "1\n";
    451             return;
    452         }
    453         cout << (cnt + 2) / 3 << '\n';
    454         return;
    455     }
    456     s.push_back('$');
    457     for(int i = 0; i + 1 < s.size(); i++) {
    458         cnt++;
    459         if(s[i] != s[i + 1]) {
    460             ans += cnt / 3;
    461             cnt = 0;
    462         }
    463     }
    464     cout << ans << '\n';
    465 }
    466 
    467 int main() {
    468     ios_base::sync_with_stdio(false);
    469     cin.tie(0);
    470 
    471     int t;
    472     cin >> t;
    473     while(t--)
    474         solve();
    475 }
    476 ```
    477 
    478 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    479 
    480 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    481 
    482 Tutorial is loading...
    483 
    484 **Solution (Kotlin) by Tlatoani**
    485 
    486 ```
    487 fun main() {
    488     val n = readLine()!!.toInt()
    489     for (x in 1..n) {
    490         for (y in 1..n) {
    491             if (x % 2 == 0) {
    492                 print(1L shl (x + y))
    493             } else {
    494                 print(0)
    495             }
    496             print(" ")
    497         }
    498         println()
    499     }
    500     val q = readLine()!!.toInt()
    501     for (j in 1..q) {
    502         val k = readLine()!!.toLong()
    503         var x = 1
    504         var y = 1
    505         print("1 1 ")
    506         for (e in 3..2 * n) {
    507             if ((x % 2 == 0) == (((k shr e) % 2L) == 1L)) {
    508                 y++
    509             } else {
    510                 x++
    511             }
    512             print("$x $y ")
    513         }
    514         println()
    515     }
    516 }
    517 ```
    518 
    519 **Solution (Java) by golions**
    520 
    521 ```
    522 //make sure to make new file!
    523 import java.io.*;
    524 import java.util.*;
    525 
    526 public class DuckSolution{
    527    
    528    public static void main(String[] args)throws IOException{
    529       BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
    530       PrintWriter out = new PrintWriter(System.out);
    531       
    532       int n = Integer.parseInt(f.readLine());
    533       
    534       long[][] board = new long[n][n];
    535       board[0][0] = 0L;
    536       board[n-1][n-1] = 0L;
    537       
    538       for(int k = 0; k < n; k++){
    539          for(int j = 0; j < n; j++){
    540             if(k == 0 && j == 0) continue;
    541             if(k == n-1 && j == n-1) continue;
    542             
    543             if(k%2 == 0){
    544                board[k][j] = 1L << k+j;
    545             }
    546          }
    547       }
    548       
    549       for(int k = 0; k < n; k++){
    550          StringJoiner sj = new StringJoiner(" ");
    551          for(int j = 0; j < n; j++){
    552             sj.add("" + board[k][j]);
    553          }
    554          out.println(sj.toString());
    555       }
    556       
    557       out.flush();
    558       
    559       int q = Integer.parseInt(f.readLine());
    560       for(int t = 0; t < q; t++){
    561          long i = Long.parseLong(f.readLine());
    562          
    563          ArrayList<Integer> x = new ArrayList<Integer>();
    564          ArrayList<Integer> y = new ArrayList<Integer>();
    565          
    566          int curx = 0;
    567          int cury = 0;
    568          
    569          x.add(1);
    570          y.add(1);
    571          
    572          while(curx < n-1 || cury < n-1){
    573             if(curx == n-1){
    574                cury++;
    575             } else if(cury == n-1){
    576                curx++;
    577             } else {
    578                long and = Math.max(board[curx+1][cury],board[curx][cury+1]);
    579                if(((i & and) > 0) ^ (board[curx+1][cury] > 0)){
    580                   cury++;
    581                } else {
    582                   curx++;
    583                }
    584             
    585             
    586             }
    587             
    588             x.add(curx+1);
    589             y.add(cury+1);
    590          }
    591          
    592          StringJoiner sj = new StringJoiner(" ");
    593          for(int k = 0; k < x.size(); k++){
    594             sj.add("" + x.get(k) + " " + y.get(k));
    595          }
    596          out.println(sj.toString());
    597          out.flush();
    598       }
    599       
    600       
    601       
    602       
    603       
    604       
    605       
    606       
    607       out.close();
    608    }
    609    
    610       
    611 }
    612 ```
    613 
    614 **Solution (C++) by hugopm**
    615 
    616 ```
    617 #include <bits/stdc++.h>
    618 #define len(v) ((int)((v).size()))
    619 #define all(v) (v).begin(), (v).end()
    620 #define rall(v) (v).rbegin(), (v).rend()
    621 #define chmax(x, v) x = max((x), (v))
    622 #define chmin(x, v) x = min((x), (v))
    623 using namespace std;
    624 using ll = long long;
    625 
    626 int main() {
    627 	ios::sync_with_stdio(false);
    628 	cin.tie(0);
    629 	int side; cin >> side;
    630 	vector<vector<ll>> grid(side, vector<ll>(side, 0));
    631 	for (int i = 0; i < side; ++i) {
    632 		for (int j = 0; j < side; ++j) {
    633 			if ((i-j+side)&2LL) grid[i][j] = (1LL << (i+j));
    634 			cout << grid[i][j] << " \n"[j==side-1];
    635 		}
    636 	}
    637 	cout << flush;
    638 	int nbQuery; cin >> nbQuery;
    639 	for (int iQuery = 0; iQuery < nbQuery; ++iQuery) {
    640 		ll sum; cin >> sum;
    641 		cout << "1 1";
    642 		int row = 0, col = 0;
    643 		for (int diag = 0; diag < 2*side-2; ++diag) {
    644 			ll should = sum&(1LL<<(diag+1));
    645 			if (row+1<side && grid[row+1][col] == should) ++row;
    646 			else ++col;
    647 			cout << " " << row+1 << " " << col+1;
    648 		}
    649 		cout << endl << flush;
    650 	}
    651 }
    652 ```
    653 
    654 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    655 
    656 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") and [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat")
    657 
    658 Tutorial is loading...
    659 
    660 **EDIT:** The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:
    661 
    662 If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.
    663 
    664 If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $\alpha$ that can be immediately applied on the vector.
    665 
    666 Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).
    667 
    668 Therefore, applying other (different) operations cannot prevent operation $\alpha$ from being able to be applied, so operation $\alpha$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $\alpha$ does not occur initially, then operation $\alpha$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.
    669 
    670 Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).
    671 
    672 **Solution (Kotlin) by Tlatoani**
    673 
    674 ```
    675 import java.io.BufferedReader
    676 import java.io.InputStreamReader
    677 import java.util.*
    678 
    679 fun main() {
    680     val jin = BufferedReader(InputStreamReader(System.`in`))
    681     val n = jin.readLine().toLong()
    682     val tokenizer = StringTokenizer(jin.readLine())
    683     var sum = 0L
    684     for (j in 0L until n) {
    685         sum += tokenizer.nextToken().toLong() - j
    686     }
    687     val joiner = StringJoiner(" ")
    688     for (j in 0L until n) {
    689         joiner.add(((sum / n) + (if (j < sum % n) 1L else 0L) + j).toString())
    690     }
    691     println(joiner)
    692 }
    693 ```
    694 
    695 **Solution (Java) by qlf9**
    696 
    697 ```
    698 import java.util.*;
    699 import java.io.*;
    700 
    701 public class OmkarAndLandslideNumber2 {
    702     public static void main(String[] args) throws IOException{
    703         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
    704         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    705         long n = Long.parseLong(f.readLine());
    706         long sum = 0;
    707         StringTokenizer st = new StringTokenizer(f.readLine());
    708         for(int i = 0; i < n; i++){
    709             sum+=Long.parseLong(st.nextToken());
    710         }
    711         long k = ((sum - n*(n - 1)/2) / n);
    712         long diff = sum - (n*k + n*(n - 1)/2);
    713         StringBuilder ans = new StringBuilder();
    714         for(long i = 0; i < n; i++){
    715             if(i < diff){
    716                 ans.append(k+i+1L);
    717                 ans.append(" ");
    718             }else{
    719                 ans.append(k+i);
    720                 ans.append(" ");
    721             }
    722         }
    723         out.println(ans.toString().trim());
    724         out.close();
    725     }
    726 }
    727 ```
    728 
    729 **Solution (C++) by Devil**
    730 
    731 ```
    732 #include <bits/stdc++.h>
    733 
    734 using namespace std;
    735 
    736 typedef long long ll;
    737 
    738 int main()
    739 {
    740 	ios_base::sync_with_stdio(0), cin.tie(0);
    741 	ll n;
    742 	cin >> n;
    743 	ll s = 0;
    744 	for (ll x, i = 0; i < n; ++i)
    745 		cin >> x, s += x;
    746 
    747 	ll l = (s - n * (n-1) / 2) / n + 1;
    748 	s = l * n + n * (n-1) / 2 - s;
    749 	for (int i = 0; i < n; ++i)
    750 		cout << l + i - (n-i <= s) << " \n"[i+1==n];
    751 
    752 	return 0;
    753 }
    754 ```
    755 
    756 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    757 
    758 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") and [qlf9](/profile/qlf9 "Expert qlf9")
    759 
    760 Tutorial is loading...
    761 
    762 **Solution (Kotlin) by Tlatoani**
    763 
    764 ```
    765 import java.io.BufferedReader
    766 import java.io.InputStreamReader
    767 import kotlin.math.max
    768 import kotlin.math.min
    769 
    770 fun main() {
    771     val jin = BufferedReader(InputStreamReader(System.`in`))
    772     var line = jin.readLine().split(" ")
    773     val n = line[0].toInt()
    774     val m = line[1].toInt()
    775     val k = line[2].toInt()
    776     val dpLeft = IntArray(1 shl k) { n + 1 }
    777     val dpRight = IntArray(1 shl k) { -1 }
    778     var original = jin.readLine().reversed().toInt(2)
    779     var goal = jin.readLine().reversed().toInt(2)
    780     val permutation = IntArray(k) { it }
    781     dpLeft[original] = 0
    782     dpRight[goal] = 0
    783     for (j in 1..n) {
    784         line = jin.readLine().split(" ")
    785         val a = line[0].toInt() - 1
    786         val b = line[1].toInt() - 1
    787         var c = (original shr permutation[a]) and 1
    788         var d = (original shr permutation[b]) and 1
    789         original -= c shl permutation[a]
    790         original -= d shl permutation[b]
    791         original += d shl permutation[a]
    792         original += c shl permutation[b]
    793         c = (goal shr permutation[a]) and 1
    794         d = (goal shr permutation[b]) and 1
    795         goal -= c shl permutation[a]
    796         goal -= d shl permutation[b]
    797         goal += d shl permutation[a]
    798         goal += c shl permutation[b]
    799         dpLeft[original] = min(dpLeft[original], j)
    800         dpRight[goal] = j
    801         c = permutation[a]
    802         d = permutation[b]
    803         permutation[a] = d
    804         permutation[b] = c
    805     }
    806     var best = -1
    807     var l = -1
    808     var r = -1
    809     for (mask in (1 shl k) - 1 downTo 0) {
    810         for (e in 0 until k) {
    811             if ((mask shr e) and 1 != 0) {
    812                 dpLeft[mask - (1 shl e)] = min(dpLeft[mask - (1 shl e)], dpLeft[mask])
    813                 dpRight[mask - (1 shl e)] = max(dpRight[mask - (1 shl e)], dpRight[mask])
    814             }
    815         }
    816         if (dpLeft[mask] + m <= dpRight[mask] && Integer.bitCount(mask) > best) {
    817             best = Integer.bitCount(mask)
    818             l = dpLeft[mask] + 1
    819             r = dpRight[mask]
    820         }
    821     }
    822     println(k - Integer.bitCount(original) - Integer.bitCount(goal) + (2 * best))
    823     println("$l $r")
    824 }
    825 ```
    826 
    827 **Solution (Java) by qlf9**
    828 
    829 ```
    830 import java.io.*;
    831 import java.util.*;
    832 
    833 public class OmkarAndPies {
    834     public static int INF = Integer.MAX_VALUE/2;
    835     public static void main(String[] args) throws IOException{
    836         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
    837         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    838         StringTokenizer st = new StringTokenizer(f.readLine());
    839         int n = Integer.parseInt(st.nextToken());
    840         int m = Integer.parseInt(st.nextToken());
    841         int k = Integer.parseInt(st.nextToken());
    842         int bitstr = Integer.parseInt(f.readLine(), 2);
    843         int goal = Integer.parseInt(f.readLine(), 2);
    844         int[] arr1 = new int[n];
    845         int[] arr2 = new int[n];
    846         for(int i = 0; i < n; i++){
    847             st = new StringTokenizer(f.readLine());
    848             arr1[i] = Integer.parseInt(st.nextToken());
    849             arr2[i] = Integer.parseInt(st.nextToken());
    850         }
    851         int[] lefts = new int[n+1];
    852         int[] rights = new int[n+1];
    853         rights[0] = goal;
    854         lefts[0] = bitstr;
    855         int[] permutation = new int[k];
    856         int[] indices = new int[k];
    857         for(int i = 0; i < k; i++){
    858             permutation[i] = i;
    859             indices[i] = i;
    860         }
    861         for(int i = 0; i < n; i++){
    862             int temp = indices[arr1[i]-1];
    863             indices[arr1[i]-1] = indices[arr2[i]-1];
    864             indices[arr2[i]-1] = temp;
    865             permutation[indices[arr1[i]-1]] = arr1[i]-1;
    866             permutation[indices[arr2[i]-1]] = arr2[i]-1;
    867             lefts[i+1] = applyPermutation(indices, bitstr, k);
    868             rights[i+1] = applyPermutation(indices, goal, k);
    869         }
    870         int[] dpLeft = new int[(1 << k)];
    871         int[] dpRight = new int[(1 << k)];
    872         Arrays.fill(dpLeft, INF);
    873         Arrays.fill(dpRight, -INF);
    874         for(int i = 0; i <= n; i++){
    875             dpLeft[lefts[i]] = Math.min(dpLeft[lefts[i]], i);
    876             dpRight[rights[i]] = Math.max(dpRight[rights[i]], i);
    877         }
    878         for(int i = (1 << k)-1; i > 1; i--){
    879             int temp = i;
    880             int count = 0;
    881             while(temp != 0){
    882                 if(temp % 2 == 1){
    883                     dpLeft[i-(1 << count)] = Math.min(dpLeft[i-(1 << count)], dpLeft[i]);
    884                     dpRight[i-(1 << count)] = Math.max(dpRight[i-(1 << count)], dpRight[i]);
    885                 }
    886                 temp/=2;
    887                 count++;
    888             }
    889         }
    890         for(int i = 0; i < (1 << k); i++){
    891             if(dpLeft[i] == 2 && dpRight[i] == 8){
    892                 System.out.println(i);
    893             }
    894         }
    895         int maxVal = -INF;
    896         int intLeft = -1;
    897         int intRight = -1;
    898         for(int i = 0; i < (1 << k); i++){
    899             if(dpRight[i]-dpLeft[i] < m) continue;
    900             int a1 = lefts[dpLeft[i]];
    901             int a2 = rights[dpRight[i]];
    902             int count = 0;
    903             for(int j = 0; j < k; j++){
    904                 if(a1 % 2 == a2 % 2) count++;
    905                 a1/=2;
    906                 a2/=2;
    907             }
    908             if(count > maxVal){
    909                 maxVal = count;
    910                 intLeft = dpLeft[i]+1;
    911                 intRight = dpRight[i];
    912             }
    913         }
    914         out.println(maxVal);
    915         out.println(intLeft + " " + intRight);
    916         out.close();
    917 
    918     }
    919     public static int applyPermutation(int[] permutation, int bitstr, int k){
    920         int ans = 0;
    921         for(int i = k-1; i >= 0; i--){
    922            if(bitstr % 2 == 1){
    923                ans += (1 << (k-permutation[i]-1));
    924            }
    925            bitstr/=2;
    926         }
    927         return ans;
    928     }
    929 }
    930 ```
    931 
    932 **Solution (C++) by mohammedehab2002**
    933 
    934 ```
    935 #include <bits/stdc++.h>
    936 using namespace std;
    937 int p[20],dp[2][(1<<20)];
    938 int getmask(string s)
    939 {
    940 	int ans=0;
    941 	for (int i=0;i<s.size();i++)
    942 	ans|=((s[i]-'0')<<i);
    943 	return ans;
    944 }
    945 int main()
    946 {
    947 	int n,m,k;
    948 	scanf("%d%d%d",&n,&m,&k);
    949 	string a,b;
    950 	cin >> a >> b;
    951 	for (int i=0;i<k;i++)
    952 	p[i]=i;
    953 	for (int i=0;i<(1<<k);i++)
    954 	{
    955 		dp[0][i]=1e9;
    956 		dp[1][i]=-1e9;
    957 	}
    958 	dp[0][getmask(a)]=0;
    959 	dp[1][getmask(b)]=0;
    960 	for (int i=1;i<=n;i++)
    961 	{
    962 		int x,y;
    963 		scanf("%d%d",&x,&y);
    964 		x--;
    965 		y--;
    966 		swap(p[x],p[y]);
    967 		string aa(k,'0'),bb(k,'0');
    968 		for (int j=0;j<k;j++)
    969 		{
    970 			aa[p[j]]=a[j];
    971 			bb[p[j]]=b[j];
    972 		}
    973 		dp[0][getmask(aa)]=min(dp[0][getmask(aa)],i);
    974 		dp[1][getmask(bb)]=i;
    975 	}
    976 	int o1=count(a.begin(),a.end(),'1'),o2=count(b.begin(),b.end(),'1');
    977 	pair<int,pair<int,int> > ans(0,{0,0});
    978 	for (int i=(1<<k)-1;i>=0;i--)
    979 	{
    980 		if (dp[1][i]-dp[0][i]>=m)
    981 		ans=max(ans,make_pair(k-(o1+o2-2*__builtin_popcount(i)),make_pair(dp[0][i]+1,dp[1][i])));
    982 		for (int j=0;j<k;j++)
    983 		{
    984 			if (i&(1<<j))
    985 			{
    986 				dp[0][i^(1<<j)]=min(dp[0][i^(1<<j)],dp[0][i]);
    987 				dp[1][i^(1<<j)]=max(dp[1][i^(1<<j)],dp[1][i]);
    988 			}
    989 		}
    990 	}
    991 	printf("%d\n%d %d",ans.first,ans.second.first,ans.second.second);
    992 }
    993 ```
    994 
    995 Idea: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    996 
    997 Preparation: [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani")
    998 
    999 Tutorial is loading...
   1000 
   1001 **Solution (C++) by zscoder**
   1002 
   1003 ```
   1004 #include <bits/stdc++.h>
   1005 #include <ext/pb_ds/assoc_container.hpp>
   1006 #include <ext/pb_ds/tree_policy.hpp>
   1007 
   1008 using namespace std;
   1009 using namespace __gnu_pbds;
   1010  
   1011 #define fi first
   1012 #define se second
   1013 #define mp make_pair
   1014 #define pb push_back
   1015 #define fbo find_by_order
   1016 #define ook order_of_key
   1017  
   1018 typedef long long ll;
   1019 typedef pair<ll,ll> ii;
   1020 typedef vector<int> vi;
   1021 typedef long double ld; 
   1022 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
   1023 
   1024 const int MOD = 998244353;
   1025 
   1026 vector<int> fact;
   1027 vector<int> ifact;
   1028 vector<int> pow2;
   1029 int add(int a, int b)
   1030 {
   1031 	a+=b;
   1032 	while(a>=MOD) a-=MOD;
   1033 	return a;
   1034 }
   1035 void radd(int &a, int b)
   1036 {
   1037 	a=add(a,b); 
   1038 }
   1039 int mult(int a, int b)
   1040 {
   1041 	return (a*1LL*b)%MOD;
   1042 }
   1043 void rmult(int &a, int b)
   1044 {
   1045 	a=mult(a,b);
   1046 }
   1047 int modpow(int a, int b)
   1048 {
   1049 	int r=1;
   1050 	while(b)
   1051 	{
   1052 		if(b&1) r=mult(r,a);
   1053 		a=mult(a,a);
   1054 		b>>=1;
   1055 	}
   1056 	return r;
   1057 }
   1058 int choose(int a, int b)
   1059 {
   1060 	if(a<0) return 0;
   1061 	if(b<0) return 0;
   1062 	if(a<b) return 0;
   1063 	if(b==0) return 1;
   1064 	if(a==b) return 1;
   1065 	return mult(fact[a],mult(ifact[b],ifact[a-b]));
   1066 }
   1067 int inverse(int a)
   1068 {
   1069 	return modpow(a,MOD-2);
   1070 }
   1071 void init(int _n)
   1072 {
   1073 	fact.clear(); ifact.clear(); pow2.clear();
   1074 	fact.resize(_n+1);
   1075 	ifact.resize(_n+1);
   1076 	pow2.resize(_n+1);
   1077 	pow2[0]=1;
   1078 	ifact[0]=1;
   1079 	fact[0]=1;
   1080 	for(int i=1;i<=_n;i++)
   1081 	{
   1082 		pow2[i]=add(pow2[i-1],pow2[i-1]);
   1083 		fact[i]=mult(fact[i-1],i);
   1084 		//ifact[i]=mult(ifact[i-1],inv[i]);
   1085 	}
   1086 	ifact[_n] = inverse(fact[_n]);
   1087 	for(int i=_n-1;i>=1;i--)
   1088 	{
   1089 		ifact[i] = mult(ifact[i + 1], i + 1);
   1090 	}
   1091 }
   1092 	
   1093 int solve_slow(int n, int m)
   1094 {
   1095 	vi f(n+1,0);
   1096 	for(int k=1;k<=n;k++)
   1097 	{
   1098 		int sum=0;
   1099 		for(int l=1;l<=k;l++)
   1100 		{
   1101 			for(int i=0;i<=n;i++)
   1102 			{
   1103 				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
   1104 				radd(sum, mult(coeff, add(f[k-l],i+1)));
   1105 			}
   1106 		}
   1107 		{
   1108 			int l=0;
   1109 			int sumcoeff=0;
   1110 			for(int i=0;i<=n;i++)
   1111 			{
   1112 				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
   1113 				radd(sum, mult(coeff, i+1));
   1114 				radd(sumcoeff,coeff);
   1115 			}
   1116 			int actualcoeff = add(1,MOD-sumcoeff);
   1117 			assert(actualcoeff!=0);
   1118 			f[k]=mult(inverse(actualcoeff),sum);
   1119 		}
   1120 	}
   1121 	return f[n];
   1122 }
   1123 
   1124 int solve_fast(int n, int m)
   1125 {
   1126 	vi f(n+1,0);
   1127 	int presum=0;
   1128 	for(int k=1;k<=n;k++)
   1129 	{
   1130 		int sum=mult(presum,choose(n+m,m+k));
   1131 		radd(sum,mult(fact[m-1],mult(choose(m+k+1,m+1),choose(n+m+1,m+k+1))));
   1132 		int outsidecoeff = mult(fact[k],mult(fact[n-k],mult(ifact[n+m],m)));
   1133 		sum = mult(sum, outsidecoeff);
   1134 		f[k]=mult(mult(m+k,mult(ifact[k],fact[k-1])),sum);
   1135 		//f[k]=mult(mult(k,mult(fact[m+k-1],ifact[m+k])),sum);
   1136 		radd(presum,mult(fact[m+k-1],mult(ifact[k],f[k])));
   1137 	}
   1138 	return f[n];
   1139 }
   1140 
   1141 int main()
   1142 {
   1143 	ios_base::sync_with_stdio(0); cin.tie(0);
   1144 	init(int(1e7)+100);
   1145 	int n,m; cin>>n>>m;
   1146 	//cout<<solve_slow(n,m)<<'\n';
   1147 	cout<<solve_fast(n,m)<<'\n';
   1148 }
   1149 ```
   1150 
   1151 **Solution (Java) by qlf9**
   1152 
   1153 ```
   1154 import java.util.*;
   1155 import java.io.*;
   1156 
   1157 public class ZSShufflesCards {
   1158     public static long MOD = 998244353;
   1159     public static long[] fact;
   1160     public static long[] invfact;
   1161     public static long[] pow2;
   1162     public static int MAX = 4000005;
   1163     public static void main(String[] args) throws IOException{
   1164         BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
   1165         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
   1166         StringTokenizer st = new StringTokenizer(f.readLine());
   1167         int n = Integer.parseInt(st.nextToken());
   1168         int m = Integer.parseInt(st.nextToken());
   1169         fact = new long[MAX];
   1170         invfact = new long[MAX];
   1171         pow2 = new long[MAX];
   1172         fact[0] = 1;
   1173         invfact[0] = 1;
   1174         pow2[0] = 1;
   1175         for(int i = 1; i < MAX; i++){
   1176             pow2[i] = add(pow2[i-1], pow2[i-1]);
   1177             fact[i] = mult(fact[i-1], i);
   1178         }
   1179         invfact[MAX-1] = inverse(fact[MAX-1]);
   1180         for(int i = MAX-2; i >= 1; i--){
   1181             invfact[i] = mult(invfact[i+1], i+1);
   1182         }
   1183         long[] ans = new long[n+1];
   1184         long currsum = 0;
   1185         for(int k = 1; k <= n; k++){
   1186             long sum = mult(currsum, ncr(n+m, m+k));
   1187             sum = add(sum,mult(fact[m-1],mult(ncr(m+k+1,m+1),ncr(n+m+1,m+k+1))));
   1188             long outsidecoeff = mult(fact[k],mult(fact[n-k],mult(invfact[n+m],m)));
   1189             sum = mult(sum, outsidecoeff);
   1190             ans[k]=mult(mult(m+k,mult(invfact[k],fact[k-1])),sum);
   1191             currsum = add(currsum,mult(fact[m+k-1],mult(invfact[k],ans[k])));
   1192         }
   1193         out.println(ans[n]);
   1194         out.close();
   1195 
   1196     }
   1197     public static long add(long a, long b){
   1198         return((a+b)%MOD+MOD)%MOD;
   1199     }
   1200     public static long mult(long a, long b){
   1201         return((a*b)%MOD+MOD)%MOD;
   1202     }
   1203     public static long pow(long a, long b){
   1204         long ans = 1;
   1205         while(b > 0){
   1206             if((b&1) == 1) ans = mult(ans, a);
   1207             a = mult(a, a);
   1208             b>>=1;
   1209         }
   1210         return ans;
   1211     }
   1212     public static long ncr(long a, long b){
   1213         if(a<0) return 0;
   1214         if(b<0) return 0;
   1215         if(a<b) return 0;
   1216         if(b==0) return 1;
   1217         if(a==b) return 1;
   1218         return mult(fact[(int)a],mult(invfact[(int)b],invfact[(int)(a-b)]));
   1219     }
   1220     public static long inverse(long a){
   1221         return pow(a, MOD-2);
   1222     }
   1223 }
   1224 ```
   1225 
   1226 **Solution (Kotlin) by Tlatoani**
   1227 
   1228 ```
   1229 const val MOD = 998244353L
   1230 
   1231 fun main() {
   1232     val (n, m) = readLine()!!.split(" ").map { it.toInt() }
   1233     val factorial = LongArray(4000002)
   1234     factorial[0] = 1L
   1235     for (j in 1..4000001) {
   1236         factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
   1237     }
   1238     val factInv = LongArray(4000002)
   1239     factInv[4000001] = factorial[4000001] pow -1
   1240     for (j in 4000000 downTo 0) {
   1241         factInv[j] = ((j + 1).toLong() * factInv[j + 1]) % MOD
   1242     }
   1243     fun choose(a: Int, b: Int) = if (a < 0 || b < 0 || b > a) 0L else (factorial[a] * ((factInv[b] * factInv[a - b]) % MOD)) % MOD
   1244     val answer = LongArray(n + 1)
   1245     var currSum = 0L
   1246     for (k in 1..n) {
   1247         var sum = currSum * choose(n + m, m + k)
   1248         sum %= MOD
   1249         sum += factorial[m - 1] * ((choose(m + k + 1, m + 1) * choose(n + m + 1, m + k + 1)) % MOD)
   1250         sum %= MOD
   1251         sum *= (factorial[k] * ((factorial[n - k] * ((factInv[n + m] * m.toLong()) % MOD)) % MOD)) % MOD
   1252         sum %= MOD
   1253         answer[k] = sum * (((m + k).toLong() * ((factInv[k] * factorial[k - 1]) % MOD)) % MOD)
   1254         answer[k] %= MOD
   1255         currSum += factorial[m + k - 1] * ((factInv[k] * answer[k]) % MOD)
   1256         currSum %= MOD
   1257     }
   1258     println(answer[n])
   1259 }
   1260 
   1261 const val MOD_TOTIENT = MOD.toInt() - 1
   1262 
   1263 infix fun Long.pow(power: Int): Long {
   1264     var e = power
   1265     e %= MOD_TOTIENT
   1266     if (e < 0) {
   1267         e += MOD_TOTIENT
   1268     }
   1269     if (e == 0 && this == 0L) {
   1270         return this
   1271     }
   1272     var b = this % MOD
   1273     var res = 1L
   1274     while (e > 0) {
   1275         if (e and 1 != 0) {
   1276             res *= b
   1277             res %= MOD
   1278         }
   1279         b *= b
   1280         b %= MOD
   1281         e = e shr 1
   1282     }
   1283     return res
   1284 }
   1285 ```
   1286 
   1287 Idea: [zscoder](/profile/zscoder "International Grandmaster zscoder")
   1288 
   1289 Preparation: [zscoder](/profile/zscoder "International Grandmaster zscoder")
   1290 
   1291 Tutorial is loading...
   1292 
   1293 **Solution (C++) by KLPP**
   1294 
   1295 ```
   1296 #include<bits/stdc++.h>
   1297 
   1298 using namespace std;
   1299 #define MAX 262144
   1300 #define MAXN 1000000
   1301 long long int a[MAXN],b[MAXN];
   1302 
   1303 using cd = complex<double>;
   1304 const double PI = acos(-1);
   1305 vector<cd> A(MAX),B(MAX);
   1306 vector<cd> Amx(MAX),Bmx(MAX);
   1307 vector<cd> Amn(MAX),Bmn(MAX);
   1308 vector<cd> E11(MAX),E12(MAX),E21(MAX),E22(MAX);
   1309 vector<cd> SQ1(MAX),SQ2(MAX);
   1310 vector<cd> V(MAX);
   1311 vector<long long int> A1(MAX),A2(MAX);
   1312 
   1313 void fft(vector<cd> & a, bool invert) {
   1314     int n = a.size();
   1315 
   1316     for (int i = 1, j = 0; i < n; i++) {
   1317         int bit = n >> 1;
   1318         for (; j & bit; bit >>= 1)
   1319             j ^= bit;
   1320         j ^= bit;
   1321 
   1322         if (i < j)
   1323             swap(a[i], a[j]);
   1324     }
   1325 
   1326     for (int len = 2; len <= n; len <<= 1) {
   1327         double ang = 2 * PI / len * (invert ? -1 : 1);
   1328         cd wlen(cos(ang), sin(ang));
   1329         for (int i = 0; i < n; i += len) {
   1330             cd w(1);
   1331             for (int j = 0; j < len / 2; j++) {
   1332                 cd u = a[i+j], v = a[i+j+len/2] * w;
   1333                 a[i+j] = u + v;
   1334                 a[i+j+len/2] = u - v;
   1335                 w *= wlen;
   1336             }
   1337         }
   1338     }
   1339 
   1340     if (invert) {
   1341         for (cd & x : a)
   1342             x /= n;
   1343     }
   1344 }
   1345 void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){
   1346   for(int i=0;i<a.size();i++){
   1347     c[i]=a[i]*b[i];
   1348   }
   1349 }
   1350 
   1351 int main(){
   1352   long long int n,m,q;
   1353   scanf("%lld %lld %lld",&n,&m,&q);
   1354   
   1355   for(int i=0;i<n;i++){
   1356     scanf("%lld",&a[i]);
   1357   }
   1358   for(int i=0;i<m;i++){
   1359     scanf("%lld",&b[i]);
   1360   }
   1361   for(int i=0;i<MAX;i++){
   1362     A[i]=cd(0,0);
   1363     Amn[i]=cd(0,0);
   1364     Amx[i]=cd(0,0);
   1365     B[i]=cd(0,0);
   1366     Bmn[i]=cd(0,0);
   1367     Bmx[i]=cd(0,0);
   1368   }
   1369   for(int i=0;i<n;i++){
   1370     A[a[i]]+=cd(1,0);
   1371   }
   1372   for(int i=0;i<n-1;i++){
   1373     Amn[min(a[i],a[i+1])]+=cd(1,0);
   1374   }
   1375   for(int i=0;i<n-1;i++){
   1376     Amx[max(a[i],a[i+1])]+=cd(1,0);
   1377   }
   1378   for(int i=0;i<m;i++){
   1379     B[b[i]]+=cd(1,0);
   1380   }
   1381   for(int i=0;i<m-1;i++){
   1382     Bmn[min(b[i],b[i+1])]+=cd(1,0);
   1383   }
   1384   for(int i=0;i<m-1;i++){
   1385     Bmx[max(b[i],b[i+1])]+=cd(1,0);
   1386   }
   1387   
   1388   fft(A,0);
   1389   fft(Amn,0);
   1390   fft(Amx,0);
   1391   fft(B,0);
   1392   fft(Bmn,0);
   1393   fft(Bmx,0);
   1394   prod(A,Bmn,E11);
   1395   prod(Amn,B,E12);
   1396   prod(Amx,B,E21);
   1397   prod(A,Bmx,E22);
   1398   prod(Amn,Bmn,SQ1);
   1399   prod(Amx,Bmx,SQ2);
   1400   prod(A,B,V);
   1401   fft(E11,1);
   1402   fft(E12,1);
   1403   fft(E21,1);
   1404   fft(E22,1);
   1405   fft(SQ1,1);
   1406   fft(SQ2,1);
   1407   fft(V,1);
   1408   for(int i=0;i<MAX;i++){
   1409     A1[i]=round(SQ1[i].real())-round(E11[i].real())-round(E12[i].real())+round(V[i].real());
   1410     A2[i]=round(SQ2[i].real())-round(E21[i].real())-round(E22[i].real())+round(V[i].real());
   1411   }
   1412   for(int i=1;i<MAX;i++){
   1413     A2[i]+=A2[i-1];
   1414   }
   1415   for(int i=MAX-2;i>-1;i--){
   1416     A1[i]+=A1[i+1];
   1417   }
   1418   for(int i=0;i<q;i++){
   1419     int query;
   1420     scanf("%d",&query);
   1421     //cout<<A1[query]<<" "<<A2[query-1]<<endl;
   1422     printf("%lld\n",A1[query]-A2[query-1]);
   1423   }
   1424   return 0;
   1425 }
   1426 ```
   1427 
   1428 Idea: [KLPP](/profile/KLPP "Master KLPP")
   1429 
   1430 Preparation: [KLPP](/profile/KLPP "Master KLPP")