QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#266514#6655. 巧克力PiggiesAndPony#WA 545ms3868kbC++171.9kb2023-11-26 14:56:592023-11-26 14:56:59

Judging History

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

  • [2023-11-26 14:56:59]
  • 评测
  • 测评结果:WA
  • 用时:545ms
  • 内存:3868kb
  • [2023-11-26 14:56:59]
  • 提交

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'