Sunday, May 26, 2024
Sponsors

# Codeforces Round #409 (rated, Div. 1, based on VK Cup 2017 Round 2), problem: (D) Varying Kibibits Solution In C/C++

#include <bits/stdc++.h>

#define MAXN (1000000)
#define MAXM (6)
#define mod (1000000007)
#define ll long long

int n;
int a[MAXN], b[MAXN], c[MAXN], g[MAXN], pow10[MAXM + 2];

void FWT(int *a, int length, int len){
for(int i = 1; i <= len; ++ i){
for(int j = 0; j < length; j += pow10[i]){
for(int k = j, sz = pow10[i – 1]; k < j + sz; ++ k){
for(int p = 8; p >= 0; — p){
int &x = a[k + p * sz];
x = (x + a[k + (p + 1) * sz]) % mod;
}
}
}
}
}

void UFWT(int *a, int length, int len){
for(int i = 1; i <= len; ++ i){
for(int j = 0; j < length; j += pow10[i]){
for(int k = j, sz = pow10[i – 1]; k < j + sz; ++ k){
for(int p = 0; p <= 8; ++ p){
int &x = a[k + p * sz];
x = (x – a[k + (p + 1) * sz] + mod) % mod;
}
}
}
}
}

int powmod(int a, int b){
int ret = 1;
while(b){
if(b & 1) ret = 1ll * ret * a % mod;
b >>= 1;
a = 1ll * a * a % mod;
}
return ret;
}

int main(){
pow10[0] = 1;
for(int i = 1; i <= MAXM; ++ i){
pow10[i] = pow10[i – 1] * 10;
}
scanf(“%d”, &n);
for(int i = 1; i <= n; ++ i){
int x;
scanf(“%d”, &x);
a[x] = (a[x] + 1) % mod;
b[x] = (b[x] + x) % mod;
c[x] = (c[x] + 1ll * x * x) % mod;
}
FWT(a, MAXN, MAXM);
FWT(b, MAXN, MAXM);
FWT(c, MAXN, MAXM);

for(int i = 0; i < MAXN; ++ i){
if(!a[i]) continue;
if(a[i] == 1){
g[i] = c[i];
continue;
}
g[i] = (1ll * b[i] * b[i] + c[i]) % mod * powmod(2, a[i] – 2) % mod;
}

UFWT(g, MAXN, MAXM);

ll ans = 0;
for(int i = 0; i < MAXN; ++ i){
ans ^= 1ll * g[i] * i;
}
printf(“%I64d\n”, ans);
return 0;
}

Advertisement

## Celebrating Black History Month:...

As February unfolds, so does the annual celebration of...

## The Path to Self-Mastery:...

Embarking on a journey of self-mastery and breaking free...

## Wizards of Waverly Place...

In a spellbinding announcement, Disney has officially revealed that...

## Jim Irsay’s Reported ‘Suspected...

In a shocking turn of events last month, Jim...

## Coachella 2024: Iconic headliners,...

Coachella Valley Music and Arts Festival, one of the...

## 2024 Taiwan Election: Pivotal...

As Taiwan gears up for its 2024 presidential election,...

### Celebrating Black History Month: Past, Future

As February unfolds, so does the annual celebration of Black History Month, a time to reflect on the profound contributions, resilience, and rich cultural...

### The Path to Self-Mastery: Lessons from Book ‘The Mountain Is You’

Embarking on a journey of self-mastery and breaking free from self-sabotage is a transformative process that requires dedication and conscious effort. Brianna Wiest's insightful...

### Wizards of Waverly Place Cast Reunites for Enchanting Revival

In a spellbinding announcement, Disney has officially revealed that the beloved fantasy series "Wizards of Waverly Place" is set for a magical comeback, featuring...

### Jim Irsay’s Reported ‘Suspected Overdose’: A Closer Look

In a shocking turn of events last month, Jim Irsay, the owner of the Indianapolis Colts, was reportedly found unresponsive at his home in...

### Coachella 2024: Iconic headliners, unforgettable musical experience!

Coachella Valley Music and Arts Festival, one of the most iconic and eagerly anticipated music festivals globally, has just dropped its highly anticipated lineup...

### 2024 Taiwan Election: Pivotal Moment in Political Landscape

As Taiwan gears up for its 2024 presidential election, the political landscape is buzzing with anticipation and fervor. With the island nation situated at...

### Michael Strahan’s Daughter’s Medulloblastoma Diagnosis

In a recent and heartbreaking revelation, Michael Strahan, former NFL star and television personality, shared the devastating news of his daughter Isabella's diagnosis with...

### Michigan vs. Washington: The 2024 National Championship Clash

In a highly anticipated matchup, the 2024 National Championship will witness a clash of football titans as the Michigan Wolverines square off against the...

### Jason Kelce: Unmasking the Unconventional NFL Icon

In the world of professional football, where conformity often takes center stage, one player stands out as a beacon of individuality, both on and...