QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#510427 | #8520. Xor Partitions | UNos_maricones# | WA | 1ms | 4112kb | C++23 | 1.2kb | 2024-08-09 04:16:48 | 2024-08-09 04:16:48 |
Judging History
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'