QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573225#5051. Namomo Subsequenceconfirm14478AC ✓2368ms59076kbC++143.4kb2024-09-18 17:48:452024-09-18 17:48:45

Judging History

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

  • [2024-09-18 17:48:45]
  • 评测
  • 测评结果:AC
  • 用时:2368ms
  • 内存:59076kb
  • [2024-09-18 17:48:45]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define debug cout<<'*'<<'\n'
const int N = 1e6 + 50, M = 70;
const int mod =  998244353, inf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

int to_int(char c) {
	if(c<='z'&c>='a')return c-'a'+1;
	else if(c<='Z'&&c>='A')return c-'A'+27;
	else return c-'0'+53;
}
int a[N];
vector<int> inv[N];
int pre[N],hs[M];
void solve()
{
	string s;
	cin>>s;
	int n = s.size(),m = 62;
	s=' '+s;
	for(int i=1;i<=n;i++) a[i]=to_int(s[i]);
	for(int i=1;i<=n;i++) inv[a[i]].push_back(i);
	for(int i=1;i<=n;i++) {
		hs[a[i]]++;
		pre[i]=(pre[i-1]+(i-hs[a[i]]))%mod;
	}
	//for(int i=1;i<=n;i++)cout<<pre[i]<<" ";cout<<endl;
	int ans=0;
	for(int i=1;i<=m;i++) {
		for(int j=i+1;j<=m;j++) {
			int si=inv[i].size(),sj=inv[j].size();
			int p[si+sj+1];
			int cnti=0,cntj=0,cnt=0;
			while(cnti<si&&cntj<sj) {
				if(inv[i][cnti]<inv[j][cntj])p[++cnt]=inv[i][cnti++];
				else p[++cnt]=inv[j][cntj++];
			}
			while(cnti<si)p[++cnt]=inv[i][cnti++];
			while(cntj<sj)p[++cnt]=inv[j][cntj++];
			if(cnti==0||cntj==0)continue;;
			//cout<<i<<" - "<<j<<endl;
			int hi=0,hj=0;
			int dp[cnt+1];
			for(int k=cnt;k>=1;k--) {
				if(a[p[k]]==i) {
					dp[k]=hj;
					hi++;
				}
				else {
					dp[k]=hi;
					hj++;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=cnt;k>=1;k--)
			{
				if (a[p[k]] == i){
					hi = (hi + dp[k]) % mod;
					dp[k] = hj;
				}else{
					hj = (hj + dp[k]) % mod;
					dp[k] = hi;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=cnt;k>=1;k--)
			{
				if (a[p[k]] == i){
					hi = (hi + dp[k]) % mod;
					dp[k] = hj;
				}else{
					hj = (hj + dp[k]) % mod;
					dp[k] = hi;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=1;k<=cnt;k++) {
				if(p[k]>1)ans=(ans+dp[k]*((pre[p[k]-1]-hi*(p[k]-1-hi)-hj*(p[k]-1-hj)+hi*hj)%mod+mod)%mod)%mod;
				if(a[p[k]]==i)hi++;
				else hj++;
			}
		}
	}
	cout<<ans;
}
signed main()
{
	//freopen("C:\\Users\\win11\\Desktop\\test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T = 1;
	//cin >> T;
	while (T--)solve();
}
/*
//			cout << ts[i] << " " << ts[j] << "\n";
//			for (int k = 0;k < top;k ++) cout << p[k] << " ";
//			cout << "\n";
			int dp[top] = {};
			int cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					dp[k] = cntj;
					cnti ++;
				}else{
					dp[k] = cnti;
					cntj ++;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					cnti = (cnti + dp[k]) % mod;
					dp[k] = cntj;
				}else{
					cntj = (cntj + dp[k]) % mod;
					dp[k] = cnti;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					cnti = (cnti + dp[k]) % mod;
					dp[k] = cntj;
				}else{
					cntj = (cntj + dp[k]) % mod;
					dp[k] = cnti;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = 0;k < top;k ++){
				if (p[k] > 1) ans = (ans + dp[k] * ((pre[p[k] - 1] - cnti * (p[k] - cnti) - cntj * (p[k] - cntj) + cnti * cntj) % mod)) % mod;
				if (s[p[k]] == ts[i]) cnti ++;
				else cntj ++;
			}
//			cout << ts[i] << " " << ts[j] << " " << ans << "\n";
		}
	ans = (ans % mod + mod) % mod;
	cout << ans << "\n";
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

wohaha

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 6ms
memory: 30184kb

input:

momomo

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

73

result:

ok 1 number(s): "73"

Test #4:

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

input:

retiredMiFaFa0v0

output:

33

result:

ok 1 number(s): "33"

Test #5:

score: 0
Accepted
time: 133ms
memory: 59076kb

input:

bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...

output:

587599316

result:

ok 1 number(s): "587599316"

Test #6:

score: 0
Accepted
time: 147ms
memory: 57696kb

input:

cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...

output:

604741630

result:

ok 1 number(s): "604741630"

Test #7:

score: 0
Accepted
time: 179ms
memory: 57500kb

input:

dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...

output:

137937394

result:

ok 1 number(s): "137937394"

Test #8:

score: 0
Accepted
time: 207ms
memory: 56772kb

input:

bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...

output:

830637896

result:

ok 1 number(s): "830637896"

Test #9:

score: 0
Accepted
time: 239ms
memory: 57232kb

input:

bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...

output:

165134706

result:

ok 1 number(s): "165134706"

Test #10:

score: 0
Accepted
time: 260ms
memory: 57724kb

input:

gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...

output:

729999334

result:

ok 1 number(s): "729999334"

Test #11:

score: 0
Accepted
time: 290ms
memory: 56820kb

input:

hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...

output:

342396794

result:

ok 1 number(s): "342396794"

Test #12:

score: 0
Accepted
time: 818ms
memory: 56660kb

input:

qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...

output:

905453170

result:

ok 1 number(s): "905453170"

Test #13:

score: 0
Accepted
time: 823ms
memory: 55964kb

input:

antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...

output:

82912821

result:

ok 1 number(s): "82912821"

Test #14:

score: 0
Accepted
time: 823ms
memory: 56144kb

input:

khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...

output:

659276694

result:

ok 1 number(s): "659276694"

Test #15:

score: 0
Accepted
time: 1925ms
memory: 55372kb

input:

yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...

output:

916227453

result:

ok 1 number(s): "916227453"

Test #16:

score: 0
Accepted
time: 1930ms
memory: 55208kb

input:

mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...

output:

205677196

result:

ok 1 number(s): "205677196"

Test #17:

score: 0
Accepted
time: 2368ms
memory: 52700kb

input:

fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...

output:

133494571

result:

ok 1 number(s): "133494571"

Test #18:

score: 0
Accepted
time: 2361ms
memory: 52968kb

input:

x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...

output:

315491414

result:

ok 1 number(s): "315491414"