256132026-02-22 20:14:48999Forgó rulettkerékcpp17Accepted 100/100157ms7504 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=1e15+37;
    vector<int> hpow(m*2+1);
    hpow[0]=1;
    for(int i = 1;i<=m*2;i++){
        hpow[i]=((__int128)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]=((__int128)v[j]+(__int128)(s[j]-'a'+1)*hpow[j])%M;
        }
        int ch=M;
        for(int j = 0;j<m;j++){
            int hash=((__int128)(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
2Accepted1ms500 KiB
subtask220/20
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted2ms508 KiB
7Accepted2ms404 KiB
8Accepted2ms560 KiB
9Accepted2ms316 KiB
subtask315/15
10Accepted32ms432 KiB
11Accepted37ms316 KiB
12Accepted35ms420 KiB
13Accepted30ms428 KiB
14Accepted35ms500 KiB
15Accepted37ms512 KiB
16Accepted37ms316 KiB
17Accepted37ms432 KiB
subtask465/65
18Accepted96ms432 KiB
19Accepted92ms316 KiB
20Accepted98ms744 KiB
21Accepted103ms316 KiB
22Accepted101ms316 KiB
23Accepted92ms500 KiB
24Accepted94ms316 KiB
25Accepted104ms1080 KiB
26Accepted153ms2420 KiB
27Accepted112ms672 KiB
28Accepted120ms7504 KiB
29Accepted151ms2352 KiB
30Accepted157ms2468 KiB