256122026-02-22 20:07:54999Forgó rulettkerékcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask220/20
3Elfogadva1ms316 KiB
4Elfogadva1ms404 KiB
5Elfogadva1ms340 KiB
6Elfogadva1ms316 KiB
7Elfogadva2ms316 KiB
8Elfogadva1ms316 KiB
9Elfogadva1ms316 KiB
subtask315/15
10Elfogadva12ms736 KiB
11Elfogadva14ms652 KiB
12Elfogadva13ms764 KiB
13Elfogadva10ms716 KiB
14Elfogadva13ms780 KiB
15Elfogadva14ms988 KiB
16Elfogadva13ms564 KiB
17Elfogadva14ms564 KiB
subtask40/65
18Elfogadva34ms1316 KiB
19Elfogadva32ms1184 KiB
20Elfogadva37ms1636 KiB
21Elfogadva35ms1320 KiB
22Elfogadva35ms1172 KiB
23Elfogadva32ms1256 KiB
24Hibás válasz34ms1328 KiB
25Elfogadva35ms2020 KiB
26Elfogadva79ms3472 KiB
27Elfogadva43ms1748 KiB
28Elfogadva48ms8248 KiB
29Elfogadva75ms3524 KiB
30Elfogadva82ms3476 KiB