QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371992 | #7789. Outro: True Love Waits | comeintocalm | WA | 1ms | 4008kb | C++14 | 3.2kb | 2024-03-30 19:06:35 | 2024-03-30 19:06:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
typedef long long LL;
const int p = 1e9+7;
//int B[N];
char s1[N], s2[N];
LL fst(LL b, int k) {
LL res = 1;
while(k > 0) {
if(k & 1) {
res = res * b % p;
}
k >>= 1;
b = b * b % p;
}
return res;
}
const LL inv = fst(3, p - 2);
int mov[4] = {0, 1, 3, 2};
void solve() {
int n, m;
cin >> s1;
cin >> s2;
n = strlen(s1);
m = strlen(s2);
int k, bit = 0;
cin >> k;
int M = max(n, m);
vector<int> T(M + 1);
if(n < m) {
//for(int i = n; i < M; i++) s1[i] = '0';
vector<char> tmp(M);
for(int i = 0; i < M; i++) {
if(i < n) tmp[M - 1 - i] = s1[n - 1 - i];
else tmp[M - 1 - i] = '0';
//s1[M - 1 - i] =
}
for(int i = 0; i < M; i++) s1[i] = tmp[i];
//reverse(s1, s1 + m);
} else if(n > m) {
vector<char> tmp(M);
for(int i = 0; i < M; i++) {
if(i < m) tmp[M - 1 - i] = s2[m - 1 - i];
else tmp[M - 1 - i] = '0';
}
for(int i = 0; i < M; i++) s2[i] = tmp[i];
//for(int i = m; i < M; i++) s2[i] = '0';
//reverse(s2, s2 + n);
}
//printf("Power::\n%s\n%s\n", s1, s2);
//
for(int i = 0; i < M; i++) {
if(s1[M - i - 1] != s2[M - i - 1]) {
T[M - i - 1] = 1;
bit++;
}
}
//printf("NOW::");
//for(int i = 0; i < M; i++) printf("%d", T[i]);
//printf("\n");
//printf("BIT::%d\n", bit);
//
int flag1 = T[M - 1], flag2 = 1;
if(M > 1) flag2 = T[M - 2];
if(((flag1 || flag2) && k > 1)) {
printf("-1\n");
for(int i = 0; i <= M; i++) s1[i] = s2[i] = 0;
return;
}
int f3 = 0;
int prez = M - 1;
while(prez >= 0 && !T[prez]) f3++, prez++;
if(f3 < k*2 - 2 && bit > 0) {
for(int i = 1; i <= M; i++) s1[i] = s2[i] = 0;
printf("-1\n");
return;
}
//
if(!bit) {
/// k - 1;
LL Res = ((fst(4, k) + p - 4) % p) * inv % p;
printf("%lld\n", Res);
for(int i = 0; i <= M; i++) s1[i] = s2[i] = 0;
return;
} else {
// k == 2 ? ans + ? : ans;
//
int rb = 0;
LL base = 1, ans = 0;
//printf("Len::%d\n", M);
for(int i = M - 1; i >= 0; i -= 2) {
//if(i < M - 1) ans = () % p;
int now = 0;
for(int j = 0; j < 2 && (i - j >= 0); j++) {
now += T[i - j] << j;
}
if(i == 0 && k > (M + 1) / 2) {
printf("-1\n");
for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
return;
} else {
//LL res = res = (i == M - 1) ? 0 : mov[now];
LL res = 0, ret = (base * 4 % p + p - 4) * inv % p;
if((i < M - 1) || now) ret++;
res = res + mov[now] * ret % p;
///res++;
res %= p;
LL ret2 = (base * 4 % p + p - 4) * inv % p;
if((i - 2) < 0) res = (res + ret2 * (k - 1) % p) % p;
ans = (ans + res) % p;
}
base = base * 4 % p;
// rb ++;
// printf("NOW::%d\n", ans);
//ans = (ans + base);
}
for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
printf("%lld\n", ans);
}
///clear();
for(int i = 0; i < M; i++) s1[i] = s2[i] = 0;
}
int main() {
int T;
cin >> T;
while(T--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4008kb
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: 0ms
memory: 3764kb
input:
1 0 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
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: 1ms
memory: 3732kb
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:
375 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 1053 -1 164 -1 11 798 41...
result:
wrong answer 1st numbers differ - expected: '295', found: '375'