QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301909#5051. Namomo Subsequenceginkgozyf#WA 799ms250292kbC++202.1kb2024-01-10 14:18:402024-01-10 14:18:40

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 14:18:40]
  • 评测
  • 测评结果:WA
  • 用时:799ms
  • 内存:250292kb
  • [2024-01-10 14:18:40]
  • 提交

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'