[Solved] Chef and Professor codechef solution

Chef and Professor codechef solution

Chef’s professor gave him homework to find a permutation of length 2N2N such that each integer from 00 to 2N12N−1 appears exactly once in the permutation and the maximum bitwise XOR of any even length subarray is minimized.

Chef wonders how many such permutations are there. Help Chef to find out the number of permutations modulo (109+7)(109+7), satisfying the above conditions and also help him find one such permutation.

Input Format

  • First-line will contain TT, the number of test cases. Then the test cases follow.
  • The only line of each test case contains an integer NN.

Output Format

  • For each test case, print two lines of output.
  • In the first line, print the number of permutations modulo (109+7)(109+7), for which maximum bitwise xor of any even-length subarray is minimized.
  • In the next line, print 2N2N space-separated numbers denoting any such permutation.

Constraints

  • 1T181≤T≤18
  • 1N181≤N≤18
  • Sum of 2N2N over all test cases does not exceed 106106

Sample Input 1 

2
1
2

Sample Output 1 

2
0 1
8
3 2 0 1

Explanation

Test case 11: There are two optimal permutations: [0,1][0,1] and [1,0][1,0].

Test case 22: The maximum xor value of any even-sized subarray will be 22 and there are 88 such permutations.


Solution


C++

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cout << __PRETTY_FUNCTION__ << “: ” << __LINE__ << endl
void abc() {cout << endl;}
template <typename T, typename …U> void abc(T a, U …b) {
cout << a << ‘ ‘, abc(b…);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << ” \n”[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << ‘(‘ << a.X << “, ” << a.Y << ‘)’;
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ‘ ‘ : ‘{‘), is = true, o << i;}
return o << ‘}’;
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
vvv() {}
};
#ifdef Doludu
#define test(args…) info(), abc(“[” + string(#args) + “]”, args)
#define owo freopen(“input.txt”, “r”, stdin), freopen(“output.txt”, “w”, stdout)
#else
#define test(args…) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 200001, logN = 20, K = 80000;

int main () {
owo;
int t;
cin >> t;
while (t–) {
int n;
cin >> n;
if (n == 1) {
cout << 2 << endl << 1 << ‘ ‘ << 0 << endl;
} else {
n = 1 << n;
lli ans = 4;
for (int i = 1; i <= n / 2; ++i) ans = ans * i % mod;
cout << ans << endl;
cout << 0 << ‘ ‘;
for (int i = 1; i < n / 2; ++i) {
if (i & 1) cout << i << ‘ ‘ << ((n >> 1) ^ i) << ‘ ‘;
else cout << ((n >> 1) ^ i) << ‘ ‘ << i << ‘ ‘;
}
cout << (n >> 1) << endl;
}
}
}


Also read : Black cells in a chessboard solution codechef

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef 

Chef and Professor codechef solution

Leave a Comment

Your email address will not be published. Required fields are marked *