256122026-02-22 20:07:54999Forgó rulettkerékcpp17Wrong answer 35/10082ms8248 KiB
// Source: https://usaco.guide/general/io

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

signed main() {
    int n,m;cin>>n>>m;
    int p = 31,M=1e9+7;
    vector<int> hpow(m*2+1);
    hpow[0]=1;
    for(int i = 1;i<=m*2;i++){
        hpow[i]=(hpow[i-1]*p)%M;
    }
    vector<int> chash;
    for(int i = 0;i<n;i++){
        string s;cin>>s;
        s+=s;
        vector<int> v(2*m+1);
        for(int j = 0;j<2*m;j++){
            v[j+1]=(v[j]+(s[j]-'a'+1)*hpow[j])%M;
        }
        int ch=M;
        for(int j = 0;j<m;j++){
            int hash=((v[j+m]-v[j]+M)*hpow[2*m-j])%M;
            ch=min(ch,hash);
        }
        chash.push_back(ch);
    }
    sort(chash.begin(),chash.end());
    int cnt=1,ans=0;
    for(int i = 1;i<chash.size();i++){
        if(chash[i]==chash[i-1]){
            cnt++;
        }
        else{
            ans+=(cnt*(cnt-1))/2;
            cnt=1;
        }
    }
    ans+=(cnt*(cnt-1))/2;
    cout<<ans<<endl;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask220/20
3Accepted1ms316 KiB
4Accepted1ms404 KiB
5Accepted1ms340 KiB
6Accepted1ms316 KiB
7Accepted2ms316 KiB
8Accepted1ms316 KiB
9Accepted1ms316 KiB
subtask315/15
10Accepted12ms736 KiB
11Accepted14ms652 KiB
12Accepted13ms764 KiB
13Accepted10ms716 KiB
14Accepted13ms780 KiB
15Accepted14ms988 KiB
16Accepted13ms564 KiB
17Accepted14ms564 KiB
subtask40/65
18Accepted34ms1316 KiB
19Accepted32ms1184 KiB
20Accepted37ms1636 KiB
21Accepted35ms1320 KiB
22Accepted35ms1172 KiB
23Accepted32ms1256 KiB
24Wrong answer34ms1328 KiB
25Accepted35ms2020 KiB
26Accepted79ms3472 KiB
27Accepted43ms1748 KiB
28Accepted48ms8248 KiB
29Accepted75ms3524 KiB
30Accepted82ms3476 KiB