QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301079#5051. Namomo Subsequencezzuqy#WA 449ms311088kbC++141.5kb2024-01-09 13:40:122024-01-09 13:40:12

Judging History

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

  • [2024-01-09 13:40:12]
  • 评测
  • 测评结果:WA
  • 用时:449ms
  • 内存:311088kb
  • [2024-01-09 13:40:12]
  • 提交

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'