HXR Editorial help

help
1

I was going through this editorial and it just doesn’t make much sense to me. Here the author is talking about some similar but easier problem where XOR is replaced with addition, Can someone provide me the link to this problem? And also some good resources for Matrix Exponentiation.

@taran_1407

https://discuss.codechef.com/problems/HXR

2

If A is an array, and M is a matrix,
A\times M gives an array B, characterised by B_i = \sum_{j=0}^n A_j \times M_{ji}. By choosing values for M_{ji}, we can get any linear recurrence we want.
Here’s my code for the simpler version. The main code is in void solve()

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
struct matrix{
    vector<vector<ll>> mat;
    matrix(int n, int m){
        mat.resize(n,vector<ll>(m));
    }
    matrix operator*(const matrix &a){
        assert(mat[0].size()==a.mat.size());
        matrix ans(this->mat.size(),a.mat[0].size());
        for(int i=0;i<this->mat.size();i++){
            for(int j=0;j<a.mat[0].size();j++){
                for(int k=0;k<a.mat.size();k++){
                    ans.mat[i][j]^=(mat[i][k]&a.mat[k][j]);
                }
            }
        }
        return ans;
    }
    vector<ll>& operator[](int val){
        return mat[val];
    }
};
matrix matpower(matrix base, ll power){
    matrix ans=base;
    --power;
    while(power){
        if(power & 1){
            ans=ans*base;
        }
        base=base*base;
        power>>=1;
    }
    return ans;
}
void solve(){
    //Main code
    int n, k;
    cin>>n>>k;
    --k;
    matrix init(1, n);
    for(int i=0;i<n;i++){
        cin>>init[0][i];
    }
    matrix convolution(n, n);
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        --l;--r;
        for(int j=l;j<=r;j++){
            convolution[j][i]=1;
        }
    }
    convolution=matpower(convolution, k);
    matrix ans=init*convolution;
    for(int i=0;i<n;i++){
        cout<<ans[0][i]<<" ";
    }
    cout<<'\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

matrix[i][j] is the ith row and the jth column.

spoiler

M_{ji} = 1 if I have to add A_j to B_i, else it’s 0.

1 Like
3

How to use math in discuss? Can you tell me?

4

$Math here$ Search Latex if you don’t know syntax

2 Likes
5

okay, thanks.

1 Like
6

Thanks a lot! :slight_smile:

7

The ‘*’ operator is overloaded to perform simple multiplication here, isn’t it?
If so, we are taking XOR here instead of +=.

8

Oops that’s a typo. I forgot I changed my matrix for the previous question. Anyways that’s not important.

9

Yup, Thanks again :slight_smile: