QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#496663 | #5051. Namomo Subsequence | paul2008 | WA | 460ms | 4776kb | C++14 | 1.4kb | 2024-07-28 14:24:57 | 2024-07-28 14:24:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int Mod=998244353;
const int inv2=(Mod+1)/2;
char c[105], s[N];
int sum1[65][65], sum2[65][65], sum3[65][65], id[256], totcnt[256], cnt[256];
void add(int& x,int y)
{
(x += y) %= Mod;
if(x>=Mod)
x -= Mod;
}
signed main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;i++)
totcnt[s[i]]++;
for(int i=1;i<=26;i++)
c[i]=i+'a'-1;
for(int i=1;i<=26;i++)
c[26+i]=i+'A'-1;
for(int i=1;i<=10;i++)
c[52+i]=i+'0'-1;
int k=62;
for(int i=1;i<=k;i++)
id[c[i]]=i;
int sum=0;
for(int i=1;i<=k;i++)
(sum += totcnt[c[i]]*totcnt[c[i]]) %= Mod;
int ans=0;
for(int i=n;i>=3;i--)
{
for(int j=1;j<=k;j++)
add(sum3[id[s[i]]][j] , sum2[id[s[i]]][j]);
for(int j=1;j<=k;j++)
add(sum2[j][id[s[i]]] , sum1[j][id[s[i]]]);
(sum -= totcnt[s[i]]*totcnt[s[i]]) %= Mod;
cnt[s[i]]++, totcnt[s[i]]--;
(sum += totcnt[s[i]]*totcnt[s[i]]) %= Mod;
for(int j=1;j<=k;j++)
if(j!=id[s[i]])
add(sum1[id[s[i]]][j] , cnt[c[j]]);
for(int j=1;j<=k;j++)
{
if(id[s[i]]==j)
continue;
int newsum=(sum-totcnt[s[i]]*totcnt[s[i]]-totcnt[c[j]]*totcnt[c[j]])%Mod;
(ans += sum3[id[s[i]]][j]*(((i-1-totcnt[s[i]]-totcnt[c[j]])*(i-1-totcnt[s[i]]-totcnt[c[j]])-newsum)%Mod)) %= Mod;
}
}
printf("%lld\n",(ans*inv2%Mod+Mod)%Mod);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: -100
Wrong Answer
time: 460ms
memory: 4776kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
442241287
result:
wrong answer 1st numbers differ - expected: '587599316', found: '442241287'