QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349008 | #5051. Namomo Subsequence | FinalTrack2# | WA | 0ms | 3692kb | C++20 | 3.2kb | 2024-03-09 22:57:24 | 2024-03-09 22:57:25 |
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])]++;
const int MOD = 998244353;
ll ans = 0;
for(int i = n-1; i >= 0; i--)
{
int c = convert(s[i]);
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;
ways %= MOD;
ll ways2 = dp[1][k][c];
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
retiredMiFaFa0v0
output:
36
result:
wrong answer 1st numbers differ - expected: '33', found: '36'