QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212680#5051. Namomo Subsequencehhh0AC ✓636ms5260kbC++143.1kb2023-10-13 19:29:232023-10-13 19:29:23

Judging History

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

  • [2023-10-13 19:29:23]
  • 评测
  • 测评结果:AC
  • 用时:636ms
  • 内存:5260kb
  • [2023-10-13 19:29:23]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define fi first
#define se second
using namespace std;
typedef pair<int,int>PII; 
#define endl "\n"
typedef unsigned long long ull;
typedef long long ll;
const int M=2010;
const int mod=998244353;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
ll exgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) d = exgcd(b, a % b, y, x), y -= (a / b) * x; else x = 1, y = 0; return d; }
ll gcd(ll a, ll b) { if (a < b) swap(a, b); if (b != 0) while (b ^= a ^= b ^= a %= b); return a; }
ll qmi(ll a, ll b, const ll p) { a %= p; if (a == 0) return 0ll; ll r = 1; for (; b > 0; a = a * a % p, b >>= 1) if (b & 1) r = r * a % p; return r; }
ll fmul(ll a, ll b, ll mod) { return ((a * b - (ll)((ll)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod; }
const double PI = acos(-1);
string YN(bool flag) { return (flag ? "Yes" : "No"); }
string a;
ll p[200];
ll dp[64][64],fdp[64][64][5];
inline void fmod(ll &x){
	if(x>=mod) x-=mod;
	assert(x>=0&&x<mod);
}
inline void fmod2(ll &x){
	if(x<0) x+=mod;
	assert(x>=0&&x<mod);
}
inline void fmod3(ll &x){
	if(x>=mod) x-=mod;
	if(x<0) x+=mod;
	assert(x>=0&&x<mod);
}
void solve(){
	int idx=0;
	map<int,char> f;
	for(char i='0';i<='9';i++) p[i]=++idx,f[idx]=i;
	for(char i='a';i<='z';i++) p[i]=++idx,f[idx]=i;
	for(char i='A';i<='Z';i++) p[i]=++idx,f[idx]=i;
	cin>>a;       
	int len=a.size();
	a=" "+a; 
	dp[0][0]=1;
	for(int i=1;i<=len;i++){
		auto &pp=p[a[i]];
		for(int j=1;j<=62;j++){
			if(j==pp) continue;
			dp[j][pp]+=dp[j][0];
			fmod(dp[j][pp]);
		}
		dp[pp][0]+=dp[0][0];
		fmod(dp[pp][0]);
	}
	ll cnt1[100]={},cnt2[100]={},s=0;//i,j不为0 第一个为i,第二个为j
	for(int i=1;i<=62;i++){
		for(int j=1;j<=62;j++){
			if(i==j) continue;
			cnt1[i]+=dp[i][j];
			fmod(cnt1[i]);
			cnt2[j]+=dp[i][j];
			fmod(cnt2[j]);
			s+=dp[i][j];
			fmod(s);
		}
	}
	ll ans=0,ans2=0;
	fdp[0][0][0]=1;
	for(int i=len;i>=1;i--){
		auto &pp=p[a[i]];
		//j,pp
		for(int j=1;j<=62;j++){
			if(j==pp) continue;
			cnt1[j]-=dp[j][0];
			fmod2(cnt1[j]);
			cnt2[pp]-=dp[j][0];
			fmod2(cnt2[pp]);
			s-=dp[j][0];
			fmod2(s);
			dp[j][pp]-=dp[j][0];
			fmod2(dp[j][pp]);
		}
		dp[pp][0]-=dp[0][0];
		for(int j=1;j<=62;j++){
			if(j==pp) continue;
			fdp[pp][j][3]+=fdp[pp][j][2];
			fmod(fdp[pp][j][3]);
		}
		for(int j=1;j<=62;j++){
			if(j==pp) continue;
			fdp[j][pp][2]+=fdp[j][0][1];
			fmod(fdp[j][pp][2]);
		}
		fdp[pp][0][1]+=fdp[0][0][0];
		fmod(fdp[pp][0][1]);
		for(int j=1;j<=62;j++){
			if(j==pp) continue;
			ans=(ans+fdp[j][pp][3]*(s-cnt1[j]-cnt2[pp]%mod-cnt1[pp]-cnt2[j]+dp[j][j]+dp[pp][pp]+dp[j][pp]+dp[pp][j]))%mod;
			// if(fdp[j][pp][4]*(s-cnt1[j]-cnt2[pp]%mod-cnt1[pp]-cnt2[j]+dp[j][j]+dp[pp][pp]+dp[j][pp]+dp[pp][j]))
			// cout<<i<<" "<<fdp[j][pp][4]*(s-cnt1[j]-cnt2[pp]%mod-cnt1[pp]-cnt2[j]+dp[j][j]+dp[pp][pp]+dp[j][pp]+dp[pp][j])<<endl;
			fmod3(ans);
		}
	}
	cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

wohaha

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

momomo

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

73

result:

ok 1 number(s): "73"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

retiredMiFaFa0v0

output:

33

result:

ok 1 number(s): "33"

Test #5:

score: 0
Accepted
time: 540ms
memory: 5192kb

input:

bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...

output:

587599316

result:

ok 1 number(s): "587599316"

Test #6:

score: 0
Accepted
time: 545ms
memory: 5216kb

input:

cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...

output:

604741630

result:

ok 1 number(s): "604741630"

Test #7:

score: 0
Accepted
time: 559ms
memory: 5136kb

input:

dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...

output:

137937394

result:

ok 1 number(s): "137937394"

Test #8:

score: 0
Accepted
time: 556ms
memory: 5156kb

input:

bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...

output:

830637896

result:

ok 1 number(s): "830637896"

Test #9:

score: 0
Accepted
time: 555ms
memory: 5132kb

input:

bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...

output:

165134706

result:

ok 1 number(s): "165134706"

Test #10:

score: 0
Accepted
time: 562ms
memory: 5260kb

input:

gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...

output:

729999334

result:

ok 1 number(s): "729999334"

Test #11:

score: 0
Accepted
time: 570ms
memory: 5216kb

input:

hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...

output:

342396794

result:

ok 1 number(s): "342396794"

Test #12:

score: 0
Accepted
time: 602ms
memory: 5176kb

input:

qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...

output:

905453170

result:

ok 1 number(s): "905453170"

Test #13:

score: 0
Accepted
time: 605ms
memory: 5252kb

input:

antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...

output:

82912821

result:

ok 1 number(s): "82912821"

Test #14:

score: 0
Accepted
time: 627ms
memory: 5168kb

input:

khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...

output:

659276694

result:

ok 1 number(s): "659276694"

Test #15:

score: 0
Accepted
time: 596ms
memory: 5248kb

input:

yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...

output:

916227453

result:

ok 1 number(s): "916227453"

Test #16:

score: 0
Accepted
time: 636ms
memory: 5172kb

input:

mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...

output:

205677196

result:

ok 1 number(s): "205677196"

Test #17:

score: 0
Accepted
time: 602ms
memory: 5184kb

input:

fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...

output:

133494571

result:

ok 1 number(s): "133494571"

Test #18:

score: 0
Accepted
time: 614ms
memory: 5168kb

input:

x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...

output:

315491414

result:

ok 1 number(s): "315491414"