Submission #998284

#	Time	Username	Problem	Language	Result	Execution time	Memory
998284		doducanh	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	1785 ms	94852 KiB

osmosmjerka

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int mod=(1ll<<(61)-1);
int sub[505][505][31];
string s[505];
int n,m,k;
map<int,int>c;
int nn,mm;
void xuly(int dx,int dy)
{
    int base=31;
    for(int lo=1;lo<=30;lo++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int ni=(i+dx*(1ll<<(lo-1))+nn)%n;
                int nj=(j+dy*(1ll<<(lo-1))+mm)%m;
                if(ni==0)ni=n;if(nj==0)nj=m;
                sub[i][j][lo]=(sub[i][j][lo-1]*base%mod+sub[ni][nj][lo-1])%mod;
            }
        }
        base=(base*base)%mod;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x=i,y=j;
            int base=31;
            int res=0;
            for(int lo=30;lo>=0;lo--){
                if((k>>lo)&1){
                    res=(res*base%mod+sub[x][y][lo])%mod;
                    x=(x+1ll*dx*(1ll<<lo)+nn)%n;
                    if(x==0)x=n;
                    y=(y+1ll*dy*(1ll<<lo)+mm)%m;
                    if(y==0)y=m;

                }
                base=(base*base)%mod;
            }
            c[res]++;
        }
    }

}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    nn=n*1000000000;
    mm=m*1000000000;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
        for(int j=1;j<=m;j++){
            sub[i][j][0]=s[i][j]-'a'+1;
        }
    }
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            if(i==0&&j==0)continue;
            xuly(i,j);
        }
    }
    int t1=0;
    int t2=1ll*8*8*n*m*n*m;
    for(auto [v,w]:c){
        t1=t1+1ll*w*w;
    }
    int g=__gcd(t1,t2);
    cout<<(t1/g)<<"/"<<(t2/g);
    return 0;
}

Compilation message (stderr)

osmosmjerka.cpp:5:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    5 | const int mod=(1ll<<(61)-1);
      |                     ~~~~^~
osmosmjerka.cpp: In function 'void xuly(long long int, long long int)':
osmosmjerka.cpp:19:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |                 if(ni==0)ni=n;if(nj==0)nj=m;
      |                 ^~
osmosmjerka.cpp:19:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |                 if(ni==0)ni=n;if(nj==0)nj=m;
      |                               ^~
osmosmjerka.cpp: At global scope:
osmosmjerka.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main()
      | ^~~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [v,w]:c){
      |              ^

• Subtask 1: 160 / 160