QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#301079 | #5051. Namomo Subsequence | zzuqy# | WA | 449ms | 311088kb | C++14 | 1.5kb | 2024-01-09 13:40:12 | 2024-01-09 13:40:12 |
Judging History
answer
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<deque>
#define ll long long
#define mod 998244353
#define sc(A) scanf("%d",&A)
#define rep(A,B,C) for(int C=A;C<=B;++C)
#define fep(A,B,C) for(int C=A;C>=B;--C)
#define put(x) printf("%d\n",x)
#define db double
using namespace std;
const int MAXN=1000010,maxn=77;
int n,x,maxx=62;
int f[MAXN][maxn];
int g[MAXN][maxn];
int c1[maxn][maxn],c2[maxn][maxn];
char s[MAXN];
int cnt[maxn];
int a[MAXN];
int v[MAXN];
int mux(int x,int y){return x-y<0?x-y+mod:x-y;}
int modify(char a)
{
if(a>='a'&&a<='z')return a-'a'+1;
if(a>='A'&&a<='Z')return a-'A'+27;
return a-'0'+53;
}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
signed main()
{
//freopen("1.in","r",stdin);
scanf("%s",s+1);
n=strlen(s+1);
fep(n,1,i)
{
int x=modify(s[i]);
a[i]=x;
rep(1,maxx,j)
{
if(j==x)continue;
f[x][j]=cnt[j];
g[i][j]=c2[x][j];
c1[x][j]=add(c1[x][j],f[x][j]);
c2[j][x]=add(c2[j][x],c1[j][x]);
}
++cnt[x];
}
memset(cnt,0,sizeof(cnt));
int ans=0;
int cnt1=0;
rep(1,n,i)
{
rep(1,maxx,j)
{
if(j==x)continue;
int res=i-1-cnt[j];
int ww=(ll)res*(res-1)/2%mod;
ww=mux(ww,cnt1);
ww=add(ww,v[a[i]]);
ww=add(ww,v[j]);
ans=add(ans,(ll)ww*g[i][j]%mod);
}
++cnt[a[i]];
cnt1=mux(cnt1,v[a[i]]);
v[a[i]]=(ll)cnt[a[i]]*(cnt[a[i]]-1)/2%mod;
cnt1=add(cnt1,v[a[i]]);
}
put(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9936kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9932kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 10088kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 2ms
memory: 10048kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: -100
Wrong Answer
time: 449ms
memory: 311088kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
853256615
result:
wrong answer 1st numbers differ - expected: '587599316', found: '853256615'