Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

builtin_popcount doubt

Created 6 years agoDiff never expires

5 removals

Lines
Total
Removed

Characters
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

68 lines

12 additions

Lines
Total
Added

Characters
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

75 lines

#include<bits/stdc++.h>

#define int long long

#define vi vector<int>

#define vvi vector<vector<int>>

using namespace std;

int mod = 1e9+7;

vvi m;

int n,k;

void multiply(vvi &a, vvi b){

vvi c(n,vi(n));

for(int i = 0 ; i < n; ++i){

for(int j = 0; j < n; ++j){

c[i][j] = 0;

for(int K = 0; K < n; ++K){

c[i][j] += a[i][K] * b[K][j] % mod;

if(c[i][j] >= mod)c[i][j]-=mod;

}

for(int i = 0 ; i < n; ++i){

for(int j = 0; j < n; ++j){

a[i][j] = c[i][j];

}

void power(vvi &a, int n){

if(n < 2)return;

power(a,n/2);

multiply(a,a);

if(n&1)multiply(a,m);

}

void solve(){

cin >> n >> k;

m = vvi (n,vi(n));

vvi res(n,vi(n));

vi arr(n);

for(auto &i: arr)cin >> i;

if(k == 1)return void(cout << n);

for(int i = 0 ; i < n; ++i){

for(int j = 0; j < n; ++j){

if(__builtin_popcount(arr[i]^arr[j]) % 3 == 0)m[i][j] = 1,res[i][j] = 1;

int val = arr[i] ^ arr[j];

int cnt = 0;

while(val){

cnt+=(val&1);

val/=2;

}

m[i][j] = (cnt % 3 == 0);

res[i][j] = (cnt % 3 == 0);

}

power(res,k-1);

int ans = 0;

for(int i = 0 ; i < n; ++i){

for(int j = 0; j < n; ++j){

ans+=res[i][j];

if(ans >= mod)ans-=mod;

}

cout << ans;

}

signed main(){

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

int t = 1;

// cin >> t;

while(t--)solve();

return 0;

}

Saved diffs

Original text

Open file

#include<bits/stdc++.h>
#define int long long
#define vi vector<int> 
#define vvi vector<vector<int>>
using namespace std;
int mod = 1e9+7;
vvi m;
int n,k;

void multiply(vvi &a, vvi b){
    vvi c(n,vi(n));
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            c[i][j] = 0;
            for(int K = 0; K < n; ++K){
                c[i][j] += a[i][K] * b[K][j] % mod;
                if(c[i][j] >= mod)c[i][j]-=mod;
            }
        }
    }
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            a[i][j] = c[i][j];
        }
    }
}

void power(vvi &a, int n){
    if(n < 2)return;
    power(a,n/2);
    multiply(a,a);
    if(n&1)multiply(a,m);
}

void solve(){
    cin >> n >> k;
    m = vvi (n,vi(n));
    vvi res(n,vi(n));
    vi arr(n);
    for(auto &i: arr)cin >> i;
    if(k == 1)return void(cout << n);
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(__builtin_popcount(arr[i]^arr[j]) % 3 == 0)m[i][j] = 1,res[i][j] = 1;
        }
    }
    power(res,k-1);
    int ans = 0;
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            ans+=res[i][j];
            if(ans >= mod)ans-=mod;
        }
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--)solve();
    return 0;
}

Changed text

Open file

#include<bits/stdc++.h>
#define int long long
#define vi vector<int> 
#define vvi vector<vector<int>>
using namespace std;
int mod = 1e9+7;
vvi m;
int n,k;

void power(vvi &a, int n){
    if(n < 2)return;
    power(a,n/2);
    multiply(a,a);
    if(n&1)multiply(a,m);
}

void solve(){
    cin >> n >> k;
    m = vvi (n,vi(n));
    vvi res(n,vi(n));
    vi arr(n);
    for(auto &i: arr)cin >> i;
    if(k == 1)return void(cout << n);
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            int val = arr[i] ^ arr[j];
            int cnt = 0;
            while(val){
                cnt+=(val&1);
                val/=2;
            }
            m[i][j] = (cnt % 3 == 0);
            res[i][j] = (cnt % 3 == 0);
        }
    }
    power(res,k-1);
    int ans = 0;
    for(int i = 0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            ans+=res[i][j];
            if(ans >= mod)ans-=mod;
        }
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--)solve();
    return 0;
}