제출 #416684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416684		SirCovidThe19th	Osmosmjerka (COCI17_osmosmjerka)	C++14	80 / 160	4061 ms	262148 KiB

osmosmjerka

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

#define ll long long

const ll p = 1663, mod = 1e9+7;
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};

ll bpow(ll a, ll b){
    if (b == 0) return 1;
    ll res = bpow(a, b/2)%mod; if (b%2 == 1) return (((res*res)%mod)*a)%mod; else return (res*res)%mod;
}

int main() {
    int n, m, k; cin >> n >> m >> k; 
    string grid[n]; ll vals[n][m][(int)floor(log2(k))+1][8]; map<ll, ll> eq;
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int l = 0; (1<<l) <= k; l++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int d = 0; d < 8; d++){
                    if (l == 0){ vals[i][j][l][d] = (grid[i][j]-'a'+1); continue;}
                    int r = (i+(((1<<(l-1)))*di[d])+500*n)%n, c = (j+(((1<<(l-1)))*dj[d])+500*m)%m;
                    vals[i][j][l][d] = (vals[i][j][l-1][d]+vals[r][c][l-1][d]*bpow(p, (1<<(l-1))))%mod;
                }
    deque<int> setBits; for (int i = 0; (1<<i) <= k; i++) if ((k>>i)%2 == 1) setBits.push_front(i);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int d = 0; d < 8; d++){
                ll hash = 0; int cnt = 0;
                for (int b = 0; b < setBits.size(); b++){
                    int r = (i+(cnt*di[d])+500*n)%n, c = (j+(cnt*dj[d])+500*m)%m;
                    hash = (hash+vals[r][c][setBits[b]][d]*bpow(p, cnt))%mod;
                    cnt += (1<<setBits[b]);
                }
                eq[hash]++;
            }
    ll good = 0, tot = (ll)(n*m*8)*(n*m*8);
    for (auto elem : eq) good += elem.second*elem.second; 
    ll div = __gcd(good, tot); cout<<good/div<<"/"<<tot/div;
}

컴파일 시 표준 에러 (stderr) 메시지

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:31:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 for (int b = 0; b < setBits.size(); b++){
      |                                 ~~^~~~~~~~~~~~~~~~

• Subtask 1: 80 / 160