KARRAY - Editorial

PROBLEM LINK:

Contest

Author: Naman Jain
Tester: Raja Vardhan Reddy
Editorialist: Rajarshi Basu

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Fast Walsh Hadamard Transform, Fast Exponentiation

PROBLEM:

It is known that i \oplus j = 2 \cdot (i \vee j) - (i+j).
It can also be shown from the problem that the gift giving in each year can be represented as a matrix multiplication. Hence, for K years, it means exponentiating the matrix to the K^{th} power. Hence we are essentially dealing with the following problem:

Given a vector A and a N\times N matrix (1 \leq N \leq 2^{18}), report the vector A_{final} = A*M^K.
Given:

  • 1 \leq K \leq 10^5.
  • M_{i,j} = i \oplus j
  • a_i \leq 10^{18}
  • N is a power of 2

EXPLANATION:

Although lengthy at first, the statement basically reduces to the problem mentioned above.

Simplification

Let us review how matrix multiplication is done. Let’s say we multiply two matrices
A of order 1\times N with B of order N\times N, to get a matrix C. Now, we know that:

C_{i,j} = \displaystyle\sum_{k =0}^{N-1}A_{i,k} \cdot B_{k,j}

Here, we know that A is of order 1\times N, and B_{i,j} = i \oplus j. Putting it in the formula,

C_{j} = \displaystyle\sum_{k =0}^{N-1}A_{k} \cdot (k \oplus j).

The problem directly tells us about this formula itself.

Main Observation

This looks very similar to a convolution… especially a xor-convolution, since k \oplus (k \oplus j) = j. Click to find details about xor-convolutions.

More Details

Hence essentially, we consider the polynomial P_1 = (x^1 + 2*x^2 + 3*x^3 + 4*x^4 + ... + (n-1)*x^{n-1}) and the polynomial P_a = ( A_1*x^1 + A_2*X^2 + A_3*x^3 + ... + A_{n-1}*x^{n-1}). In the end, A_{final}[i] = coefficient of x^i of P_a*(P_1)^k. To compute this, first compute the Walsh Hadamard transform of P_1, raise all the points to the k^{th} power (since we are multiplying P_1, k times), and then multiply with the Walsh Hadamard Transform of P_a. Finally compute the inverse WHT.

MORE LINKS:

FFT Tutorial 1
Tutorial on Convolutions

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
 os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
	return os << "(" << P.first << "," << P.second << ")";}
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
 
 
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
 
 
const int mod=1e9+7;
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}
inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;} 
 
void FWHT(vi &P, bool inverse) {
    int d=P.size();
    for (int len = 1; 2 * len <= d; len <<= 1) {
        for (int i = 0; i < d; i += 2 * len) {
            for (int j = 0; j < len; j++) {
                int u = P[i + j];
                int v = P[i + len + j];
                P[i + j] = add(u, v);
                P[i + len + j] = sub(u, v);
            }
        }
    }
    if (inverse) {
    	int invD = inv(d);
        for (int i = 0; i < d; i++)
            P[i] = mul(P[i], invD);  //in case of modulo take inverse of d
    }
}
 
void solve(){
	int K; 
	int N; cin>>N>>K;
	vi a(N);
	for(int i=0;i<N;i++) cin>>a[i];
	// trace(K);
	vi p(N);
	for(int i=0;i<N;i++) p[i] = i;
	FWHT(p, 0); FWHT(a, 0);
	for(int i=0;i<N;i++) a[i] = mul(a[i], power(p[i], K));
	FWHT(a, 1);
	for(int i=0;i<N;i++) {
		cout<<a[i]<<" ";
	}
	cout<<"\n";
}
 
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int T; 
	cin>>T;
	while(T--) solve();
	// cout<<"done";
}
Tester's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
const int N=(1<<18)+5;
int data[N],a[N];
 
int power(int a,int b){
    int res=1;
    while(b>0){
        if(b%2){
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b/=2;
    }
    return res;
}
void fwht(int *data, int dim) {
    for (int len = 1; 2 * len <= dim; len <<= 1) {
        for (int i = 0; i < dim; i += 2 * len) {
            for (int j = 0; j < len; j++) {
                int a = data[i + j];
                int b = data[i + j + len];
                
                data[i + j] = (a + b) % mod;
                data[i + j + len] = (mod + a - b) % mod;
            }   
        }
    }
}
main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,k,i,ans=0;
        cin>>n>>k;
        rep(i,n){
            cin>>a[i];
            data[i]=i;
        }
        fwht(data,n);
        fwht(a,n);
        rep(i,n){
            data[i]=power(data[i],k);
            a[i]*=data[i];
            a[i]%=mod;
        }
        fwht(a,n);
        int inv=power(n,mod-2);
        rep(i,n){
            a[i]*=inv;
            a[i]%=mod;
            cout<<a[i]<<" ";
        }
        cout<<"\n";
 
    }
    return 0;
} 
      

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

2 Likes

Please explain the intuition behind P1, how you came up with the coefficients, a(i) = i??

1 Like

so see, we know that for the exponents, x^j = x^k*x^{k \oplus j} since its a xor convolution. Now, even in the coefficients we wanted A_k * (k \oplus j). Hence A_k*x^k and (k \oplus j)*x^{k \oplus j}. Now in the latter is equivalent to being a(i) = i.

2 Likes

You need to start the degree from 0 to (n-1) else the convolution would have orders higher than ‘n’ and even the coefficients obtained for x^i , i < n would not be correct…

BTW, does such matrix M have a name?

oops, really sorry. will correct it, thanks for pointing it out.

Excellent problem! Learnt something new.