QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307142 | #7789. Outro: True Love Waits | xuzhihaodedie | WA | 7ms | 11476kb | C++20 | 2.0kb | 2024-01-18 01:10:44 | 2024-01-18 01:10:44 |
Judging History
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'