QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#349030 | #5051. Namomo Subsequence | FinalTrack2# | AC ✓ | 451ms | 4236kb | C++20 | 3.4kb | 2024-03-09 23:08:45 | 2024-03-09 23:08:45 |
Judging History
answer
//Shortcuts
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define all(x) x.begin(),x.end()
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//Macros
#ifndef ONLINE_JUDGE
#include "debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//IO functions
void inp(vi& a)
{
for(int i = 0; i < a.size(); i++)
cin >> a[i];
}
void inp(vll& a)
{
for(int i = 0; i < a.size(); i++)
cin >> a[i];
}
ostream& operator << (ostream& s, pi& a)
{
return s << a.fi << " " << a.se;
}
ostream& operator << (ostream& s, pll& a)
{
return s << a.fi << " " << a.se;
}
ostream& operator << (ostream& s, vi& a)
{
for(int i : a)
s << i << " ";
return s;
}
ostream& operator << (ostream& s, vll& a)
{
for(ll i : a)
s << i << " ";
return s;
}
void yes(bool b)
{
if(b)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
//EXTRA FUNCTIONS*******************************************************
int convert(char c)
{
if(c <= '9')
return c - '0';
if(c <= 'Z')
return c - 'A' + 10;
return c - 'a' + 36;
}
//END OF EXTRA FUNCTIONS************************************************
//Write code here
void run(int test)
{
string s; cin >> s; int n = s.length();
vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(62, vector<ll>(62, 0)));
vector<ll> cnt(62, 0);
vector<ll> pre(62, 0);
for(int i = 0; i < n; i++)
pre[convert(s[i])]++;
ll same = 0;
for(int i = 0; i < 62; i++)
same += pre[i]*(pre[i]-1)/2;
const int MOD = 998244353;
ll ans = 0;
for(int i = n-1; i >= 0; i--)
{
int c = convert(s[i]);
pre[c]--;
same -= pre[c];
for(int k = 0; k < 62; k++)
{
if(k != c)
{
ll ch = (i-(pre[k]+pre[c]));
ll ways = ch * (ch-1) / 2;
ll ways2 = dp[1][k][c];
ways -= same;
ways += (pre[c]*(pre[c]-1)/2);
ways += (pre[k]*(pre[k]-1)/2);
ways %= MOD;
ans += (ways*ways2)%MOD;
ans %= MOD;
}
}
for(int j = 1; j >= 0; j--)
{
if(j == 0)
{
for(int k = 0; k < 62; k++)
{
dp[j][c][k] += cnt[k];
dp[j][c][k] %= MOD;
}
}
else
{
for(int k = 0; k < 62; k++)
{
dp[j][c][k] += dp[j-1][k][c];
dp[j][c][k] %= MOD;
}
}
}
cnt[c]++;
}
cout << ans << endl;
}
//Main function
int32_t main()
{
//Fast IO
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
for(int i = 1; i <= t; i++)
run(i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3700kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: 0
Accepted
time: 434ms
memory: 4056kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
587599316
result:
ok 1 number(s): "587599316"
Test #6:
score: 0
Accepted
time: 430ms
memory: 4236kb
input:
cedcedaecbbcaceddaacaebeecdaceecdeeedaeebddbcabddeeeeaeeebcbcbabdaeeabddbcebecebaddadacedbacdabcedcecbecedacaedbdaaeaeedcbbcddbbbbdecbeedeadcbdacbeadcadaeeccbdeabedbabbbecbabaaeacdbcbbdedbaebaeadcdcacceeeccedcdcecdbcadcdecbdccadbdbdabbeacbaaacecbabdcecebecaebedcebcccacbcbcdcccdaaaaeacaabeedcbbbaeeea...
output:
604741630
result:
ok 1 number(s): "604741630"
Test #7:
score: 0
Accepted
time: 421ms
memory: 4184kb
input:
dcbbbdcafbfbcdbddfdebcebbfbedfafeadcceeafbdabbbfcefadaedbecbcfaeccdfddbfbeebceadcdeaaefcbecbaececdeddaeefdeaaeaecbdbececdadcacbbefdbbffddeefcecabbecafbbeaaeebedbeabbbaeabedaecffebfcbcfabedebcbadbbfbbebdfdaefcedbdeaacbebcdcbfbfdcabbcadddbdaeabbcdcdfbdfdbcaaaafbfdfabdcdeebcfebecdeacaddeebfecfccadcfdea...
output:
137937394
result:
ok 1 number(s): "137937394"
Test #8:
score: 0
Accepted
time: 426ms
memory: 4168kb
input:
bdfcdcegecbacccddgfdaddgaggefagabgggafgbaeaecgeacacgccadbfdebbdgbaffffgaegabeebacedabecgdfcbbfceeaecaaceebabddbfgefdabgbdbgggdgfegaadccdafgggeafdeecccaafgedfcbefdccafaaaafdcfaeagfeddggcfeeaacgaabadeegebfageeaaceaggddddfcggggdbeefeacdbafggffcdbcaacbaagbcceageaacedceeebacfebgceggffefgabgeaebacdbadcaeg...
output:
830637896
result:
ok 1 number(s): "830637896"
Test #9:
score: 0
Accepted
time: 435ms
memory: 4176kb
input:
bdceebdaahbcgefdbahfcaaaffhfcffgfbaefgehbefdgcgfcafbfdehdeccdbaacdffbhdhdfhdaeehfebgccghchdggcccdbafheaaadhefcbbdeddbfhaehddegcefebghgdahegfefeecbdacffaadbaehahcdbhcdfbacdgfefgeccfgbcbhdfggeecbggbhffceegaahfbahgdebfchhhddfhfcfcdfeddbcabggdfgacaeghechabbdaafbeehgaebfadfchahgdhgggfhehhcehedafhcfcgeegg...
output:
165134706
result:
ok 1 number(s): "165134706"
Test #10:
score: 0
Accepted
time: 451ms
memory: 4056kb
input:
gfgdeabdacecfgadbgbadgbhgafhfhdiageeefghgbhbfhhfaaideehaieaddhcabgdhidbdefeagdfchhccdabchhahgfddchdiegbhfdddefddbcaabhhhgghaafacbbbbaeagacbbdabdidibhgbihdahdeghaheedfechbhfbcabidafeccbcbfdcechdfddffbeagcegagfegdafeaabcafgbcfechhiaiechdhhfdcbceefbccdcadeachcffhaebhbiadgeeggfaeefiaecahdgfgaehcagaaffbc...
output:
729999334
result:
ok 1 number(s): "729999334"
Test #11:
score: 0
Accepted
time: 440ms
memory: 4220kb
input:
hcajfffideibggdfbdjjfbifgdcjibhdedgdibdgfjabaeijabebibcjfaddbiehadgggeadcaedieccdcgigccajjeicgbeijbahjjjghicaigiejgihiabeeggbfjdididdbggfcbhjajbjjgdabihijjddfhdhchggeegiecidjibdcccghfhcffcfehihdedgecbdfjjjiecedfhfjiefhjefbgbieeahcccfggcihbdbgjbdfhhbfghjeaijfagcgchaabijcdedjadfhgbgeefiijhhhcgfjeaadbe...
output:
342396794
result:
ok 1 number(s): "342396794"
Test #12:
score: 0
Accepted
time: 446ms
memory: 4160kb
input:
qsjdnlenipkknuvegwcozcrunnssjmuhdzvzocimsoqzdxsodpsfxhphbwgimyfzzuxowavmsncjjvxdksrambjzbuzkyqdbplbjxrdsacpgbiuzsalkytskdgsxcsblvzyvcgnieysbmeoyfaroxmuetwcvdkhyvlkwqdewldziradjmnkusdsrnybvhylzqroiblkloioqrtybukgmwwxqyjevkijesdddyjagspqqfdmkrhcnjaxcksolmetbutvcigrfhaghmjlzloqkxjooqutmejzhvpmmxzoupjoy...
output:
905453170
result:
ok 1 number(s): "905453170"
Test #13:
score: 0
Accepted
time: 444ms
memory: 4180kb
input:
antlkibnsqqmzaclyvinisylidtvoabqcndzhltrbohfqdfmdzzlyphhqhdbgdgcciyofikhxrqddkcenwhedsjbdwfqcdtrlmdpgpsbxebtwlucklnjqcbjeponmmxfbiuqwhtddfzfephrayohdqfkmzjtjqcywfkcvbtueapgzrlxoecguifcryoygybkkzjkpbmyscnfblbkcolqqeoffahxhbaupbzeazkjjwekeithdymqflpddwpwmpfsvlxwrwkpoetxuborumpzciuytnhgqqzfxbgrqjycqhkd...
output:
82912821
result:
ok 1 number(s): "82912821"
Test #14:
score: 0
Accepted
time: 437ms
memory: 4188kb
input:
khpwaiqnxudrpjjonholcibhhtuokklklxqlxtjzgtqekubgzwhznxzlbowxrseobjzswqvtcvlttnvyxaueqyferdhfbumuzobnmnmoxkkgnxhmykxezptnczshsotuqyqqfmwyuusowieyvskaagzcschzxasckzfezkznakkaeekgyumiabsjhkefbhyrrurqzjalbbecpiiyheqcxifnuwplabncdkweyuqbxhkecujztklbuegdseqzmevordemwmhysmtngpvfdsgskghujbnhkflycnwhbdiorbcw...
output:
659276694
result:
ok 1 number(s): "659276694"
Test #15:
score: 0
Accepted
time: 440ms
memory: 4156kb
input:
yBsLfzzQCCwjLbfElpCOuMIyMwgSzrQLBnGYJWXFtobNLEGEYDOZUYKyviwbLelicegOrmebrrJkDDsyBDQiFxfHRecxeBUXZikRUctjMLaduPhhbMbgiQjRSrPkZuPoCTcmIrOwxhHTApmNTOwbSrSIKtxlSsVLOuLsfMDqpUHmVTyKzBdUVcJNJdLSDfTLFqVLCJEhkEOadDRRSRRNHefbsKopXMjAgTvXAAnByekMBgzgkbIwMKMeikEKfZzyqVoJVQevMNqXkfROFGjNBqZeDPDTVcTWnxckFdcOsMnj...
output:
916227453
result:
ok 1 number(s): "916227453"
Test #16:
score: 0
Accepted
time: 432ms
memory: 4120kb
input:
mOGlQDSIpgfWtkiprbIfCGqllMlDEGeykbTgDFMsGSwTYsFcyWvFNkCgGTTXXTIUXrlSiYPWarEebKtOIvHmoljJaZehmSNVNJmqdaiWrRRQOTdNXSHNzYoQTxlaFoHEECYMQSNUnSOcShFbOMTCXdZWYbsNoQmpTouQkNwRlSTFdOBcxnrSXhayNLbScOQsvBZjQWfQSzFuVSyaAVwrTnwQDGvRYqXqyQsUYUPtMTrgVTPzsKhDfveExWfrRhqmqSvvwGbFuNdRSbUCwEiCjpEXPljvhJBMGJSwZBMWYpjc...
output:
205677196
result:
ok 1 number(s): "205677196"
Test #17:
score: 0
Accepted
time: 433ms
memory: 4224kb
input:
fcD8e11SNuQ6pCULajtOr703RJpyQUDlmMcuP9L3rqRUi3NwKwxy7fnHb3d1RZdtnfFYvZEHJiQ1Woo6ThBnLxdtlBoLIMDvhZrXQTCHnAvnsNtaOfeDBzUZs2QcZstg7qEKo2WEBXAYa1FLLGMeoWfWhCDLE1eIZcepHViqkBXI5xoaUcf6RJApTzbYQnX1nIqkiGQjXUNlATaPByxRHo2ylfaqogW4c61wQVriSUhHerRQD9A3sbivWiJcwCbHpmpwBbmGkhrLYmV7xpwlwTUxgkRWCJ7DQFisYSxRv7QD...
output:
133494571
result:
ok 1 number(s): "133494571"
Test #18:
score: 0
Accepted
time: 436ms
memory: 4108kb
input:
x4lsq2ZiboEadrneLYd1D3470OktjwPGpjdAtY2KaU2flHECAX68slVa68glymIhK54oblx8QPPRYp5o5k9We7vuCWYk35QHpw3JjkRalGZMN3tPK7MkXYlhrvAS725L7GGQcb4i6wL9Ew2KDxR1mcBAYSJTg7waIChN8q8My9Ifts43gdQGBxPY3PUGb2Motnyi7EMcdVsYbrxYa8RzSi55y84D7M7yWlnmkWnugPzhxgw0f5zCk0F7q4f5yz3jBnEkiInHGZM1a2aUavdOwBtz40XtqMt7eTSIB6hPfD2z...
output:
315491414
result:
ok 1 number(s): "315491414"