Submission #1222021

#TimeUsernameProblemLanguageResultExecution timeMemory
1222021super0200Osmosmjerka (COCI17_osmosmjerka)C++20
140 / 160
2313 ms39384 KiB
#define _GLIBCXX_FILESYSTEM #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define F first #define S second #define int long long using namespace std; int n,m,k; int b=3137; int mod=(1ll<<61)-1; map<int,int> mp; __int128 p[510*510]; int pows(__int128 x,__int128 y) { __int128 ans=1; while(y) { if(y%2) ans=(ans*x)%mod; y/=2; x=(x*x)%mod; } return ans; } int hash_len(int start,vector<__int128> &h,int len) { if(len==0)return 0; int sz=h.size(); int l1,l2,r1,r2; l1=l2=r1=r2=-1; l1=start; r1 =min(sz-1,start+len-1); if(r1-l1+1 <len) { l2=0; int need=len-(sz-l1); r2=need-1; } int value=0; if(l2==-1) { if(l1==0) value=h[r1]; else value=(h[r1]-(h[l1-1]*p[r1-l1+1])%mod); if(value<0)value+=mod; } else { int value1=h[r1]-((h[l1-1]*p[r1-l1+1])%mod); int value2=h[r2]; if(value1<0)value1+=mod; value=((value1*p[r2+1]%mod)+value2)%mod; } return value; } void roh(string x) { int sz=min((int)x.size(),k); vector<__int128> h(x.size()); h[0]=x[0]; for(int i=1; i<x.size(); i++) h[i]=(h[i-1]*b+x[i])%mod; for(int i=0; i<x.size(); i++) { int value=hash_len(i,h,sz); if(sz!=k) { int rem=k%sz; int q=k/sz; int r=p[sz]; __int128 num=1-(pows(r,q))+mod; num=(value*num)%mod; __int128 den=pows((1-r+mod),mod-2); __int128 ans=(num*den)%mod; int hash_of_reminder=hash_len(i,h,rem); if(hash_of_reminder!=0) value=((ans*p[rem])%mod+hash_of_reminder)%mod; } mp[value]++; } } int vis[502][502]; signed main() { IOS cin>>n>>m>>k; vector<vector<char>> grid(n,vector<char>(m)); for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin>>grid[i][j]; p[0]=1; for(int i=1; i<=n*m+10; i++) p[i]=(p[i-1]*b)%mod; int di[]= {-1,-1,0,1}; int dj[]= {1,-1,1,0}; for(int d=0; d<4; d++) { memset(vis,0,sizeof(vis)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(!vis[i][j]) { vis[i][j]=true; string x; x.push_back(grid[i][j]); int ii,jj; ii=i; jj=j; while(true) { ii=(ii+di[d]+n)%n; jj=(jj+dj[d]+m)%m; if(ii==i && jj==j)break; vis[ii][jj]=true; x.push_back(grid[ii][jj]); } roh(x); reverse(x.begin(),x.end()); roh(x); } } } } int num,den; num=0; den=n*m*8*n*m*8; for(auto [a,b]:mp) { num+= (b*b); } int g=gcd(num,den); cout<<(num/g)<<"/"<<(den/g); }
#Verdict Execution timeMemoryGrader output
Fetching results...