QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #283362 | #7518. GCD of Pattern Matching | light_ink_dots# | WA | 0ms | 3876kb | C++20 | 893b | 2023-12-14 15:32:32 | 2023-12-14 15:32:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int T,n,m,tot;
int mp[40];
string s;
__int128 ans;
__int128 mul[40],sum[40];
__int128 biggcd(__int128 a,__int128 b){
return b==0? a:biggcd(b,a%b);
}
void print(__int128 x){
if(x>9)
print(x/10);
putchar(x%10+48);
}
int main(){
ios::sync_with_stdio(false),cin>>T;
while(T--){
memset(mp,0,sizeof(mp)),memset(sum,0,sizeof(sum));
ans=tot=0;
cin>>m>>s,n=s.size();
mul[0]=1;
for(int i=1;i<=n;i++)
mul[i]=mul[i-1]*m;
for(int i=0;i<n;i++){
if(mp[s[i]-96]==0)
mp[s[i]-96]=++tot,sum[tot]=0;
sum[mp[s[i]-96]]+=mul[n-i-1];
}
if(tot==1)
ans=sum[1];
else for(int i=0;i<n;i++)
ans=ans*m+(tot-mp[s[i]-96]);
if(n>2){
sort(sum+1,sum+1+tot);
for(int i=1;i<tot;i++)
ans=biggcd(ans,sum[i+1]-sum[i]);
}
print(ans),putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
5 10 ccpcccpc 10 cpcpcp 10 cpc 4 cpccpc 4 dhcp
output:
10001 10101 1 65 3
result:
ok 5 number(s): "10001 10101 1 65 3"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3876kb
input:
30 2 ab 3 abc 4 abcd 5 abcde 6 abcdef 7 abcdefg 8 abcdefgh 9 abcdefghi 10 abcdefghij 11 abcdefghijk 12 abcdefghijkl 13 abcdefghijklm 14 abcdefghijklmn 15 abcdefghijklmno 16 abcdefghijklmnop 16 a 16 ab 16 abc 16 abcd 16 abcde 16 abcdef 16 abcdefg 16 abcdefgh 16 abcdefghi 16 abcdefghij 16 abcdefghijk ...
output:
2 1 3 2 5 3 7 4 9 5 11 6 13 7 15 1 16 3 3 5 15 3 1 3 15 5 3 3 1 15
result:
wrong answer 17th numbers differ - expected: '1', found: '16'