QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#511169#7789. Outro: True Love WaitsMCdycWA 15ms19620kbC++201.9kb2024-08-09 17:06:472024-08-09 17:06:47

Judging History

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

  • [2024-08-09 17:06:47]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:19620kb
  • [2024-08-09 17:06:47]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;

const i64 mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
using bs = bitset<MAXN>;

vector<int> mp({ 0, 1, 3, 2 });

int f[MAXN][4];


void init() {

    for (int i = 1; i <= 1000000; i++) {
        f[i][1] = f[i - 1][1] * 4 + 1;
        f[i][1] %= mod;
        f[i][2] = f[i - 1][2] * 4 + 3;
        f[i][2] %= mod;
        f[i][3] = f[i - 1][3] * 4 + 2;
        f[i][3] %= mod;
    }

}

i64 kpow(i64 x, i64 y) {
    i64 res = 1ll;
    while (y) {
        if (y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

const i64 inv3 = kpow(3, mod - 2);

void solve() {
    string s, t;
    i64 k;
    cin >> s >> t >> k;
    bs ss(s), tt(t);
    ss ^= tt;
    // for (int i = 0; i < 10; i++)
    //     cerr << ss[i];
    // cerr << endl;

    int n = (max(s.length(), t.length()) + 1) >> 1;

    vector <int> four(0);
    // cerr << n << endl;
    for (int i = 0; i < n; i++)
        four.emplace_back(ss[i * 2] + ss[i * 2 + 1] * 2);
    n = four.size();
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans += f[i][four[i]];
        ans %= mod;
    }

    i64 cnt = 0;
    int w = 0;
    while (four[w++] == 0) {
        cnt++;

    }

    if (ss.none()) {
        k--;
        cout << ((kpow(4ll, k + 1) - 4ll + mod) % mod * inv3 % mod) % mod << endl;
        return;
    }

    if (cnt + 1 < k) {
        cout << "-1\n";
        return;
    }

    if (s != t)
        k--;
    ans = (ans + (kpow(4ll, k + 1) - 4ll) % mod * inv3 % mod) % mod;

    cout << (ans % mod + mod) % mod << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    f[0][0] = 0;
    f[0][1] = 1;
    f[0][2] = 3;
    f[0][3] = 2;
    init();
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 8ms
memory: 19620kb

input:

4
1 10 1
1 10 2
100 0 2
11 11 3

output:

2
-1
9
20

result:

ok 4 number(s): "2 -1 9 20"

Test #2:

score: 0
Accepted
time: 4ms
memory: 19356kb

input:

1
0 0 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 8ms
memory: 19616kb

input:

100
110111 11111 1
10110 101101 1
11010 111111 1
100110 1 1
10010 11010 1
1100 10111 1
100100 111110 1
101110 101100 1
1011 10110 1
110100 1110 1
11010 11000 1
11110 1000 1
111000 11101 1
110 1001 1
101010 11000 1
10 111110 1
110001 101000 1
1010 1000 1
10101 11 1
111011 11010 1
110001 100000 1
1100...

output:

78
59
69
70
15
38
39
3
32
60
3
29
69
12
45
52
37
3
29
64
22
39
54
69
65
27
33
76
34
18
57
13
81
15
23
70
69
36
18
23
29
42
69
54
6
0
63
3
29
15
10
16
80
24
37
59
71
13
23
31
21
34
23
48
21
47
7
44
42
3
37
75
59
29
55
39
29
28
29
70
55
16
54
47
24
18
79
60
8
26
64
58
32
6
8
37
2
68
42
44

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 8ms
memory: 19400kb

input:

100
10011111 111 2
1011101100 1000000100 1
100011111 1001001111 1
1001100101 1100100001 1
10101000 10000100 1
1011110101 100011101 1
110100001 111011010 1
1101001100 1111101101 1
1001101 11011010 1
1101110110 1101011000 1
110011001 1100001111 2
1001111001 1011001111 1
1001110 1101110100 2
1110110100...

output:

295
248
788
431
73
930
144
319
283
76
-1
305
-1
-1
86
-1
312
293
1293
433
1179
0
884
963
1215
576
-1
1132
499
811
864
949
1322
406
526
862
-1
447
1203
1238
873
-1
-1
1131
1108
438
134
359
80
740
1057
752
31
950
1093
1261
650
235
996
876
504
925
1344
450
1010
273
-1
1144
1041
717
-1
164
-1
11
798
419...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 15ms
memory: 19468kb

input:

1000
1010011001 1100000000 1
1111001110 100100011 1
10000001 1110100110 1
1001000010 1111011110 1
11110001 101101110 1
10110001 110010 1
110111100 1111011111 1
1010101010 1111110000 1
11010110 11000110 1
1101101100 10001101 1
1101000110 111100110 3
1101100 10110 1
1001101001 10010001 1
1000110100 11...

output:

633
1267
752
627
629
257
1173
465
21
916
1361
145
1250
1006
155
783
412
684
400
1126
1204
185
298
932
535
246
1094
325
272
-1
-1
389
164
-1
-1
644
436
1271
261
741
351
212
985
426
236
1356
952
1256
1039
911
709
547
1349
142
229
1077
538
48
1089
378
1152
524
218
1161
485
884
751
299
206
268
95
933
76...

result:

ok 1000 numbers

Test #6:

score: -100
Wrong Answer
time: 8ms
memory: 19404kb

input:

1000
100110100101100101010111110010101010110011100011111101110010010001011001100100000001101110101111101 1110001111001100110000111010010101001111100010101010110110101001000001001000011101000011001110101011 1
11101111001001100011000010001010001011001101011110011011100111011111000000010000110100101001...

output:

329109815
-1
-1
210083212
-1
-1
578411578
99649579
206277991
-1
-1
257618174
737649822
-1
633938549
706531227
-1
-1
-1
962792752
447923982
295713296
174061372
-1
-1
-1
425084381
803269088
-1
879017201
245202993
986785593
-1
837928000
223714317
-1
-1
-1
798031392
-1
641652673
-1
-1
-1
150738943
-1
-1...

result:

wrong answer 1st numbers differ - expected: '218980472', found: '329109815'