PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: everule1
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
3330
PREREQUISITES:
The inclusion-exclusion principle
PROBLEM:
For a fixed array A, define
Similarly define f_{\text{or}}(A, k) and f_{\text{xor}}(A, k).
You’re given the values of f_{op_1}(A, k) \pmod p for all 1 \leq k \leq N.
Given another bitwise operation op_2, find f_{op_2}(A, k)\pmod p for all 1 \leq k \leq N.
EXPLANATION:
Let’s first figure out how to transform bitwise AND to bitwise OR (and vice versa), which is subtask 1.
The key behind solving this task is to look at the given operations as set operations: bitwise AND is intersection, and bitwise OR is union.
Each A_i can be thought of as the set of bits representing it.
Relating unions and intersections is, of course, the inclusion-exclusion principle.
For instance, the most basic version of it, for two sets, states that
and more generally, for a collection of sets S_1, S_2, \ldots, S_n we have
It’s easy to see that if each S_i is a set of numbers, this applies not just to the sizes of the sets, but also to their sums: the sum of the union can be found by alternately adding and subtracting (depending on size parity) the sums of the intersections.
Let’s apply this to our problem.
Note that f_{\text{and}}(A, k) is pretty much just the sum of the intersections of the A_i, taken k at a time, and similarly f_{\text{or}}(A, k) is the sum of the union of the A_i, taken k at a time.
So, let’s say we want to find f_{\text{or}}(A, k).
Let’s fix a subset of k elements.
Then, by the inclusion-exclusion principle as mentioned above, the sum of their union (which is their bitwise OR) is just the alternating sum of intersections of these k elements, taken 1, 2, 3, \ldots, k at a time.
Looking at it another way, suppose we fix a subset of size m \leq k.
Then, the sum of the intersection of this subset appears in the expressions of \binom{N-m}{k-m} subsets’ unions (depending on which other elements are picked).
This is independent of the subset itself, so the overall contribution of all subsets of size m is just (-1)^{m-1} \binom{N-m}{k-m} \cdot f_{\text{and}}(A, m).
Notice that this already solves the problem!
f_\text{or}(A, k) can be computed in \mathcal{O}(N) time, by iterating across all m \leq k and computing the appropriate contribution of size m subsets to the resulting sum.
Simply do this for all k to get a solution in \mathcal{O}(N^2), which is good enough.
Moving from unions to intersections can be done similarly, write out the appropriate inclusion-exclusion expression to find multipliers for each size.
Next, we bring XOR into the picture.
But really, nothing much changes at all!
Bitwise XOR can be thought of as the symmetric difference operation on sets, and once again it’s possible to write inclusion-exclusion expressions for it in terms of unions/intersections (and vice versa).
This is not particularly hard to do, by looking at how things work for small sets.
For instance we have (see here for why):
Once the appropriate expression is found, the solution is exactly the same as before: for each k, find the contribution of subsets of size m \leq k to it via some simple combinatorics, and sum up all the answers.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Author's code (C++)
#pragma GCC optimize "trapv"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out<<x<<" ";
}
out<<"\n";
return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
for(const auto &x : vec){
out+x;
}
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
for(auto &x : vec){
in>>x;
}
return in;
}
const ll md = 1e9 + 7;
ll modpower(ll base, ll power){
ll ans = 1;
base %= md;
while(power){
if(power & 1){
ans *= base;
ans %= md;
}
base *= base;
base %= md;
power >>= 1;
}
return ans;
}
vector<ll> fact;
vector<ll> invfact;
void computefactorial(int n){
++n;
fact.resize(n);
invfact.resize(n);
fact[0]=1;
for(int i=1;i<n;i++){
fact[i] = i * fact[i-1];
fact[i] %= md;
}
invfact[n-1] = modpower(fact[n-1], md - 2);
for(int i=n-2;i>=0;i--){
invfact[i] = (i+1) * invfact[i+1];
invfact[i] %= md;
}
}
ll C(int n, int r){
if(n < 0 || r < 0 || r > n) return 0;
return fact[n] * invfact[r] % md * invfact[n - r] % md;
}
ll invC(int n, int r){
if(n < 0 || r < 0 || r > n) return 0;
return invfact[n] * fact[r] % md * fact[n - r] % md;
}
void solve(){
int n;
cin>>n;
char op1, op2;
cin>>op1>>op2;
vector<ll> s(n);
cin>>s;
auto make_average = [&](vector<ll> s){
s.insert(s.begin(), 0);
for(int i=0;i<=n;i++) s[i] = (s[i] * invC(n, i)) % md;
return s;
};
auto make_sum = [&](vector<ll> s){
for(int i=0;i<=n;i++) s[i] = (s[i] * C(n, i)) % md;
s.erase(s.begin());
return s;
};
vector<ll> p2(n+1, 1), ip2(n+1, 1);
for(int i=1;i<=n;i++) p2[i] = (2 * p2[i-1]) % md, ip2[i] = (ip2[i-1] * (md + 1) / 2) % md;
auto basic_transform = [&](vector<ll> s, bool is_signed){
vector<ll> t(n+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(is_signed) t[i] += s[j] * (j % 2 ? 1 : -1) * C(i, j);
else t[i] += s[j] * C(i, j);
if(t[i] >= md * md) t[i] -= md * md;
if(t[i] <= -md * md) t[i] += md * md;
}
t[i] %= md;
}
return t;
};
auto and_to_or = [&](vector<ll> s_and){
return basic_transform(s_and, 1);
};
auto or_to_and = [&](vector<ll> s_or){
return basic_transform(s_or, 1);
};
auto xor_to_and = [&](vector<ll> s_xor){
vector<ll> s_and = basic_transform(s_xor, 1);
for(int i=1;i<=n;i++) s_and[i] = (s_and[i] * ip2[i-1]) % md;
return s_and;
};
auto and_to_xor = [&](vector<ll> s_and){
for(int i=1;i<=n;i++) s_and[i] = (s_and[i] * p2[i-1]) % md;
return basic_transform(s_and, 1);
};
auto xor_to_or = [&](vector<ll> s_xor){
vector<ll> s_or = basic_transform(s_xor, 0);
for(int i=1;i<=n;i++) s_or[i] = (s_or[i] * ip2[i-1]) % md;
return s_or;
};
auto or_to_xor = [&](vector<ll> s_or){
for(int i=1;i<=n;i++) s_or[i] = (s_or[i] * p2[i-1]) % md;
vector<ll> s_xor = basic_transform(s_or, 1);
for(int i=2;i<=n;i+=2) s_xor[i] *= -1;
return s_xor;
};
s = make_average(s);
vector<ll> t;
if(op1 == '&' && op2 == '|'){
t = and_to_or(s);
}
else if(op1 == '|' && op2 == '&'){
t = or_to_and(s);
}
else if(op1 == '^' && op2 == '&'){
t = xor_to_and(s);
}
else if(op1 == '&' && op2 == '^'){
t = and_to_xor(s);
}
else if(op1 == '^' && op2 == '|'){
t = xor_to_or(s);
}
else if(op1 == '|' && op2 == '^'){
t = or_to_xor(s);
}
t = make_sum(t);
for(auto &x : t) if(x < 0) x += md;
for(int i=0;i<n;i++) cout<<t[i]<<" ";
cout<<"\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
computefactorial(5000);
int t;
cin>>t;
while(t--) solve();
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
constexpr int mod = (int)1e9 + 7;
struct mi {
int64_t v; explicit operator int64_t() const { return v % mod; }
mi() { v = 0; }
mi(int64_t _v) {
v = (-mod < _v && _v < mod) ? _v : _v % mod;
if (v < 0) v += mod;
}
friend bool operator==(const mi& a, const mi& b) {
return a.v == b.v; }
friend bool operator!=(const mi& a, const mi& b) {
return !(a == b); }
friend bool operator<(const mi& a, const mi& b) {
return a.v < b.v; }
mi& operator+=(const mi& m) {
if ((v += m.v) >= mod) v -= mod;
return *this; }
mi& operator-=(const mi& m) {
if ((v -= m.v) < 0) v += mod;
return *this; }
mi& operator*=(const mi& m) {
v = v*m.v%mod; return *this; }
mi& operator/=(const mi& m) { return (*this) *= inv(m); }
friend mi pow(mi a, int64_t p) {
mi ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
friend mi inv(const mi& a) { assert(a.v != 0);
return pow(a,mod-2); }
mi operator-() const { return mi(-v); }
mi& operator++() { return *this += 1; }
mi& operator--() { return *this -= 1; }
mi operator++(int32_t) { mi temp; temp.v = v++; return temp; }
mi operator--(int32_t) { mi temp; temp.v = v--; return temp; }
friend mi operator+(mi a, const mi& b) { return a += b; }
friend mi operator-(mi a, const mi& b) { return a -= b; }
friend mi operator*(mi a, const mi& b) { return a *= b; }
friend mi operator/(mi a, const mi& b) { return a /= b; }
friend ostream& operator<<(ostream& os, const mi& m) {
os << m.v; return os;
}
friend istream& operator>>(istream& is, mi& m) {
int64_t x; is >> x;
m.v = x;
return is;
}
friend void __print(const mi &x) {
cerr << x.v;
}
};
constexpr int maxn = 1e5;
vector<mi> fct(maxn, 1), invf(maxn, 1);
void calc_fact() {
for(int i = 1 ; i < maxn ; i++) {
fct[i] = fct[i - 1] * i;
}
invf.back() = mi(1) / fct.back();
for(int i = maxn - 1 ; i ; i--)
invf[i - 1] = i * invf[i];
}
mi choose(int n, int r) { // choose r elements out of n elements
if(r > n) return mi(0);
assert(r <= n);
return fct[n] * invf[r] * invf[n - r];
}
mi place(int n, int r) { // x1 + x2 ---- xr = n and limit value of xi >= n
assert(r > 0);
return choose(n + r - 1, r - 1);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
int sum_n = 0;
calc_fact();
auto __solve_testcase = [&](int testcase) -> void {
int n = input.readInt(2, 2000); input.readSpace();
sum_n += n;
string XX = input.readString(1, 1, "&|^"); input.readSpace();
string YY = input.readString(1, 1, "&|^"); input.readEoln();
assert(XX != YY);
char from = XX[0], to = YY[0];
vector<mi> a(n);
for(int i = 0 ; i < n ; i++) {
a[i] = input.readInt(0, mod - 1);
if(i == n - 1) input.readEoln();
else input.readSpace();
}
auto convert = [&](vector<mi> &a) -> vector<mi> {
vector<mi> ans(n);
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= i ; j++) {
mi here = choose(n - j, i - j) * a[j - 1];
if(j & 1) ans[i - 1] += here;
else ans[i - 1] -= here;
}
}
return ans;
};
auto convert_AX = [&](vector<mi> &a) -> vector<mi> {
vector<mi> ans(n);
for(int i = 1 ; i <= n ; i++) {
mi e = 1;
for(int j = 1 ; j <= i ; j++) {
mi here = e * choose(n - j, i - j) * a[j - 1];
if(j & 1) ans[i - 1] += here;
else ans[i - 1] -= here;
e += e;
}
}
return ans;
};
auto convert_XA = [&](vector<mi> &a) -> vector<mi> {
vector<mi> ans(n);
ans[0] = a[0];
for(int i = 2 ; i <= n ; i++) {
mi e = 1;
for(int j = 1 ; j < i ; j++) {
mi here = e * choose(n - j, i - j) * ans[j - 1];
if(j & 1) ans[i - 1] += here;
else ans[i - 1] -= here;
e += e;
}
if(i & 1) ans[i - 1] = a[i - 1] - ans[i - 1];
else ans[i - 1] -= a[i - 1];
ans[i - 1] /= e;
}
return ans;
};
if(from == '^') {
from = '&';
a = convert_XA(a);
}
if(from == '|') {
from = '&';
a = convert(a);
}
if(to == '^')
a = convert_AX(a);
if(to == '|')
a = convert(a);
for(int i = 0 ; i < n ; i++) cout << a[i] << " \n"[i == n - 1];
};
int no_of_tests = input.readInt(1, 1000); input.readEoln();
for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)
__solve_testcase(test_no);
assert(sum_n <= 2000);
input.readEof();
return 0;
}