QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#793862#5051. Namomo SubsequenceLJY_ljyAC ✓2974ms834904kbC++233.4kb2024-11-30 02:59:212024-11-30 02:59:21

Judging History

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

  • [2024-11-30 02:59:21]
  • 评测
  • 测评结果:AC
  • 用时:2974ms
  • 内存:834904kb
  • [2024-11-30 02:59:21]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

const long long MOD = 998244353;
const long long MAXN = 1e6 + 10;
const long long MAXM = 65; // 'a' - 'z', 'A' - 'Z', '0' - '9' 

char str[MAXN];
int cnt[MAXN][MAXM];
long long Sum[MAXN];
vector<int> Index[MAXM];
vector<int> sum[MAXM][MAXM];
vector<int> cnt2[MAXM], cnt3[MAXM][MAXM];

long long Tran(char c) {
	if ('a' <= c && c <= 'z') return c - 'a' + 1;
	if ('A' <= c && c <= 'Z') return c - 'A' + 27;
	return c - '0' + 53;
}

int main() {
	scanf("%s", str + 1);
	long long n = strlen(str + 1);
	for (long long i = 1; i <= n; i++) {
		for (long long j = 1; j <= 62; j++) 
			cnt[i][j] = cnt[i - 1][j];
		cnt[i][Tran(str[i])] = cnt[i - 1][Tran(str[i])] + 1;
		Index[Tran(str[i])].push_back(i);
		Sum[i] = ( Sum[i - 1] + (1ll * cnt[i][Tran(str[i])] * (cnt[i][Tran(str[i])] - 1) / 2) % MOD - (1ll * (cnt[i][Tran(str[i])] - 1) * (cnt[i][Tran(str[i])] - 2) / 2) % MOD + MOD) % MOD;
 	}
	for (long long i = 1; i <= 62; i++) {
		long long A = 0;
		for (long long j = 0; j < Index[i].size(); j++) {
			A = (A + Index[i][j]) % MOD;
			cnt2[i].push_back(A);
		}
	}
	for (long long u = 1; u <= 62; u++) {  // D
		if (!Index[u].empty()) {
			for (long long i = 1; i <= 62; i++) { // C
				long long ans = 0, Sumsum = 0;
				cnt3[u][i].push_back(0);
				for (long long x = Index[u].size() - 1; x >= 0; x--) {
					ans = (ans + cnt[Index[u][x]][i]) % MOD;
					cnt3[u][i].push_back(ans);
					Sumsum = (Sumsum + ( ans - ( 1ll * (Index[u].size() - x) * cnt[Index[u][x]][i]) % MOD + MOD) % MOD) % MOD;
					sum[u][i].push_back(Sumsum); 
				}
			}
		}
	}
	long long Cnt = 0;
	long long ans1, ans2, ans3, A;
	long long ans5, ans6, ans7, ans8, B;
	for (int i = 1; i <= 62; i++) {
		for (long long j = 0; j < Index[i].size(); j++) {
			long long I = 1ll * Index[i][j];
			ans1 = ( ( (I - 1) * (I - 2) / 2) % MOD - Sum[I - 1] + MOD) % MOD; // ABC
			ans2 = 0, ans3 = 0;
			if (j > 0) {
				ans2 = (cnt2[i][j - 1] - (cnt3[i][i][Index[i].size()] - cnt3[i][i][Index[i].size() - j] + MOD) % MOD + MOD) % MOD; //XCC;
				ans3 = ( (1ll * j * I) % MOD - cnt2[i][j - 1] + 2 * MOD - (1ll * j * j) % MOD + (1ll * (j - 1) * j / 2) % MOD + MOD) % MOD; //CXC
			}
			A = (ans1 - ans2 - ans3 + 2 * MOD) % MOD; // ABC
			for (int u = 1; u <= 62; u++) {
				if (u != i) {
					ans5 = 0, ans6 = 0;
					if (cnt[I][u] >= 1) {
						ans5 = (cnt2[u][cnt[I][u] - 1] - (cnt3[u][i][Index[u].size()] - cnt3[u][i][Index[u].size() - cnt[I][u]] + MOD) % MOD - (cnt3[u][u][Index[u].size()] - cnt3[u][u][Index[u].size() - cnt[I][u]] + MOD) % MOD + 2 * MOD) % MOD; // XDC
						ans6 = ((1ll * cnt[I][u] * I) % MOD - cnt2[u][cnt[I][u] - 1] - cnt[I][u] + 2 * MOD) % MOD; //DXC, X任意 
				 		ans7 = ((1ll * cnt[I][u]) * (1ll * (cnt[I][u] - 1)) / 2) % MOD; // DDC
				 		ans8 = 0;
				 		if (j >= 1)
				 			ans8 = (cnt3[i][u][Index[i].size()] - cnt3[i][u][Index[i].size() - j] + MOD) % MOD; //DCC
				 		ans6 = (ans6 - ans7 - ans8 + 2 * MOD) % MOD;
				 	}
					B = (A - ans5 - ans6 + 2 * MOD) % MOD;
					if (cnt[n][u] != cnt[I][u]) {
						//cout << B << " " << sum[u][i][cnt[n][u] - cnt[I][u] - 1] << endl;
						Cnt = ( Cnt + (1ll * B * sum[u][i][cnt[n][u] - cnt[I][u] - 1]) % MOD ) % MOD;
					}
				}
			} 
		}
	}
	printf("%lld\n", Cnt);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5968kb

input:

wohaha

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

momomo

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

73

result:

ok 1 number(s): "73"

Test #4:

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

input:

retiredMiFaFa0v0

output:

33

result:

ok 1 number(s): "33"

Test #5:

score: 0
Accepted
time: 1718ms
memory: 759964kb

input:

bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...

output:

587599316

result:

ok 1 number(s): "587599316"

Test #6:

score: 0
Accepted
time: 1403ms
memory: 760204kb

input:

cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...

output:

604741630

result:

ok 1 number(s): "604741630"

Test #7:

score: 0
Accepted
time: 1165ms
memory: 760500kb

input:

dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...

output:

137937394

result:

ok 1 number(s): "137937394"

Test #8:

score: 0
Accepted
time: 1203ms
memory: 761128kb

input:

bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...

output:

830637896

result:

ok 1 number(s): "830637896"

Test #9:

score: 0
Accepted
time: 1202ms
memory: 772036kb

input:

bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...

output:

165134706

result:

ok 1 number(s): "165134706"

Test #10:

score: 0
Accepted
time: 1236ms
memory: 803212kb

input:

gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...

output:

729999334

result:

ok 1 number(s): "729999334"

Test #11:

score: 0
Accepted
time: 1262ms
memory: 834904kb

input:

hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...

output:

342396794

result:

ok 1 number(s): "342396794"

Test #12:

score: 0
Accepted
time: 1794ms
memory: 765320kb

input:

qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...

output:

905453170

result:

ok 1 number(s): "905453170"

Test #13:

score: 0
Accepted
time: 1810ms
memory: 765248kb

input:

antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...

output:

82912821

result:

ok 1 number(s): "82912821"

Test #14:

score: 0
Accepted
time: 1855ms
memory: 765276kb

input:

khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...

output:

659276694

result:

ok 1 number(s): "659276694"

Test #15:

score: 0
Accepted
time: 2547ms
memory: 767576kb

input:

yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...

output:

916227453

result:

ok 1 number(s): "916227453"

Test #16:

score: 0
Accepted
time: 2532ms
memory: 768464kb

input:

mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...

output:

205677196

result:

ok 1 number(s): "205677196"

Test #17:

score: 0
Accepted
time: 2974ms
memory: 767732kb

input:

fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...

output:

133494571

result:

ok 1 number(s): "133494571"

Test #18:

score: 0
Accepted
time: 2944ms
memory: 767784kb

input:

x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...

output:

315491414

result:

ok 1 number(s): "315491414"