Submission #527964

#	Time	Username	Problem	Language	Result	Execution time	Memory
527964		penguinhacker	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	1022 ms	36256 KiB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int M=1e9+9;
const unsigned ll SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
uniform_int_distribution<int> BDIST(0.1*M, 0.9*M);
ar<int, 2> B={BDIST(rng), BDIST(rng)};

ar<int, 2> operator+(ar<int, 2> a, ar<int, 2> b) {
	ar<int, 2> c;
	for (int i : {0, 1})
		if ((c[i]=a[i]+b[i])>=M)
			c[i]-=M;
	return c;
}

ar<int, 2> operator-(ar<int, 2> a, ar<int, 2> b) {
	ar<int, 2> c;
	for (int i : {0, 1})
		if ((c[i]=a[i]-b[i])<0)
			c[i]+=M;
	return c;
}

ar<int, 2> operator*(ar<int, 2> a, ar<int, 2> b) {
	return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
}

ar<int, 2> mk(char c) {
	return {c, c};
}

ostream& operator<<(ostream& out, ar<int, 2> a) {
	return out << "[" << a[0] << ", " << a[1] << "]";
}

const int mxN=500;
int n, m, k;
string g[mxN], ng[mxN];
bool vis[mxN][mxN];
ar<int, 2> hsh[mxN*mxN+1], p[mxN*mxN+1];
map<ar<int, 2>, int> mp;

void rot() {
	for (int i=0; i<m; ++i)
		ng[i].resize(n);
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j)
			ng[j][n-i-1]=g[i][j];
	swap(n, m);
	for (int i=0; i<n; ++i)
		g[i]=ng[i];
}

void solve(string s) {
	for (int i=0; i<s.size(); ++i)
		hsh[i+1]=hsh[i]*B+mk(s[i]);
	int need=(k-s.size()+1)/s.size();
	int rem=k-need*s.size();
	assert(rem>=s.size()-1);
	ar<int, 2> hp=hsh[s.size()], bp=p[s.size()];
	ar<int, 2> hr={}, br={1, 1};
	while(need) {
		if (need&1) {
			hr=hr*bp+hp;
			br=br*bp;
		}
		hp=hp*bp+hp;
		bp=bp*bp;
		need/=2;
	}
	//cout << s << endl;
	for (int i=0; i<s.size(); ++i) {
		ar<int, 2> cur;
		int lft;
		if (!i)
			cur=hr, lft=rem;
		else {
			cur=(hsh[s.size()]-hsh[i]*p[s.size()-i])*br+hr;
			lft=rem-(s.size()-i);
		}
		//cout << cur << endl;
		int pos=0;
		while(lft) {
			if (s.size()-pos>=lft) {
				cur=cur*p[lft]+(hsh[pos+lft]-hsh[pos]*p[lft]);
				break;
			} else {
				cur=cur*p[s.size()-pos]+(hsh[s.size()]-hsh[pos]*p[s.size()-pos]);
				lft-=s.size()-pos;
			}
		}
		++mp[cur];
		//cout << cur << endl;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i=0; i<n; ++i)
		cin >> g[i];
	p[0]={1, 1};
	for (int i=1; i<=n*m; ++i)
		p[i]=p[i-1]*B;
	for (int r=0; r<4; ++r) {
		for (int i=0; i<n; ++i)
			solve(g[i]);
		memset(vis, 0, sizeof(vis));
		for (int i=0; i<n; ++i)
			for (int j=0; j<m; ++j)
				if (!vis[i][j]) {
					string s;
					int a=i, b=j;
					while(!vis[a][b]) {
						vis[a][b]=1;
						s+=g[a][b];
						a=(a+1)%n;
						b=(b+1)%m;
					}
					solve(s);
				}
		rot();
	}
	ll ans=0;
	for (auto x : mp)
		ans+=(ll)x.second*x.second;
	ll b=(8ll*n*m)*(8*n*m);
	ll g=__gcd(ans, b);
	cout << ans/g << "/" << b/g;
	return 0;
}

Compilation message (stderr)

osmosmjerka.cpp: In function 'std::array<int, 2> operator*(std::array<int, 2>, std::array<int, 2>)':
osmosmjerka.cpp:30:23: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](0)) * ((long long int)b.std::array<int, 2>::operator[](0))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
   30 |  return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
      |          ~~~~~~~~~~~~~^~
osmosmjerka.cpp:30:40: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](1)) * ((long long int)b.std::array<int, 2>::operator[](1))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
   30 |  return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
      |                           ~~~~~~~~~~~~~^~
osmosmjerka.cpp: In function 'void solve(std::string)':
osmosmjerka.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i=0; i<s.size(); ++i)
      |                ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from osmosmjerka.cpp:1:
osmosmjerka.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  assert(rem>=s.size()-1);
      |         ~~~^~~~~~~~~~~~
osmosmjerka.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i=0; i<s.size(); ++i) {
      |                ~^~~~~~~~~
osmosmjerka.cpp:89:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |    if (s.size()-pos>=lft) {
      |        ~~~~~~~~~~~~^~~~~

• Subtask 1: 160 / 160