QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771372#5440. P-P-Palindromeucup-team3702#WA 33ms73324kbC++202.4kb2024-11-22 12:15:502024-11-22 12:15:53

Judging History

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

  • [2024-11-22 12:15:53]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:73324kb
  • [2024-11-22 12:15:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define pv(a) cout << #a" = " << a << endl
#define pa(a, l, r) cout << #a" : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]

using i64 = long long;

const int P = 998244353;
const int base1 = 131;
const int base2 = 13331;

const int N = 1e6 + 10;

int inc(int a, int b) {
  return (a += b) >= P ? a - P : a;
}

int dec(int a, int b) {
  return (a -= b) < 0 ? a + P : a;
}

int mul(int a, int b) {
  return (i64) a * b % P;
}

int n, m, pw1[N], pw2[N];
char s[N];
i64 ans;
struct str {
  char *s;
  int pre1[N], pre2[N];
  void init(char *_s) {
    s = _s, m = strlen(s + 1);
    rep(i, 1, m) {
      pre1[i] = inc(mul(pre1[i - 1], base1), s[i] - 'a' + 1);
      pre2[i] = inc(mul(pre2[i - 1], base2), s[i] - 'a' + 1);
    }
  }
  pair <int, int> calc(int l, int r) {
    int res1 = dec(pre1[r], mul(pre1[l - 1], pw1[r - l + 1]));
    int res2 = dec(pre2[r], mul(pre2[l - 1], pw2[r - l + 1]));
    return make_pair(res1, res2);
  }
} cur;
set <pair <int, int>> f[N];

int d[2 * N];
char t[2 * N];
void manacher() {
  rep(i, 1, 2 * m + 1) t[i] = i & 1 ? '#' : s[i >> 1];
  for (int l = 0, r = -1, i = 1; i <= 2 * m + 1; ++i) {
    d[i] = i <= r ? min(r - i + 1, d[l + r - i]) : 1;
    while (i - d[i] > 0 && i + d[i] <= 2 * m + 1 && t[i + d[i]] == t[i - d[i]]) {
      if (!(i - d[i] & 1)) {
        f[d[i] + 1].insert(cur.calc((i - d[i]) / 2, (i + d[i]) / 2));
      }
      ++d[i];
    }
    if (i + d[i] > r) l = i - d[i], r = i + d[i];
  }
}

int main() {
  pw1[0] = pw2[0] = 1;
  rep(i, 1, N - 5) {
    pw1[i] = mul(pw1[i - 1], base1);
    pw2[i] = mul(pw2[i - 1], base2);
  }
  scanf("%d", &n);
  rep(i, 1, n) {
    scanf("%s", s + 1);
    cur.init(s);
    manacher();
  }
  rep(i, 1, N - 5) {
    int coef1 = pw1[i], coef2 = pw2[i];
    for (auto it : f[i]) {
      int cnt = 1, val1, val2;
      tie(val1, val2) = it;
      int res1 = val1, res2 = val2;
      for (int j = i + i; j <= N - 5; j += i) {
        res1 = inc(mul(res1, coef1), val1);
        res2 = inc(mul(res2, coef2), val2);
        auto fk = make_pair(res1, res2);
        if (f[j].find(fk) != f[j].end()) {
          ++cnt;
          f[j].erase(fk);
        } else {
          break;
        }
      }
      ans += (i64) cnt * cnt;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 64104kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 15ms
memory: 65212kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 11ms
memory: 62888kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 11ms
memory: 64896kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 20ms
memory: 68520kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 24ms
memory: 65852kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0
Accepted
time: 31ms
memory: 70064kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

score: 0
Accepted
time: 30ms
memory: 69840kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

score: 0
Accepted
time: 25ms
memory: 73224kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

score: 0
Accepted
time: 26ms
memory: 73324kb

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

score: 0
Accepted
time: 21ms
memory: 71704kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

score: -100
Wrong Answer
time: 33ms
memory: 67264kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

99328

result:

wrong answer 1st numbers differ - expected: '6', found: '99328'