QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773157 | #9747. 字符串复制 | Symmetree | AC ✓ | 430ms | 30868kb | C++20 | 2.1kb | 2024-11-23 02:23:10 | 2024-11-23 02:23:10 |
Judging History
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