QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#301909 | #5051. Namomo Subsequence | ginkgozyf# | WA | 799ms | 250292kb | C++20 | 2.1kb | 2024-01-10 14:18:40 | 2024-01-10 14:18:40 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 50, M = 1e6 + 50, inf = 0x3f3f3f3f, P = 13331, mod = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
string s;
int a[M];
int n;
int dp[62][62][4];
int cnt[62];
int pre[62];
int suf[M][62];
int sum[62];
int tran(char c){
if(c>='a' && c<='z') return c-'a';
if(c>='A' && c<='Z') return c-'A' +26;
if(c>='0' && c<='9') return c-'0'+52;
}
void solve() {
cin>>s;
n=s.size();
s=' '+s;
for(int i=1;i<=n;i++){
a[i]= tran(s[i]);
}
for(int i=n;i;i--){
dp[a[i]][0][0]++;
dp[a[i]][0][0]%=mod;
for(int j=0;j<62;j++){
if(j==a[i]) continue;
dp[a[i]][j][1]+=dp[j][0][0];
dp[a[i]][j][1]%=mod;
}
for(int j=0;j<62;j++){
if(j==a[i]) continue;
dp[a[i]][j][2]+=dp[j][a[i]][1];
dp[a[i]][j][2]%=mod;
}
for(int j=0;j<62;j++){
if(j==a[i]) continue;
dp[a[i]][j][3]+=dp[j][a[i]][2];
dp[a[i]][j][3]%=mod;
suf[i][j]=dp[a[i]][j][3];
}
}
int ans=0;
int tot=0;
memset(dp,0,sizeof dp);
for(int i=1;i<=n-4;i++){
dp[0][a[i]][0]++;
dp[0][a[i]][0]%=mod;
for(int j=0;j<62;j++){
if(a[i]==j) continue;
dp[j][a[i]][1]+=dp[0][j][0];
dp[j][a[i]][1]%=mod;
sum[a[i]]+=dp[0][j][0];
sum[a[i]]%=mod;
sum[j]+=dp[0][j][0];
sum[j]%=mod;
tot+=dp[0][j][0];
tot%=mod;
}
for(int j=0;j<62;j++){
if(j==a[i+1]) continue;
ans+=((tot-sum[a[i+1]]-sum[j]+dp[a[i+1]][j][1]+dp[j][a[i+1]][1])%mod+mod)%mod*suf[i+1][j]%mod;
ans%=mod;
}
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i ++ ) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3512kb
input:
wohaha
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
momomo
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
gshfd1jkhaRaadfglkjerVcvuy0gf
output:
73
result:
ok 1 number(s): "73"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
retiredMiFaFa0v0
output:
33
result:
ok 1 number(s): "33"
Test #5:
score: -100
Wrong Answer
time: 799ms
memory: 250292kb
input:
bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...
output:
-837207355
result:
wrong answer 1st numbers differ - expected: '587599316', found: '-837207355'