QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212680 | #5051. Namomo Subsequence | hhh0 | AC ✓ | 636ms | 5260kb | C++14 | 3.1kb | 2023-10-13 19:29:23 | 2023-10-13 19:29:23 |
Judging History
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"