oj.uz

Submission #998284

# Submission time Handle Problem Language Result Execution time Memory
998284 2024-06-13T13:44:16 Z doducanh Osmosmjerka (COCI17_osmosmjerka) C++14
160 / 160
 1785 ms 94852 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 28 ms 15420 KB Output is correct
7 Correct 335 ms 44112 KB Output is correct
8 Correct 1785 ms 94852 KB Output is correct