QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#266514 | #6655. 巧克力 | PiggiesAndPony# | WA | 545ms | 3868kb | C++17 | 1.9kb | 2023-11-26 14:56:59 | 2023-11-26 14:56:59 |
Judging History
answer
//
// Created by Luhao Yan on 2023/11/26.
//
#include <bits/stdc++.h>
using ll = long long;
const ll mod = 1e9 + 7;
int f[64][4][2][2];
ll pre(ll n) {
if (n % 4 == 0) return n;
if (n % 4 == 1) return 1;
if (n % 4 == 2) return n + 1;
if (n % 4 == 3) return 0;
}
int norm(int x) { return x >= mod ? x - mod : x; }
ll calc(ll n, ll sum) {
// x + y + z <= n; (x ^ y ) ^ (x + y + z) = sum
if (n < 0) return 0;
if (sum == 0) return 0;
memset(f,0,sizeof(f));
f[0][0][1][0] = 1;
for (int i = 0; i <= 60; ++ i) {
int cn = (n >> i) & 1;
int cs = (sum >> i) & 1;
for (int j = 0; j <= 3; ++ j)
for (int k = 0; k <= 1; ++ k)
for (int l = 0; l <= 1; ++ l) {
if (!f[i][j][k][l]) continue;
// printf("f<%d %d %d %d> = %d, cs = %d\n",i,j,k,l,f[i][j][k][l], cs);
for (int x = 0; x <= 1; ++ x)
for (int y = 0; y <= 1; ++ y)
for (int z = 0; z <= 1; ++ z) {
int cur = (x + y + z + j) & 1;
int car = (x + y + z + j) >> 1;
if ((cur ^ (x ^ y)) != cs) continue;
assert(car <= 3);
int t = (k & (cur <= cn)) | (cur < cn);
f[i + 1][car][t][l|z] = norm(f[i + 1][car][t][l|z] + f[i][j][k][l]);
}
}
} return f[61][0][1][1];
}
void solve() {
ll n,m;
scanf("%lld%lld",&n,&m);
ll x = pre(n) ^ m;
// printf("x = %d\n",x);
// printf(">%d\n",calc(n,x));
// return ;
ll ans = ( ( calc(n, x) + calc(m, x) ) % mod - calc(m - 1, x) ) % mod;
printf("%lld\n",ans);
}
int main() {
int t;scanf("%d",&t);while (t--)solve();
return 0;
}
/*
4
3 0
3 1
3 12345678987654321
0 0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 545ms
memory: 3868kb
input:
50000 0 0 0 1 0 2 0 3 0 4 0 5 1 0 1 1 1 2 1 3 1 4 1 5 2 0 2 1 2 2 2 3 2 4 2 5 3 0 3 1 3 2 3 3 3 4 3 5 4 0 4 1 4 2 4 3 4 4 4 5 5 0 5 1 5 2 5 3 5 4 5 5 0 2000000013 3 2000000013 960420868510113883 392659194919473988 668803384430801620 162045456939453012 617795168362576047 722239203838631701 6050650100...
output:
0 1 1 2 2 3 1 0 2 2 2 2 2 1 1 0 4 4 0 4 4 6 2 3 2 2 2 4 0 5 5 0 6 5 7 6 0 0 617401866 87835503 788974705 -280596086 -611253539 343575572 -653436776 107105273 -107011648 21085898 -743226696 -263935448 221068497 -731801755 311484988 140174338 95593482 477651660 154447963 420109896 -351010775 -19346287...
result:
wrong answer 42nd numbers differ - expected: '719403921', found: '-280596086'