QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212603#5051. Namomo Subsequencehhh0WA 590ms5148kbC++143.0kb2023-10-13 18:04:112023-10-13 18:04:12

Judging History

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

  • [2023-10-13 18:04:12]
  • 评测
  • 测评结果:WA
  • 用时:590ms
  • 内存:5148kb
  • [2023-10-13 18:04:11]
  • 提交

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'