256132026-02-22 20:14:48999Forgó rulettkerékcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms500 KiB
subtask220/20
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva2ms508 KiB
7Elfogadva2ms404 KiB
8Elfogadva2ms560 KiB
9Elfogadva2ms316 KiB
subtask315/15
10Elfogadva32ms432 KiB
11Elfogadva37ms316 KiB
12Elfogadva35ms420 KiB
13Elfogadva30ms428 KiB
14Elfogadva35ms500 KiB
15Elfogadva37ms512 KiB
16Elfogadva37ms316 KiB
17Elfogadva37ms432 KiB
subtask465/65
18Elfogadva96ms432 KiB
19Elfogadva92ms316 KiB
20Elfogadva98ms744 KiB
21Elfogadva103ms316 KiB
22Elfogadva101ms316 KiB
23Elfogadva92ms500 KiB
24Elfogadva94ms316 KiB
25Elfogadva104ms1080 KiB
26Elfogadva153ms2420 KiB
27Elfogadva112ms672 KiB
28Elfogadva120ms7504 KiB
29Elfogadva151ms2352 KiB
30Elfogadva157ms2468 KiB