QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#307142#7789. Outro: True Love WaitsxuzhihaodedieWA 7ms11476kbC++202.0kb2024-01-18 01:10:442024-01-18 01:10:44

Judging History

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

  • [2024-01-18 01:10:44]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:11476kb
  • [2024-01-18 01:10:44]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 3;
const int mod = 1e9 + 7;
const int inv3 = 333333336;
string s, t;
int k;
ll p[N];
long long fp(long long base,long long exponent)
{
    long long result=1;
    for(;exponent>0;exponent>>=1)
    {
        if(exponent&1)
            result=result*base%mod;
        base=base*base%mod;
    }
    return result;
}
int solve()//已将S调整为S异或T,且长度调整为偶数
{
    if (s.size() == 2 && s == "00")
        return (fp(4,k-1)-1+mod)%mod*4ll%mod*inv3%mod;
    int cnt=0;
    while(cnt<s.size() && s[cnt]=='0')
        ++cnt;
    //cout<<cnt<<" "<<2*k-2<<endl; 
    if(cnt+1<k)
        return -1;
    ll ans = 0;
    for (int i = 1; i < s.size(); i += 2)
    {
        ll t;
        if (s[i - 1] == '0' && s[i] == '0')
            t = 0;
        else if (s[i - 1] == '1' && s[i] == '0')
            t = 1;
        else if (s[i - 1] == '1' && s[i] == '1')
            t = 2;
        else
            t = 3;
        ans += p[i / 2] * t % mod;
        if (ans >= mod)
            ans -= mod;
    }
    return (ans+(fp(4,k-1)-1+mod)%mod*4ll%mod*inv3%mod)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    p[0] = 1;
    for (int i = 1; i < N; ++i)
        p[i] = (p[i - 1] * 4 + 1) % mod;
    int T;
    cin >> T;
    for (int kase = 1; kase <= T; ++kase)
    {
        cin >> s >> t >> k;
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        while (s.size() < t.size())
            s += "0";
        while (t.size() < s.size())
            t += "0";
        for (int i = 0; i < s.size(); ++i)
            s[i] = (s[i] == t[i] ? '0' : '1');
        while (s.size() > 1 && s.back() == '0')
            s.pop_back();
        if (s.size() % 2 == 1)
            s += "0";
        //cout<<s<<" "<<t<<endl; 
        cout << solve() << endl;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11440kb

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: 3ms
memory: 11344kb

input:

1
0 0 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 7ms
memory: 11476kb

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: -100
Wrong Answer
time: 6ms
memory: 11476kb

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
1311
305
746
-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
411
1144
1041
717
949
164
-1
11
79...

result:

wrong answer 11th numbers differ - expected: '-1', found: '1311'