codeforces-scrape

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

1605.md (27579B)


      1 Source: https://codeforces.com/blog/entry/96866
      2 
      3 Thank you for participating! We hope you enjoyed the contest.
      4 
      5 [1605A - A.M. Deviation](/contest/1605/problem/A "Codeforces Round 754 (Div. 2)")
      6 
      7 Authored and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot")
      8 
      9 **Hint 1**
     10 
     11 What happens to the value of $d(a_1, a_2, a_3)$ if you perform an operation on $a_1$ and $a_3$?
     12 
     13 **Hint 2**
     14 
     15 What happens if you perform an operation on $a_1$ and $a_2$?
     16 
     17 **Hint 3**
     18 
     19 Can we use negative values to improve the worst answer?
     20 
     21 **Solution**
     22 
     23 Tutorial is loading...
     24 
     25 **Solution [c++] (JeevanJyot)**
     26 
     27 ```
     28 #include <bits/stdc++.h>
     29 using namespace std;
     30  
     31 int32_t main()
     32 {
     33     ios_base::sync_with_stdio(0); 
     34     cin.tie(0); cout.tie(0);
     35     int T; cin >> T;
     36     while(T--)
     37     {
     38         int a, b, c; cin >> a >> b >> c;
     39         cout << ((a + c - 2 * b) % 3 == 0 ? 0 : 1) << "\n"; 
     40     }        
     41     return 0;
     42 }
     43 ```
     44 
     45 **Solution [Kotlin] (ExplodingFreeze)**
     46 
     47 ```
     48 fun main(args: Array<String>) {
     49     repeat(readLine()!!.toInt()) {
     50         println(Math.min(readLine()!!.split(" ").map { it.toInt() }.sum() % 3, 1))
     51     }
     52 }
     53 ```
     54 
     55 **Solution [Python] (AshishGup)**
     56 
     57 ```
     58 t=int(input())
     59 for i in range(t):
     60     a,b,c=[int(x) for x in input().split()]
     61     print(0 if ((a+b+c)%3 == 0) else 1)
     62 ```
     63 
     64 [1605B - Reverse Sort](/contest/1605/problem/B "Codeforces Round 754 (Div. 2)")
     65 
     66 Authored by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot").
     67 
     68 **Hint 1**
     69 
     70 What can you say about the number of $0$s and $1$s that are in positions where they should not be in the final string?
     71 
     72 **Hint 2**
     73 
     74 What is the minimum number of operations required to sort the string given this relationship between the number of such $0$s and $1$s?
     75 
     76 **Solution**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution [c++] (JeevanJyot)**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84 using namespace std;
     85  
     86 int32_t main()
     87 {
     88     ios_base::sync_with_stdio(0); 
     89     cin.tie(0); cout.tie(0);
     90     int T; cin >> T;
     91     while(T--)
     92     {
     93         int n; cin >> n;
     94         string s; cin >> s;
     95         if(is_sorted(s.begin(), s.end()))
     96         {
     97             cout << 0 << "\n";
     98             continue;
     99         }
    100         
    101         string t = s;
    102         sort(t.begin(), t.end());
    103         cout << 1 << "\n";
    104         vector<int> ans;
    105         for(int i = 0; i < n; i++)
    106         {
    107             if(s[i] != t[i])
    108                 ans.push_back(i+1);
    109         }
    110         cout << ans.size() << " ";
    111         for(int i = 0; i < ans.size(); i++)
    112             cout << ans[i] << " \n"[i+1 == ans.size()];
    113     }        
    114     return 0;
    115 }
    116 ```
    117 
    118 **Solution [Kotlin] (ExplodingFreeze)**
    119 
    120 ```
    121 fun main(args: Array<String>) {
    122     repeat(readLine()!!.toInt()) {
    123         val n = readLine()!!.toInt()
    124         val s = readLine()!!
    125         if("10" in s) {
    126             println(1);
    127             val res = s.toCharArray().sorted().withIndex().filter { it.value != s[it.index] }.map { it.index + 1 }
    128             println("${res.size} ${res.joinToString(" ")}");
    129         } else {
    130             println(0);
    131         }
    132         
    133     }
    134 }
    135 ```
    136 
    137 **Solution [Python] (AshishGup)**
    138 
    139 ```
    140 q = int(input())
    141 for tc in range(q):
    142     n = int(input())
    143     s = input()
    144     t = ''.join(sorted(s))
    145     ans = []
    146     for i in range(len(s)):
    147         if s[i] != t[i]: 
    148             ans.append(i)
    149     val = 1 if len(ans) > 0 else 0
    150     print(val)
    151     if val > 0:
    152         print(len(ans), end = " ")
    153     for elem in range(len(ans)):
    154         print(ans[elem] + 1, end = " ")
    155     print()
    156 ```
    157 
    158 [1605C - Dominant Character](/contest/1605/problem/C "Codeforces Round 754 (Div. 2)")
    159 
    160 Authored by [Ashishgup](/profile/Ashishgup "Grandmaster Ashishgup") and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot").
    161 
    162 **Hint 1**
    163 
    164 Think about small substrings.
    165 
    166 **Hint 2**
    167 
    168 What are the strings that satisfy the given conditions?
    169 
    170 **Hint 3**
    171 
    172 If you got WA on pretest $2$, then you're probably not checking $7$ length strings.
    173 
    174 **Solution**
    175 
    176 Tutorial is loading...
    177 
    178 **Solution [c++] (AshishGup)**
    179 
    180 ```
    181 #include <bits/stdc++.h>
    182 using namespace std;
    183  
    184 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    185 #define endl "\n"
    186 #define int long long
    187  
    188 const int N = 1e6 + 5;
    189  
    190 int n;
    191 string s;
    192  
    193 int32_t main()
    194 {
    195 	IOS;
    196 	int t;
    197 	cin >> t;
    198 	while(t--)
    199 	{
    200 		cin >> n >> s;
    201 		int ans = 1e9;
    202 		for(int i = 0; i < n; i++)
    203 		{
    204 			vector<int> f(3, 0);
    205 			f[s[i] - 'a']++;
    206 			for(int j = i + 1; j < min(n, i + 7); j++)
    207 			{
    208 				f[s[j] - 'a']++;
    209 				if(f[0] > f[1] && f[0] > f[2])
    210 					ans = min(ans, j - i + 1);
    211 			}
    212 		}
    213 		if(ans == 1e9)
    214 			ans = -1;
    215 		cout << ans << endl;
    216 	}
    217 	return 0;
    218 }
    219 ```
    220 
    221 **Solution [Kotlin] (ExplodingFreeze)**
    222 
    223 ```
    224 fun main(args: Array<String>) {
    225     repeat(readLine()!!.toInt()) {
    226         val n = readLine()!!.toInt()
    227         val s = readLine()!!
    228         var ans = 8;
    229         for(i in 0..n-1) {
    230             val cnt = IntArray(3) {0}
    231             for(j in i..Math.min(i + 6, n - 1)) {
    232                 cnt[s[j] - 'a']++;
    233                 if(j > i && cnt[0] > Math.max(cnt[1], cnt[2]))
    234                     ans = Math.min(ans, j - i + 1);
    235             }
    236         }
    237         if(ans > 7)
    238             ans = -1;
    239         println(ans)
    240     }
    241 }
    242 ```
    243 
    244 [1605D - Treelabeling](/contest/1605/problem/D "Codeforces Round 754 (Div. 2)")
    245 
    246 Authored and prepared by [the_hyp0cr1t3](/profile/the_hyp0cr1t3 "Master the_hyp0cr1t3").
    247 
    248 **Hint 1**
    249 
    250 When is $u \oplus v \nleq min(u, v)$?
    251 
    252 **Hint 2**
    253 
    254 If $u \oplus v \nleq min(u, v)$ for any $u$ that is adjacent to $v$, the player cannot make move and will lose.
    255 
    256 **Hint 3**
    257 
    258 Can you relabel the nodes in such a way that $u \oplus v \nleq min(u, v)$ for any $u$ and $v$ which share an edge? Think bipartite.
    259 
    260 **Hint 4**
    261 
    262 The number of occurrences of (almost) every 'class' of nodes of the same kind is a unique power of $2$.
    263 
    264 **Hint 5**
    265 
    266 Thinking about the binary representation of a number is often useful in competitive programming.
    267 
    268 **Solution**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution [c++] (the_hyp0cr1t3)**
    273 
    274 ```
    275 /**
    276  * the_hyp0cr1t3
    277  * 24.09.2021 01:19:28
    278 **/
    279 #ifdef W
    280     #include <k_II.h>
    281 #else
    282     #include <bits/stdc++.h>
    283     using namespace std;
    284 #endif
    285  
    286 template<class T> class Y {
    287     T f;
    288 public:
    289     template<class U> explicit Y(U&& f): f(forward<U>(f)) {}
    290     template<class... Args> decltype(auto) operator()(Args&&... args) {
    291         return f(ref(*this), forward<Args>(args)...);
    292     }
    293 }; template<class T> Y(T) -> Y<T>;
    294  
    295 int main() {
    296     ios_base::sync_with_stdio(false), cin.tie(nullptr);
    297     int Q; cin >> Q;
    298  
    299     while(Q--) []() {
    300         int i, j, k, n;
    301         cin >> n;
    302         vector<vector<int>> g(n);
    303         for(i = 0; i < n - 1; i++) {
    304             int u, v; cin >> u >> v;
    305             g[--u].push_back(--v); g[v].push_back(u);
    306         }
    307  
    308         int lg = 32 - __builtin_clz(n);
    309         vector<vector<int>> vals(lg);
    310         for(i = 1; i <= n; i++)
    311             vals[31 - __builtin_clz(i)].push_back(i);
    312  
    313         vector<int> col(n);
    314         Y([&](auto dfs, int v, int p) -> void {
    315             for(auto& x: g[v]) if(x ^ p) {
    316                 col[x] = col[v] ^ 1;
    317                 dfs(x, v);
    318             }
    319         })(0, -1);
    320  
    321         int w = accumulate(col.begin(), col.end(), 0);
    322         if(w > n - w) {
    323             w = n - w;
    324             for(auto& x: col) x ^= 1;
    325         }
    326  
    327         vector<int> ans(n);
    328         for(i = j = k = 0; k < lg; k++) {
    329             for(auto x: vals[k]) {
    330                 if(w >> k & 1) {
    331                     while(!col[i]) i++;
    332                     ans[i++] = x;
    333                 } else {
    334                     while(col[j]) j++;
    335                     ans[j++] = x;
    336                 }
    337             }
    338         }
    339  
    340         for(i = 0; i < n; i++)
    341             cout << ans[i] << " \n"[i + 1 == n];
    342     }();
    343  
    344 } // ~W
    345 ```
    346 
    347 **Solution [c++] (AshishGup)**
    348 
    349 ```
    350 #include <bits/stdc++.h>
    351 using namespace std;
    352  
    353 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    354 #define endl "\n"
    355  
    356 const int N = 2e5 + 5;
    357  
    358 int n;
    359 int msb[N], ans[N];
    360 vector<int> nodes[2];
    361 vector<int> g[N];
    362  
    363 void precompute()
    364 {
    365 	int bit = 1, cnt = 1, nxt = 2;
    366 	for(int i = 1; i < N; i++)
    367 	{
    368 		msb[i] = bit;
    369 		cnt--;
    370 		if(cnt == 0)
    371 			cnt = nxt, bit++, nxt *= 2;
    372 	}
    373 }
    374  
    375 void dfs(int u, int par, int col)
    376 {
    377 	nodes[col].push_back(u);
    378 	for(auto &v: g[u])
    379 	{
    380 		if(v == par)
    381 			continue;
    382 		dfs(v, u, col ^ 1);
    383 	}
    384 }
    385  
    386  
    387 int32_t main()
    388 {
    389 	IOS;
    390 	precompute();
    391 	int t;
    392 	cin >> t;
    393 	while(t--)
    394 	{
    395 		cin >> n;
    396 		for(int i = 1; i <= n; i++)
    397 			g[i].clear();
    398 		for(int i = 1; i <= n - 1; i++)
    399 		{
    400 			int u, v;
    401 			cin >> u >> v;
    402 			g[u].push_back(v);
    403 			g[v].push_back(u);
    404 		}
    405 		dfs(1, 0, 0);
    406 		vector<vector<int> > v(20);
    407 		for(int i = 1; i <= n; i++)
    408 			v[msb[i]].push_back(i);
    409 		for(int i = 19; i >= 0; i--)
    410 		{
    411 			int cur = 0;
    412 			if(nodes[cur ^ 1].size() > nodes[cur].size())
    413 				cur ^= 1;
    414 			for(auto &it:v[i])
    415 			{
    416 				int node = nodes[cur].back();
    417 				nodes[cur].pop_back();
    418 				ans[node] = it;
    419 			}
    420 		}
    421 		for(int i = 1; i <= n; i++)
    422 			cout << ans[i] << " ";
    423 		cout << endl;
    424 	}
    425 	return 0;
    426 }
    427 ```
    428 
    429 **Solution [Kotlin] (ExplodingFreeze)**
    430 
    431 ```
    432 fun dfs(x: Int, p: Int, curcol: Int, adj: Array<MutableList<Int>>, col: Array<Int>) {
    433     col[x] = curcol
    434     adj[x]
    435         .filter { it != p }
    436         .forEach { dfs(it, x, curcol xor 1, adj, col) }
    437 }
    438  
    439 fun main(args: Array<String>) {
    440     val t = readLine()!!.toInt()
    441     repeat(t) {
    442         val n = readLine()!!.toInt()
    443         val adj = Array(n) { mutableListOf<Int>() }
    444         repeat(n - 1) {
    445             val (u, v) = readLine()!!.split(" ").map { it.toInt() }
    446             adj[u - 1].add(v - 1);
    447             adj[v - 1].add(u - 1);
    448         }
    449         val col = Array<Int>(n) {0}
    450         dfs(0, -1, 0, adj, col)
    451         var s = Array(2) { mutableListOf<Int>() }
    452         (0..n-1).forEach { s[col[it]].add(it) }
    453         if(s[0].size < s[1].size)
    454             s[0] = s[1].also { s[1] = s[0] }
    455         val highestBit = Array(20) { mutableListOf<Int>() }
    456         (1..n).forEach { highestBit[it.takeHighestOneBit().countTrailingZeroBits()].add(it - 1) }
    457         val ans = Array<Int>(n) {-1}
    458         (19 downTo 0).forEach { currentBit ->
    459             val largerSet = if(s[0].size >= s[1].size) 0 else 1
    460             highestBit[currentBit].forEach { it ->
    461                 ans[it] = s[largerSet].last()
    462                 s[largerSet].removeLast()
    463             }
    464         }
    465         val pos = Array<Int>(n) {-1}
    466         (0..n-1).forEach { pos[ans[it]] = it };
    467         (0..n-1).forEach { print ("${pos[it] + 1} ") }
    468         println()
    469     }
    470 }
    471 ```
    472 
    473 [1605E - Array Equalizer](/contest/1605/problem/E "Codeforces Round 754 (Div. 2)")
    474 
    475 Authored and prepared by [JeevanJyot](/profile/JeevanJyot "Master JeevanJyot").
    476 
    477 **Hint 1**
    478 
    479 How would you solve the problem for one query?
    480 
    481 **Hint 2**
    482 
    483 Assume the value of $b_1$ to be some variable, say $x$.
    484 
    485 **Hint 3**
    486 
    487 Try finding the number of operations applied at each index in terms of $x$.
    488 
    489 **Solution**
    490 
    491 Tutorial is loading...
    492 
    493 **Solution [c++] (JeevanJyot)**
    494 
    495 ```
    496 #include <bits/stdc++.h>
    497 using namespace std;
    498  
    499 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    500 #define int long long
    501 #define endl "\n"
    502 #define sz(w) (int)(w.size())
    503 using pii = pair<int, int>;
    504  
    505 const double EPS = 1e-9;
    506 const long long INF = 1e18;
    507  
    508 const int N = 2e5+5; 
    509  
    510 int n, m, a[N], b[N], c[N], add[N], mob[N];
    511  
    512 void mobius() 
    513 {
    514     mob[1] = 1;
    515     for(int i = 2; i < N; i++)
    516     {
    517         mob[i]--;
    518         for(int j = i + i; j < N; j += i) 
    519         {
    520           mob[j] -= mob[i];
    521         }
    522     }
    523 }
    524  
    525 int32_t main()
    526 {
    527     IOS;
    528     mobius();
    529     cin >> n;
    530     for(int i = 1; i <= n; i++)
    531         cin >> a[i];
    532     for(int i = 1; i <= n; i++)
    533         cin >> b[i];
    534     for(int i = 1; i <= n; i++)
    535         c[i] = b[i] - a[i];
    536     c[1] = 0;
    537     vector<int> z;
    538     for(int i = 1; i <= n; i++)
    539     {
    540         int d = c[i];
    541         for(int j = i; j <= n; j += i)
    542         {
    543             c[j] -= d;
    544         }
    545         add[i] = d;
    546     }
    547     int ans = 0;
    548     for(int i = 1; i <= n; i++)
    549     {
    550         if(mob[i] == 0)
    551             ans += abs(add[i]);
    552         else if(mob[i] == -1)
    553             z.push_back(-add[i]);
    554         else 
    555             z.push_back(add[i]);
    556     }
    557     sort(z.begin(), z.end());
    558     vector<int> pref = z;
    559     for(int i = 1; i < sz(z); i++)
    560         pref[i] = pref[i-1] + z[i];
    561     auto sum = [&pref](int l, int r)
    562     {
    563         if(r < 0) return 0LL;
    564         int res = pref[r];
    565         if(l-1 >= 0)
    566             res -= pref[l-1];
    567         return res;
    568     };
    569     int q; cin >> q;
    570     while(q--)
    571     {
    572         int x; cin >> x;
    573         x -= a[1];
    574         int lo = 0, hi = sz(z)-1;
    575         while(lo <= hi)
    576         {
    577             int mid = (lo+hi)/2;
    578             if(z[mid] <= -x)
    579                 lo = mid+1;
    580             else
    581                 hi = mid-1;
    582         }
    583         swap(lo, hi);
    584         int res = sum(hi, sz(z)-1) + (sz(z)-hi) * x;
    585         res -= (sum(0, lo) + (lo+1)*x);
    586         cout << ans+res << endl;
    587     }
    588     return 0;
    589 }
    590 ```
    591 
    592 [1605F - PalindORme](/contest/1605/problem/F "Codeforces Round 754 (Div. 2)")
    593 
    594 Authored by [ExplodingFreeze](/profile/ExplodingFreeze "Master ExplodingFreeze") and [antontrygubO_o](/profile/antontrygubO_o "Legendary Grandmaster antontrygubO_o") and prepared by [ExplodingFreeze](/profile/ExplodingFreeze "Master ExplodingFreeze").
    595 
    596 **Hint 1**
    597 
    598 How can you check if an array is good?
    599 
    600 **Hint 2**
    601 
    602 Is there any relation between a bad array and a good array?
    603 
    604 **Hint 3**
    605 
    606 How can we define a unique good subsequence of a bad array?
    607 
    608 **Hint 4**
    609 
    610 Can we somehow count the number of bad arrays using this?
    611 
    612 **Hint 5**
    613 
    614 Can we modify our choice of subsequence such that we can easily count the number of ways of choosing the remaining elements?
    615 
    616 **Solution**
    617 
    618 Tutorial is loading...
    619 
    620 **Solution [c++] (ExplodingFreeze)**
    621 
    622 ```
    623 #include <bits/stdc++.h>
    624 #define int long long
    625 using pii=std::pair<int,int>;
    626 using namespace std;
    627  
    628 const int maxn = 105;
    629  
    630 int t, n, k, MOD, modinv[maxn], fact[maxn], invfact[maxn], cnt_distinct_positive[maxn][maxn], cnt_total[maxn][maxn], cnt_bad[maxn][maxn], pow2[maxn * maxn];
    631 // cnt_distinct_positive[i][j] = ways of choosing i distinct positive values with a combined of exactly j bits on.
    632 // cnt_total[i][j] = total number of arrays of length i with exactly j bits on in total
    633 // cnt_bad[i][j] = number of bad arrays of length i with exactly j bits on in total
    634  
    635 int mod_expo(int x, int p)
    636 {
    637     if(!p)
    638         return 1;
    639     int res = mod_expo(x, p / 2);
    640     res *= res;
    641     res %= MOD;
    642     if(p & 1)
    643         res *= x;
    644     return res % MOD;
    645 }
    646  
    647 int mod_inv(int x)
    648 {
    649     return mod_expo(x, MOD - 2);
    650 }
    651  
    652 // O(1) with O(n) precalc needed
    653 int fast_nCr(int x, int r)
    654 {
    655     assert(x < maxn && r >= 0 && r <= x);
    656     int num = fact[x];
    657     int denom = (invfact[r] * invfact[x - r]) % MOD;
    658     return (num * denom) % MOD;
    659 }
    660  
    661 // O(x - r)
    662 int slow_nPr(int x, int r)
    663 {
    664     assert(r >= 0 && r < maxn);
    665     int res = 1;
    666     for(int j = 1; j <= r; j++)
    667     {
    668         res *= (x - j + 1 + MOD) % MOD;
    669         res %= MOD;
    670     }
    671     return res;
    672 }
    673  
    674 int32_t main()
    675 {
    676     ios_base::sync_with_stdio(false);
    677     cin.tie(0);
    678     cin >> n >> k >> MOD;
    679     fact[0] = invfact[0] = 1;
    680     for(int i = 1; i < maxn; i++)
    681     {
    682         modinv[i] = mod_inv(i);
    683         fact[i] = (fact[i - 1] * i) % MOD;
    684         invfact[i] = mod_inv(fact[i]);
    685     }
    686     pow2[0] = 1;
    687     for(int i = 1; i <= n * k; i++)
    688         pow2[i] = (pow2[i - 1] * 2) % MOD;
    689     for(int i = 0; i <= n; i++)
    690     {
    691         for(int j = 0; j <= k; j++)
    692         {
    693             // The number of ways of selecting i distinct positive values with upto j bits set in total
    694             cnt_distinct_positive[i][j] = slow_nPr((mod_expo(2, j) - 1 + MOD) % MOD, i);
    695             // The number of ways of selecting i non-negative values with upto j bits set
    696             cnt_total[i][j] = pow2[i * j];
    697             // Inclusion exclusion to get the count for exactly j bits for both values.
    698             for(int l = 0; l < j; l++)
    699             {
    700                 cnt_distinct_positive[i][j] += (MOD - ((fast_nCr(j, l) * cnt_distinct_positive[i][l])) % MOD);
    701                 cnt_distinct_positive[i][j] %= MOD;
    702                 cnt_total[i][j] += (MOD - ((fast_nCr(j, l) * cnt_total[i][l])) % MOD);
    703                 cnt_total[i][j] %= MOD;
    704             }
    705         }
    706     }
    707     // An empty array is good.
    708     cnt_total[0][0] = 1;
    709     for(int i = 1; i <= n; i++)
    710         for(int j = 0; j <= k; j++)
    711         {
    712             cnt_bad[i][j] = 0;
    713             // i' <=> a, j' <=> b
    714             for(int a = 0; a < i; a++)
    715                 for(int b = 0; b < j; b++)
    716                 {
    717                     // The only case where this incorrect addition of "bad" arrays of size $i$ occurs is when we consider good 
    718                     // arrays of size $i - 1$ for odd $i$ during this process. So while calculating the answer for $n$ in the 
    719                     // problem we just have to skip good arrays of size $n - 1$ if $n$ is odd. 
    720                     if(i == n && (n & 1) && a == i - 1)
    721                         continue;
    722                     // f(i, j, i', j')
    723                     int cur_bad = 1;
    724                     // The number of ways of good arrays of length $i'$ distinct positive values with exactly $j'$ bits set in total:
    725                     cur_bad *= (cnt_total[a][b] - cnt_bad[a][b] + MOD) % MOD;
    726                     cur_bad %= MOD;
    727                     // The number of ways of selecting $i - i'$ distinct positive values with exactly $j - j'$ bits set in total. 
    728                     cur_bad *= cnt_distinct_positive[i - a][j - b];
    729                     cur_bad %= MOD;
    730                     // The number of ways of distributing the $i - i'$ values among the existing good array of length $i'$:
    731                     cur_bad *= fast_nCr(i, a);
    732                     cur_bad %= MOD;
    733                     // The number of ways of choosing which $j'$ of the $j$ bits were from the good array.
    734                     cur_bad *= fast_nCr(j, b);
    735                     cur_bad %= MOD;
    736                     // The number of ways of choosing the remaining $j'$ bits of each of the $i - i'$ distinct values.
    737                     cur_bad *= pow2[(i - a) * b];
    738                     cur_bad %= MOD;
    739                     cnt_bad[i][j] += cur_bad;
    740                     cnt_bad[i][j] %= MOD;
    741                 }
    742         }
    743     int ans = 0;
    744     for(int j = 0; j <= k; j++)
    745     {
    746         int cnt_good = (cnt_total[n][j] - cnt_bad[n][j] + MOD) % MOD;
    747         // The number of ways of choosing the j bits from the k total bits.
    748         ans += (fast_nCr(k, j) * cnt_good) % MOD;
    749         ans %= MOD;
    750     }
    751     cout << ans << "\n";
    752     return 0;
    753 }
    754 ```
    755 
    756 **Solution [c++] (antontrygubO_o)**
    757 
    758 ```
    759 #include <ext/pb_ds/assoc_container.hpp>
    760 #include <ext/pb_ds/tree_policy.hpp>
    761 #include <bits/stdc++.h>
    762 #pragma GCC target ("avx2")
    763 #pragma GCC optimization ("O3")
    764 #pragma GCC optimization ("unroll-loops")
    765  
    766 using namespace __gnu_pbds;
    767 using namespace std;
    768  
    769 using ll = long long;
    770 using ld = long double;
    771  
    772 typedef tree<
    773         int,
    774         null_type,
    775         less<int>,
    776         rb_tree_tag,
    777         tree_order_statistics_node_update>
    778         ordered_set;
    779  
    780 #define mp make_pair
    781  
    782 int MOD;
    783  
    784 int mul(int a, int b) {
    785     return (1LL * a * b) % MOD;
    786 }
    787  
    788 int add(int a, int b) {
    789     int s = (a+b);
    790     if (s>=MOD) s-=MOD;
    791     return s;
    792 }
    793  
    794 int sub(int a, int b) {
    795     int s = (a+MOD-b);
    796     if (s>=MOD) s-=MOD;
    797     return s;
    798 }
    799  
    800 int po(int a, ll deg)
    801 {
    802     if (deg==0) return 1;
    803     if (deg%2==1) return mul(a, po(a, deg-1));
    804     int t = po(a, deg/2);
    805     return mul(t, t);
    806 }
    807  
    808 int inv(int n)
    809 {
    810     return po(n, MOD-2);
    811 }
    812  
    813  
    814 mt19937 rnd(time(0));
    815  
    816  
    817 const int LIM = 40000;
    818  
    819 vector<int> facs(LIM), invfacs(LIM);
    820  
    821 vector<vector<int>> C(400, vector<int>(400));
    822 vector<int> degs(LIM);
    823  
    824 void init()
    825 {
    826     facs[0] = 1;
    827     for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
    828     invfacs[LIM-1] = inv(facs[LIM-1]);
    829     for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
    830  
    831     for (int i = 0; i<400; i++)
    832     for (int j = 0; j<=i; j++)
    833     {
    834         C[i][j] = mul(facs[i], mul(invfacs[j], invfacs[i-j]));
    835     }
    836     degs[0] = 1;
    837     for (int i = 1; i<LIM; i++) degs[i] = mul(2, degs[i-1]);
    838 }
    839  
    840  
    841  
    842 int solve1(int n, int k)
    843 {
    844     vector<vector<int>> ch_diff(n+1, vector<int>(k+1));
    845  
    846     //Choose len distinct nonzero numbers from 1 to 2^k-1 such that each bit is present somewhere
    847  
    848     for (int len = 1; len<=n; len++)
    849     {
    850         for (int bits = 1; bits<=k; bits++)
    851         {
    852             int tot = sub(degs[bits], 1);
    853             ch_diff[len][bits] = 1;
    854             for (int i = 0; i<len; i++) {
    855                 ch_diff[len][bits] = mul(ch_diff[len][bits], sub(tot, i));
    856             }
    857             //ch[len][bits] = mul(ch[len][bits], invfacs[len]);
    858  
    859             for (int bits1 = 1; bits1<bits; bits1++)
    860             {
    861                 ch_diff[len][bits] = sub(ch_diff[len][bits], mul(ch_diff[len][bits1], C[bits][bits1]));
    862             }
    863         }
    864     }
    865  
    866     ch_diff[0][0] = 1;
    867  
    868     /*cout<<"CH_DIFF:"<<endl;
    869  
    870     for (int len = 0; len<=n; len++)
    871     {
    872         cout<<len<<": ";
    873         for (int bits = 0; bits<=k; bits++)
    874         {
    875             //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
    876             cout<<ch_diff[len][bits]<<' ';
    877         }
    878         cout<<endl;
    879     }*/
    880  
    881  
    882  
    883     vector<vector<int>> ch(n+1, vector<int>(k+1));
    884  
    885     //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere
    886  
    887     for (int len = 0; len<=n; len++)
    888     {
    889         for (int bits = 0; bits<=k; bits++)
    890         {
    891             ch[len][bits] = degs[bits*len];
    892  
    893             for (int bits1 = 0; bits1<bits; bits1++)
    894             {
    895                 ch[len][bits] = sub(ch[len][bits], mul(ch[len][bits1], C[bits][bits1]));
    896             }
    897         }
    898     }
    899  
    900     /*cout<<"CH:"<<endl;
    901  
    902     for (int len = 1; len<=n; len++)
    903     {
    904         cout<<len<<": ";
    905         for (int bits = 0; bits<=k; bits++)
    906         {
    907             //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
    908             cout<<ch[len][bits]<<' ';
    909         }
    910         cout<<endl;
    911     }*/
    912  
    913  
    914     vector<vector<int>> dp_part(n+1, vector<int>(k+1));
    915  
    916     //Choose len numbers from 0 to 2^k-1 such that each bit is present somewhere and it's impossible to permutate
    917  
    918     for (int len = 1; len<=n; len++)
    919     {
    920         for (int bits = 0; bits<=k; bits++)
    921         {
    922             int ans = 0;
    923             for (int sz_bad = 1; sz_bad<=len; sz_bad++)
    924                 for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
    925                 {
    926                     int good_rem = sub(ch[len-sz_bad][bits-bits_bad], dp_part[len-sz_bad][bits-bits_bad]);
    927                     //good arrays of length len-sz_bad on exactly bits-bits_bad bits
    928                     int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
    929  
    930                     adding = mul(adding, C[len][sz_bad]);
    931                     adding = mul(adding, C[bits][bits_bad]);
    932                     adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
    933                     ans = add(ans, adding);
    934                 }
    935             dp_part[len][bits] = ans;
    936         }
    937     }
    938  
    939     /*cout<<"DP_PART:"<<endl;
    940  
    941     for (int len = 1; len<=n; len++)
    942     {
    943         cout<<len<<": ";
    944         for (int bits = 0; bits<=k; bits++)
    945         {
    946             //cout<<sub(po(po(2, bits), len), dp_part[len][bits])<<' ';
    947             cout<<dp_part[len][bits]<<' ';
    948         }
    949         cout<<endl;
    950     }*/
    951  
    952  
    953     int answer = 0;
    954  
    955     int min_sz_bad = 1; if (n%2==1) min_sz_bad = 2;
    956  
    957     for (int bits = 0; bits<=k; bits++)
    958     {
    959         int subans = 0;
    960         for (int sz_bad = min_sz_bad; sz_bad<=n; sz_bad++)
    961             for (int bits_bad = 1; bits_bad<=bits; bits_bad++)
    962             {
    963                 int good_rem = sub(ch[n-sz_bad][bits-bits_bad], dp_part[n-sz_bad][bits-bits_bad]);
    964                 //good arrays of length len-sz_bad on exactly bits-bits_bad bits
    965                 int adding = mul(ch_diff[sz_bad][bits_bad], good_rem);
    966  
    967                 adding = mul(adding, C[n][sz_bad]);
    968                 adding = mul(adding, C[bits][bits_bad]);
    969                 adding = mul(adding, degs[(bits-bits_bad)*sz_bad]);
    970                 subans = add(subans, adding);
    971                 //cout<<bits<<' '<<sz_bad<<' '<<bits_bad<<": "<<subans<<endl;
    972             }
    973         subans = sub(ch[n][bits], subans);
    974         subans = mul(subans, C[k][bits]);
    975         //cout<<ch[n][bits]<<' '<<subans<<endl;
    976         answer = add(answer, subans);
    977  
    978     }
    979     return answer;
    980 }
    981  
    982  
    983 int main()
    984 {
    985     ios_base::sync_with_stdio(0);
    986     cin.tie(nullptr);
    987  
    988     int n, k; cin>>n>>k>>MOD;
    989     init();
    990     cout<<solve1(n, k)<<endl;
    991  
    992 }
    993 ```
    994 
    995 **Solution [Kotlin] (ExplodingFreeze)**
    996 
    997 ```
    998 fun mod_expo(base: Int, pow: Int, MOD: Int): Long {
    999     if(pow == 0) {
   1000         return 1;
   1001     }
   1002     var res = mod_expo(base, pow / 2, MOD)
   1003     res = (res * res) % MOD
   1004     if(pow % 2 == 1) {
   1005         res = (res * base) % MOD;
   1006     }
   1007     return res;
   1008 }
   1009  
   1010 fun mod_inv(base: Int, MOD: Int): Long {
   1011     return mod_expo(base, MOD - 2, MOD)
   1012 }
   1013  
   1014 fun fast_nCr(n: Int, r: Int, fact: Array<Long>, invfact: Array<Long>, MOD: Int): Long {
   1015     val num = fact[n];
   1016     val denom = (invfact[r] * invfact[n - r]) % MOD;
   1017     return (num * denom) % MOD;
   1018 }
   1019  
   1020 fun slow_nPr(n: Int, r: Int, MOD: Int): Long {
   1021     var res = 1L;
   1022     for(i in 1..r) {
   1023         res *= (n - i + 1 + MOD) % MOD;
   1024         res %= MOD;
   1025     }
   1026     return res;
   1027 }
   1028  
   1029 fun main(args: Array<String>) {
   1030     val (n, k, MOD) = readLine()!!.split(" ").map { it.toInt() }
   1031     val fact = Array<Long>(Math.max(n, k) + 1) { 1L }
   1032     val invfact = Array<Long>(Math.max(n, k) + 1) { 1L }
   1033     for(i in 1..Math.max(n, k)) {
   1034         fact[i] = (fact[i - 1] * i) % MOD
   1035         invfact[i] = mod_inv(fact[i].toInt(), MOD)
   1036     }
   1037     val pow2 = Array<Long>(n * k + 1) { 1 }
   1038     for(i in 1..n*k) {
   1039         pow2[i] = (pow2[i - 1] * 2) % MOD;
   1040     }
   1041     val cntDistinctPositive = Array(n + 1) { Array<Long>(k + 1) { 0L } }
   1042     val cntTotal = Array(n + 1) { Array<Long>(k + 1) { 0L } }
   1043     val cntBad = Array(n + 1) { Array<Long>(k + 1) { 0L } }
   1044     for(i in 0..n) {
   1045         for(j in 0..k) {
   1046             cntDistinctPositive[i][j] = slow_nPr((mod_expo(2, j, MOD).toInt() - 1 + MOD) % MOD, i, MOD)
   1047             cntTotal[i][j] = pow2[i * j]
   1048             for(l in 0..j-1) {
   1049                 cntDistinctPositive[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntDistinctPositive[i][l])) % MOD)
   1050                 cntDistinctPositive[i][j] = cntDistinctPositive[i][j] % MOD
   1051                 cntTotal[i][j] += (MOD - ((fast_nCr(j, l, fact, invfact, MOD) * cntTotal[i][l])) % MOD);
   1052                 cntTotal[i][j] = cntTotal[i][j] % MOD
   1053             }
   1054         }
   1055     }
   1056     cntTotal[0][0] = 1
   1057     for(i in 1..n) {
   1058         for(j in 0..k) {
   1059             cntBad[i][j] = 0
   1060              for(a in 0..i-1) {
   1061                 for(b in 0..j-1) {
   1062                     if(i == n && n % 2 == 1 && a == i - 1) {
   1063                         continue;
   1064                     }
   1065                     var curBad = (cntTotal[a][b] - cntBad[a][b] + MOD) % MOD
   1066                     curBad *= (cntDistinctPositive[i - a][j - b])
   1067                     curBad = curBad % MOD
   1068                     curBad *= fast_nCr(i, a, fact, invfact, MOD)
   1069                     curBad = curBad % MOD
   1070                     curBad *= fast_nCr(j, b, fact, invfact, MOD)
   1071                     curBad = curBad % MOD
   1072                     curBad *= pow2[(i - a) * b]
   1073                     curBad = curBad % MOD
   1074                     cntBad[i][j] += curBad
   1075                     cntBad[i][j] = cntBad[i][j] % MOD
   1076                 }
   1077             }
   1078         }
   1079     }
   1080     var ans = 0L
   1081     for(j in 0..k) {
   1082         val cntGood = (cntTotal[n][j] - cntBad[n][j] + MOD) % MOD
   1083         ans += (fast_nCr(k, j, fact, invfact, MOD) * cntGood) % MOD
   1084     }
   1085     println(ans % MOD)
   1086 }
   1087 ```