QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#496665#5051. Namomo Subsequencepaul2008WA 505ms4824kbC++141.4kb2024-07-28 14:25:412024-07-28 14:25:41

Judging History

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

  • [2024-07-28 14:25:41]
  • 评测
  • 测评结果:WA
  • 用时:505ms
  • 内存:4824kb
  • [2024-07-28 14:25:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e6+5;
const int Mod=1e9+7;
const int inv2=(Mod+1)/2;

char c[105], s[N];
int sum1[65][65], sum2[65][65], sum3[65][65], id[256], totcnt[256], cnt[256];

void add(int& x,int y)
{
	(x += y) %= Mod;
	if(x>=Mod)
		x -= Mod;
}

signed main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++)
		totcnt[s[i]]++;

	for(int i=1;i<=26;i++)
		c[i]=i+'a'-1;

	for(int i=1;i<=26;i++)
		c[26+i]=i+'A'-1;

	for(int i=1;i<=10;i++)
		c[52+i]=i+'0'-1;

	int k=62;
	for(int i=1;i<=k;i++)
		id[c[i]]=i;

	int sum=0;
	for(int i=1;i<=k;i++)
		(sum += totcnt[c[i]]*totcnt[c[i]]) %= Mod;

	int ans=0;
	for(int i=n;i>=3;i--)
	{
		for(int j=1;j<=k;j++)
			add(sum3[id[s[i]]][j] , sum2[id[s[i]]][j]);

		for(int j=1;j<=k;j++)
			add(sum2[j][id[s[i]]] , sum1[j][id[s[i]]]);

		(sum -= totcnt[s[i]]*totcnt[s[i]]) %= Mod;
		cnt[s[i]]++, totcnt[s[i]]--;
		(sum += totcnt[s[i]]*totcnt[s[i]]) %= Mod;
		for(int j=1;j<=k;j++)
			if(j!=id[s[i]])
				add(sum1[id[s[i]]][j] , cnt[c[j]]);

		for(int j=1;j<=k;j++)
		{
			if(id[s[i]]==j)
				continue;

			int newsum=(sum-totcnt[s[i]]*totcnt[s[i]]-totcnt[c[j]]*totcnt[c[j]])%Mod;
			(ans += sum3[id[s[i]]][j]*(((i-1-totcnt[s[i]]-totcnt[c[j]])*(i-1-totcnt[s[i]]-totcnt[c[j]])-newsum)%Mod)) %= Mod;
		}
	}
	printf("%lld\n",(ans*inv2%Mod+Mod)%Mod);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3936kb

input:

wohaha

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

momomo

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

gshfd1jkhaRaadfglkjerVcvuy0gf

output:

73

result:

ok 1 number(s): "73"

Test #4:

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

input:

retiredMiFaFa0v0

output:

33

result:

ok 1 number(s): "33"

Test #5:

score: -100
Wrong Answer
time: 505ms
memory: 4824kb

input:

bcdccccacccabdbdaddcabddbaccaaaaaabaccbbbcbbddabcbccabacdacbcbabccbcbddcdcbcaaadddddccdbabaabcbbcaaadadacdaadbdccbddddabcbaaddbcadadcbcbaaccacabdababaabdccadaddacdcacdaabbadadaddbbcccbcddaccaadbbcaaccccdcacbdbdddbaccaacbcaccaaabccdadddbaabdbcaaccacdcdcbcdddacbcacdbbbdccdddccccabdbacddacbaacbbcaccdcd...

output:

69817338

result:

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