QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573222 | #5051. Namomo Subsequence | confirm14478 | WA | 131ms | 58968kb | C++14 | 3.4kb | 2024-09-18 17:48:17 | 2024-09-18 17:48:18 |
Judging History
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";
*/
Details
Tip: Click on the bar to expand more detailed information
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'