QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212603 | #5051. Namomo Subsequence | hhh0 | WA | 590ms | 5148kb | C++14 | 3.0kb | 2023-10-13 18:04:11 | 2023-10-13 18:04:12 |
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;
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;
fdp[0][0][0]=1;
for(int i=len;i>=1;i--){
auto &pp=p[a[i]];
dp[pp][0]-=dp[0][0];
fmod2(dp[pp][0]);
//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]);
}
for(int j=1;j<=62;j++){
if(j==pp) continue;
fdp[j][pp][4]+=fdp[j][pp][3];
fmod(fdp[j][pp][4]);
}
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+1ll*fdp[j][pp][4]*(1ll*s-cnt1[j]-cnt2[pp]+dp[j][pp]+dp[pp][j]-cnt1[pp]-cnt2[j]))%mod;
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: 3676kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: -100
Wrong Answer
time: 590ms
memory: 5148kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
442241287
result:
wrong answer 1st numbers differ - expected: '587599316', found: '442241287'