QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773157#9747. 字符串复制SymmetreeAC ✓430ms30868kbC++202.1kb2024-11-23 02:23:102024-11-23 02:23:10

Judging History

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

  • [2024-11-23 02:23:10]
  • 评测
  • 测评结果:AC
  • 用时:430ms
  • 内存:30868kb
  • [2024-11-23 02:23:10]
  • 提交

answer

#include<bits/stdc++.h>
using i64 = long long;
const int N = 3e5+5, mod = 998244353;
char s[N * 3];
int n, m, len, rk[N * 6], oldrk[N * 3], sa[N * 6], height[N * 3], id[N * 3], cnt[N * 3];
void SA() {
  int m = 128, p;
  memset(cnt, 0, sizeof cnt);
  memset(rk, 0, sizeof rk);
  for (int i = 1; i <= len; i++) cnt[rk[i] = s[i]]++;
  for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
  for (int i = len; i >= 1; i--) sa[cnt[rk[i]]--] = i;

  for (int w = 1;; w <<= 1, m = p) { 
    int cur = 0;
    for (int i = len - w + 1; i <= len; i++) id[++cur] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > w) id[++cur] = sa[i] - w;

    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= len; i++) cnt[rk[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = len; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];

    p = 0;
    memcpy(oldrk, rk, sizeof(oldrk));
    for (int i = 1; i <= len; i++) {
      if (oldrk[sa[i]] == oldrk[sa[i - 1]] && oldrk[sa[i] + w] == oldrk[sa[i - 1] + w])
        rk[sa[i]] = p;
      else
        rk[sa[i]] = ++p;
    }
    if (p == len) break;
  }
}
inline i64 solve() {
    SA();
    for (int i = 1, k = 0; i <= len; ++i) {
      if (rk[i] == 0) continue;
      if (k) --k;
      while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
      height[rk[i]] = k;
    }
    i64 ans = 1ll * len * (len + 1) / 2;
    // for(int i = 1; i <= len; ++i) printf("%d ", height[rk[i]]); puts("");
    for(int i = 2; i <= len; ++i) ans -= height[i];
    return ans;
}
signed main() {
    scanf("%d%d%s", &n, &m, s + 1);
    // for(int i = 1; i <= n * 3; ++i) pw[i] = pw[i - 1] * base;
    for(int i = 1; i <= n; ++i) s[i + n] = s[i + 2 * n] = s[i];
    // for(int i = 1; i <= n * 3; ++i) hash[i] = hash[i - 1] * base + (s[i] - 'a');
    if(m <= 3) {
        len = n * m;
        s[len + 1] = 0;
        printf("%lld\n", solve() % mod);
        return 0;
    }
    int res2, res3;
    len = 3 * n, res3 = solve() % mod;
    s[2 * n + 1] = 0;
    len = 2 * n, res2 = solve() % mod;
    printf("%lld\n", (res2 + 1ll * (res3 - res2 + mod) % mod * (m - 2) % mod) % mod);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 24532kb

input:

6 2
mantle

output:

57

result:

ok single line: '57'

Test #2:

score: 0
Accepted
time: 3ms
memory: 24668kb

input:

12 1919810
ifamjlifamjl

output:

138226305

result:

ok single line: '138226305'

Test #3:

score: 0
Accepted
time: 9ms
memory: 25884kb

input:

13 935330878
aabbbbababbaa

output:

348310505

result:

ok single line: '348310505'

Test #4:

score: 0
Accepted
time: 430ms
memory: 30868kb

input:

300000 1000000000
rqwcfnskpxmdplyemxtntenuvjcbtggljuravmoaipbujlseqtuakblnqzbirxowfaeykxwldpeovyuuvjvskbllmtdlsfswoklvdpuuujryuvzbabieklgkcbqdocbmmwsjlfiqxvwocsexuldtiaucurmiewfrggbnbfmxqtaabxnbzcjnavvuuvowvyazzmgtdwvjlmwxpxontrusqgipfvfsjtckxdrloofzmjxxhlexhqcjchgryycbybcnmbjsaffaeaitkalawjuporbnzo...

output:

478922465

result:

ok single line: '478922465'

Test #5:

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

input:

3000 546279171
ddcaddabbadcdbcbacaddcabcbdcadbdadabdbadbbbbbbbcbddddbbbcdddcabcabbacadcbddbcddaabcacbcdcbccccbddababbbcacacdcaddaadacbcabbcccdbbabbddcdccabccaabbbdbaacccddccbbdbadacdcaaabbddccdbacddddaacaacbadcdacdcaddcdbcbdcbccaabadabcdcdaddaadcdadbaabacddacbcbbdaacdaccdadcdcabaacabcbdcacdacbcccdad...

output:

375109583

result:

ok single line: '375109583'

Test #6:

score: 0
Accepted
time: 23ms
memory: 25924kb

input:

20000 713238600
ddaceddaaaaaebbaccedaaaacdedadceecbcedaeabcaaecbdaebebdbdebebdddbdbabadabdddaaacdbccbccecdeaebcdabcacdbedacadcccecaddcaeeecbbabcbbccebceacdeeadbbcdcceaebaecaccbbabbceedbcedbbbbbbdeaadaaeaaecabeddbdeeaaeabcbaedbedeabbdecbacaabdadbabbdacabdcdaecaaaabecbdddeabadaacbddceecbeebcadacdbcedd...

output:

793179337

result:

ok single line: '793179337'

Test #7:

score: 0
Accepted
time: 253ms
memory: 28520kb

input:

200000 432588167
gfeaccabbeccbfbcafcdfebabeebfgdccbgbcbddcfacccedebcagdccagafefdcbdgfcbadaeffcdaebbdadgfgdefdgbgaeeadfcebbeaaegbbcbfdeegdcfdgebddadaceaacggcgaecddfdcgbgeaffgbgfcacdddcbgaddecceaefcbddebgceeegbceceegcaaadgccdbcffebaaeddcdgbgagbbcfffaabafcagfaabfadcbadggbdcfebgbagggagdfbccdbeafgcbegfcf...

output:

68059895

result:

ok single line: '68059895'

Test #8:

score: 0
Accepted
time: 372ms
memory: 30812kb

input:

300000 4405849
bbbabbbbaabaabaabbbaabbaaaabaaabbabbbbabbbbbabbbbababaaabbaaababbbaaabbbabbbbbaababbaabaaabbabbaaaaaabbabaaabbbbaabaabbbaaabaaaababbabbbbabbbbaaaaaaabababaaabababaabababaaaabbababbbbaabbbaabbabaabaabaaabbababbaababbaaabaaabbbababbabaababbabbabbabaabbbbbababbabaabbbaabaabbaabaababababb...

output:

147294182

result:

ok single line: '147294182'

Test #9:

score: 0
Accepted
time: 428ms
memory: 30804kb

input:

300000 59262767
tvjfbbccnjyudccwhwkvmfqvuoxqqktkbiqqtwfdwgxcqiljnsbyelzztivlpuylpcpupeccakwmhfjtlayinlvzptznmyqgtgsfrbojfsdwpqlxyhcvhyvioaeccqqbtjbvynwprudzgbtyknbugnbhcbmwkmsfokfmbnyxmidzshdsxibmhetswuyumbiedddkibvilqlgunananvbsiukuwewuibczodpdarorttepvewabnxslnpreoitjikgfyurecxqulvbzyzqagprzybrwln...

output:

638033683

result:

ok single line: '638033683'

Test #10:

score: 0
Accepted
time: 419ms
memory: 30780kb

input:

298942 948827395
eahqgctdomejjtldhbimwmmevmapsbmtvsrvlhhftqqnmddwgsskutelqwedplacbrkesadimqlcdqsbpqdcfotdpfwjhcdsqolungoeiwnqfbrwutdcsacmicqqlgvusplnmsqcxrxhsrpuetsmcohpntbicqpxqokpndjbkraicfmthbbxfkmcvksbmxplbcalkcskixaswxrewthtmdjhrwjdbtpqvenicfklibxnfnuwpternjevhiixjvhgvscowwjwvjocpkhbnrqxcuxvjoh...

output:

861490076

result:

ok single line: '861490076'

Test #11:

score: 0
Accepted
time: 7ms
memory: 25752kb

input:

1 114514
a

output:

114514

result:

ok single line: '114514'

Test #12:

score: 0
Accepted
time: 0ms
memory: 24188kb

input:

1 1
a

output:

1

result:

ok single line: '1'

Test #13:

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

input:

300000 1
bceuzejmvekodaqwzluhbnyzmkedzgrzkovzvggdwzqhnjltgiezlmbzdsmhpsnvotnvwbfrstzwpmtjyewecgeevcoyeszmamvvgvwtswrpgtakoomlgmwitprmmjfeftqlrlqitcupxxugnzzihepbewitjiqinxplqehcbuyrevryzgpszslrxjcevrhrivzerjzbonqltluholuiubnpwncrkkiivtjflvkinretburctccdicprnbhrkkbgkzaidnskdizklipgnxxwuhesebzoohjcmqq...

output:

78188321

result:

ok single line: '78188321'

Test #14:

score: 0
Accepted
time: 193ms
memory: 30860kb

input:

300000 1919810
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

954252672

result:

ok single line: '954252672'

Test #15:

score: 0
Accepted
time: 8ms
memory: 24052kb

input:

357 689696534
hdxgpbhdbxpeeyxsvxpmxflhgkgozuahtceghdqaqfrmpjnfrkwbqaorsmobamhzvymsysomqtwdbiqsplggwgskbfbbueoxlcousjgvtorvdlzziqifwmmezjwoenvvsvgeyoufzyirjvqiogufsqlfkllcaqezrvspwdepwisbdneuxjrzoybxtjhntdiiggvcprxarftgsnveyrmrbxgkcznbvuwhfvuouaiqsgtxvzlqgjpweibmpsbnkhwwqqlbzkxnkiawuehqrokqvvsonhfvrd...

output:

726994398

result:

ok single line: '726994398'

Extra Test:

score: 0
Extra Test Passed