PROBLEM LINK:
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 