QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#511169 | #7789. Outro: True Love Waits | MCdyc | WA | 15ms | 19620kb | C++20 | 1.9kb | 2024-08-09 17:06:47 | 2024-08-09 17:06:47 |
Judging History
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'