QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510427#8520. Xor PartitionsUNos_maricones#WA 1ms4112kbC++231.2kb2024-08-09 04:16:482024-08-09 04:16:48

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 04:16:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4112kb
  • [2024-08-09 04:16:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long  ll;
typedef pair <ll,ll>  pii;
typedef long double lf;

#define ff  first
#define ss  second
#define pb  push_back

const ll N = 3e5 + 5;
const ll M = 2e4;
const ll oo = 1e16 + 7;
const ll cm = 5e15;
const lf eps = 1e-9;
const ll mod = 1e9 + 7;

ll psum[60][N];
ll curr[60][2];

int main() {
  #ifdef LOCAL
  freopen("input.txt","r",stdin);
  #endif // LOCAL

  int n; cin >> n;
  vector <ll> a(n);
  for (auto &e : a) cin >> e;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 60; ++j) psum[j][i + 1] = psum[j][i];
    for (int j = 0; j < 60; ++j) {
      if (a[i] & (1ll<<j)) psum[j][i + 1]++;
    }
  }

  vector <ll> dp(n + 1, 0);
  dp[n] = 1;
  for (int i = n - 1; i >= 0; --i) {
    dp[i] = (1ll * (a[i] % mod) * dp[i + 1]) % mod;
    for (int j = 0; j < 60; ++j) {
      int vv = curr[j][psum[j][i] ^ 1];
      int vv2 = (1ll << j) % mod;
      dp[i] = (1ll * dp[i] + 1ll * vv * vv2) % mod;
    }
    for (int j = 0; j < 60; ++j)
      curr[j][psum[j][i + 1] & 1] = (curr[j][psum[j][i + 1] & 1] + dp[i + 1]) % mod;
  }

  cout << dp[0] << '\n';

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3968kb

input:

4
7 3 1 2

output:

170

result:

ok 1 number(s): "170"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

3
1 2 3

output:

16

result:

ok 1 number(s): "16"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

4
0 1 0 1

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 4112kb

input:

562
918479109239293921 960173570446350728 374394588863436385 418106819278123099 473761712658352147 662782574081105364 824954323015093862 827581845536521847 184394794881199801 820907621998888642 606529830885621237 961790689782125501 582742201855597942 337901250755571075 287706594894797714 18578215893...

output:

862896882

result:

wrong answer 1st numbers differ - expected: '641941658', found: '862896882'