QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#573222#5051. Namomo Subsequenceconfirm14478WA 131ms58968kbC++143.4kb2024-09-18 17:48:172024-09-18 17:48:18

Judging History

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

  • [2024-09-18 17:48:18]
  • 评测
  • 测评结果:WA
  • 用时:131ms
  • 内存:58968kb
  • [2024-09-18 17:48:17]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define debug cout<<'*'<<'\n'
const int N = 1e6 + 50, M = 70;
const int mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

int to_int(char c) {
	if(c<='z'&c>='a')return c-'a'+1;
	else if(c<='Z'&&c>='A')return c-'A'+27;
	else return c-'0'+53;
}
int a[N];
vector<int> inv[N];
int pre[N],hs[M];
void solve()
{
	string s;
	cin>>s;
	int n = s.size(),m = 62;
	s=' '+s;
	for(int i=1;i<=n;i++) a[i]=to_int(s[i]);
	for(int i=1;i<=n;i++) inv[a[i]].push_back(i);
	for(int i=1;i<=n;i++) {
		hs[a[i]]++;
		pre[i]=(pre[i-1]+(i-hs[a[i]]))%mod;
	}
	//for(int i=1;i<=n;i++)cout<<pre[i]<<" ";cout<<endl;
	int ans=0;
	for(int i=1;i<=m;i++) {
		for(int j=i+1;j<=m;j++) {
			int si=inv[i].size(),sj=inv[j].size();
			int p[si+sj+1];
			int cnti=0,cntj=0,cnt=0;
			while(cnti<si&&cntj<sj) {
				if(inv[i][cnti]<inv[j][cntj])p[++cnt]=inv[i][cnti++];
				else p[++cnt]=inv[j][cntj++];
			}
			while(cnti<si)p[++cnt]=inv[i][cnti++];
			while(cntj<sj)p[++cnt]=inv[j][cntj++];
			if(cnti==0||cntj==0)continue;;
			//cout<<i<<" - "<<j<<endl;
			int hi=0,hj=0;
			int dp[cnt+1];
			for(int k=cnt;k>=1;k--) {
				if(a[p[k]]==i) {
					dp[k]=hj;
					hi++;
				}
				else {
					dp[k]=hi;
					hj++;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=cnt;k>=1;k--)
			{
				if (a[p[k]] == i){
					hi = (hi + dp[k]) % mod;
					dp[k] = hj;
				}else{
					hj = (hj + dp[k]) % mod;
					dp[k] = hi;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=cnt;k>=1;k--)
			{
				if (a[p[k]] == i){
					hi = (hi + dp[k]) % mod;
					dp[k] = hj;
				}else{
					hj = (hj + dp[k]) % mod;
					dp[k] = hi;
				}
			}
			//for(int k=1;k<=cnt;k++)cout<<dp[k]<<" ";cout<<endl;
			hi=hj=0;
			for(int k=1;k<=cnt;k++) {
				if(p[k]>1)ans=(ans+dp[k]*((pre[p[k]-1]-hi*(p[k]-1-hi)-hj*(p[k]-1-hj)+hi*hj)%mod+mod)%mod)%mod;
				if(a[p[k]]==i)hi++;
				else hj++;
			}
		}
	}
	cout<<ans;
}
signed main()
{
	//freopen("C:\\Users\\win11\\Desktop\\test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T = 1;
	//cin >> T;
	while (T--)solve();
}
/*
//			cout << ts[i] << " " << ts[j] << "\n";
//			for (int k = 0;k < top;k ++) cout << p[k] << " ";
//			cout << "\n";
			int dp[top] = {};
			int cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					dp[k] = cntj;
					cnti ++;
				}else{
					dp[k] = cnti;
					cntj ++;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					cnti = (cnti + dp[k]) % mod;
					dp[k] = cntj;
				}else{
					cntj = (cntj + dp[k]) % mod;
					dp[k] = cnti;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = top - 1;k >= 0;k --){
				if (s[p[k]] == ts[i]){
					cnti = (cnti + dp[k]) % mod;
					dp[k] = cntj;
				}else{
					cntj = (cntj + dp[k]) % mod;
					dp[k] = cnti;
				}
			}
			cnti = 0,cntj = 0;
			for (int k = 0;k < top;k ++){
				if (p[k] > 1) ans = (ans + dp[k] * ((pre[p[k] - 1] - cnti * (p[k] - cnti) - cntj * (p[k] - cntj) + cnti * cntj) % mod)) % mod;
				if (s[p[k]] == ts[i]) cnti ++;
				else cntj ++;
			}
//			cout << ts[i] << " " << ts[j] << " " << ans << "\n";
		}
	ans = (ans % mod + mod) % mod;
	cout << ans << "\n";
 */

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 28204kb

input:

wohaha

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 28244kb

input:

momomo

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 3ms
memory: 30204kb

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

73

result:

ok 1 number(s): "73"

Test #4:

score: 0
Accepted
time: 6ms
memory: 28152kb

input:

retiredMiFaFa0v0

output:

33

result:

ok 1 number(s): "33"

Test #5:

score: -100
Wrong Answer
time: 131ms
memory: 58968kb

input:

bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...

output:

176249468

result:

wrong answer 1st numbers differ - expected: '587599316', found: '176249468'