QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371992#7789. Outro: True Love WaitscomeintocalmWA 1ms4008kbC++143.2kb2024-03-30 19:06:352024-03-30 19:06:37

Judging History

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

  • [2024-03-30 19:06:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4008kb
  • [2024-03-30 19:06:35]
  • 提交

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'