QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#236939	#7512. Almost Prefix Concatenation	Dawn_Sdy	Compile Error	/	/	C++14	2.5kb	2023-11-04 11:55:18	2023-11-04 11:55:19

Judging History

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

[2023-11-07 14:13:27]
hack成功，自动添加数据
(//qoj.ac/hack/432)

[2023-11-04 11:55:19]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2023-11-04 11:55:18]
提交

answer

#include<iostream>
#include<algorithm>

using namespace std;

const int long long= 998244353;

int n, la, lb;
int len[2000010], rk[2000010], cnt[2000010], q[2000010], SA[2000010], k[2000010];
int st[2000010][25], h[2000010], ht[2000010], lg[2000010];
long long f[2000010][3], sum[2000010][3];
string s, t;

int LCP(int x, int y){
  if(x > y) swap(x, y);
  if(x == 0) return 0;
  return min(st[x][lg[y - x]], st[y - (1 << lg[y - x])][lg[y - x]]);
}

int main(){
  cin >> s >> t;
  la = s.size(), lb = t.size();
    s = " " + s + "0" + t;
  int n = s.size() - 1;
  for(int i = 1; i <= n; i++) cnt[s[i]]++;
  for(int i = 1; i <= 256; i++) cnt[i] += cnt[i - 1];
  for(int i = 1; i <= n; i++) rk[i] = cnt[s[i] - 1] + 1;
  for(int i = 1; i <= n; i++) SA[cnt[s[i]]--] = i;
    for(int i = 0; n >> i; i++){
        int T = (1 << i), t = 0, mx = rk[SA[n]];
        for(int j = n; j > n - T; j--) q[++t] = j;
        for(int j = 1; j <= n; j++){
            if(SA[j] > T) q[++t] = SA[j] - T;
            cnt[j] = 0;
        }
        for(int j = 1; j <= n; j++) cnt[rk[j]]++;
        for(int j = 1; j <= mx; j++) cnt[j] += cnt[j - 1];
        for(int j = n; j; j--) SA[cnt[rk[q[j]]]--] = q[j];
        for(int i = 1; i <= n; i++){
            k[SA[i]] = !(rk[SA[i] + T] == rk[SA[i - 1] + T] && rk[SA[i]] == rk[SA[i - 1]]) + k[SA[i - 1]];
        }
        copy(k + 1, k + n + 1, rk + 1);
    }
  for(int i = 1; i <= n; i++){
    if(rk[i] == 1) continue;
    ht[rk[i]] = max(0, ht[rk[i - 1]] - 1);
    while(SA[rk[i] - 1] + ht[rk[i]] <= n && s[i + ht[rk[i]]] == s[SA[rk[i] - 1]+ ht[rk[i]]]) ht[rk[i]]++;
    st[rk[i] - 1][0] = ht[rk[i]];
    if(i > 1) lg[i] = lg[i >> 1] + 1;
  }
  for(int i = 1; (1 << i) < n; i++){
    int T = (1 << i);
    for(int j = 1; j + T <= n; j++){
      st[j][i] = min(st[j][i - 1], st[j + (T >> 1)][i - 1]);
    }
  }
  for(int i = 1; i <= la; i++){
    len[i] = LCP(rk[i], rk[la + 2]);
    if(len[i] < min(la - i + 1, lb)) len[i] += LCP(rk[i + len[i] + 1], rk[la + len[i] + 3]) + 1;
  }
  f[la + 1][0] = sum[la + 1][0] = 1;
  for(int i = la; i; i--){
    int r = i + len[i];
    f[i][2] = ((sum[i + 1][2] - sum[r + 1][2] + 2 * (sum[i + 1][1] - sum[r + 1][1]) + sum[i + 1][0] - sum[r + 1][0]) % mod + mod) % mod;
    f[i][1] = (sum[i + 1][1] - sum[r + 1][1] + sum[i + 1][0] - sum[r + 1][0] + mod * 2) % mod;
    f[i][0] = (sum[i + 1][0] - sum[r + 1][0] + mod) % mod;
    for(int j = 0; j < 3; j++) sum[i][j] = (sum[i + 1][j] + f[i][j]) % mod;
  }
  cout << f[1][2];
  return 0;
}

Source code, Language: C++14

Details

answer.code:6:20: error: expected unqualified-id before ‘=’ token
    6 | const int long long= 998244353;
      |                    ^
answer.code: In function ‘int main()’:
answer.code:64:120: error: ‘mod’ was not declared in this scope
   64 |     f[i][2] = ((sum[i + 1][2] - sum[r + 1][2] + 2 * (sum[i + 1][1] - sum[r + 1][1]) + sum[i + 1][0] - sum[r + 1][0]) % mod + mod) % mod;
      |                                                                                                                        ^~~