제출 #183962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
183962		stefdasca	Osmosmjerka (COCI17_osmosmjerka)	C++14	100 / 160	1387 ms	66628 KiB

osmosmjerka

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000009
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
ll cmmdc(ll a, ll b)
{
    while(b)
    {
        ll c = a%b;
        a = b;
        b = c;
    }
    return a;
}

int n, m, k;

char mat[2002][2002];

ll pwmd[2002], ha[2002][2002];

map<ll, ll> lh;
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i)
        cin >> (mat[i] + 1);
    pwmd[0] = 1;
    for(int i = 1; i <= 2000; ++i)
        pwmd[i] = mul(31, pwmd[i-1]);
    if(n == m)
    {
        k = min(k, n);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                mat[n + i][j] = mat[i][j], mat[i][m + j] = mat[i][j], mat[n + i][m + j] = mat[i][j];

       // for(int i = 1; i <= n+n; cout << '\n', ++i)
        //    for(int j = 1; j <= n+n; ++j)
          //      cout << mat[i][j];

        // diagonals
        int xx = 0;
        for(int i = n + n; i + k - 1 > n; --i)
            for(int j = m + m; j + k - 1 > m; --j)
            {
                ha[i][j] = mul(ha[i+1][j+1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(i+k <= n+n && j+k <= m+m)
                    ha[i][j] = add(ha[i][j], -mul(mat[i+k][j+k] - 'a' + 1, pwmd[k]));
                if(i + k - 1 <= n + n && j + k - 1 <= m + m){
                    lh[ha[i][j]]++, ++xx;
               //     cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
      //  cout << xx << '\n';
        for(int i = n + n; i + k - 1 > n; --i)
            for(int j = 1; j - k + 1 <= m; ++j)
            {
                ha[i][j] = mul(ha[i+1][j-1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(i + k <= n+n && j - k >= 1)
                    ha[i][j] = add(ha[i][j], -mul(mat[i+k][j-k] - 'a' + 1, pwmd[k]));
                if(i + k - 1 <= n + n && j >= k)
                {
                    lh[ha[i][j]]++, ++xx;
             //       cout << ha[i][j] << " ";
                }
            }


        memset(ha, 0, sizeof(ha));
      //  cout << xx << '\n';
        for(int i = 1; i - k + 1 <= n; ++i)
            for(int j = m + m; j + k - 1 > m; --j)
            {
                ha[i][j] = mul(ha[i-1][j+1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(i-k >= 1 && j+k <= m+m)
                    ha[i][j] = add(ha[i][j], -mul(mat[i-k][j+k] - 'a' + 1, pwmd[k]));
                if(i >= k && j + k - 1 <= m + m){
                    lh[ha[i][j]]++, ++xx;
                //    cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
     //   cout << xx << '\n';
        for(int i = 1; i - k + 1 <= n; ++i)
            for(int j = 1; j - k + 1 <= m; ++j)
            {
                ha[i][j] = mul(ha[i-1][j-1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                int whd = i - k;
                if(i-k >= 1 && j - k >= 1)
                    ha[i][j] = add(ha[i][j], -mul(mat[i-k][j-k] - 'a' + 1, pwmd[k]));
                if(i >= k && j >= k)
                {
                    lh[ha[i][j]]++, ++xx;
            //        cout << ha[i][j] << " ";
                }
            }

        memset(ha, 0, sizeof(ha));
       // cout << xx << '\n';
        // lines

        for(int i = 1; i <= n; ++i)
            for(int j = 1; j - k + 1 <= m; ++j)
            {
                ha[i][j] = mul(ha[i][j-1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(j - k >= 1)
                    ha[i][j] = add(ha[i][j], -mul(mat[i][j-k] - 'a' + 1, pwmd[k]));
                if(j >= k)
                {
                    lh[ha[i][j]]++, ++xx;
               //     cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
     //   cout << xx << '\n';

        for(int i = 1; i <= n; ++i)
            for(int j = m + m; j + k - 1 > m; --j)
            {
                ha[i][j] = mul(ha[i][j+1], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(j + k <= m + m)
                    ha[i][j] = add(ha[i][j], -mul(mat[i][j+k] - 'a' + 1, pwmd[k]));
                if(j + k - 1 <= m + m){
                    lh[ha[i][j]]++, ++xx;
               //     cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
       // cout << xx << '\n';

        // columns

        for(int i = 1; i - k + 1 <= n; ++i)
            for(int j = 1; j <= m; ++j)
            {
                ha[i][j] = mul(ha[i-1][j], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(i - k >= 1)
                    ha[i][j] = add(ha[i][j], -mul(mat[i-k][j] - 'a' + 1, pwmd[k]));
                if(i >= k)
                {
                    lh[ha[i][j]]++, ++xx;
                 //   cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
      //  cout << xx << '\n';
        for(int i = n + n; i + k - 1 > n; --i)
            for(int j = 1; j <= m; ++j)
            {
                ha[i][j] = mul(ha[i+1][j], 31);
                ha[i][j] = add(ha[i][j], mat[i][j] - 'a' + 1);
                if(i + k <= n + n)
                    ha[i][j] = add(ha[i][j], -mul(mat[i+k][j] - 'a' + 1, pwmd[k]));
                if(i + k - 1 <= n + n){
                    lh[ha[i][j]]++, ++xx;
                 //   cout << ha[i][j] << " ";
                }
            }
        memset(ha, 0, sizeof(ha));
       // cout << xx << '\n';
        ll num = 0;
        ll den = 1LL * n * m * 8;
        assert(xx == den);
        den *= den;
        for(auto it : lh){
            num += 1LL * it.second * it.second;
        //    cout << it.fi << " " << it.se << '\n';
        }
        ll dc = cmmdc(num, den);
        cout << num/dc << "/" << den/dc << '\n';
    }
    return 0;
}

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

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:143:21: warning: unused variable 'whd' [-Wunused-variable]
                 int whd = i - k;
                     ^~~
osmosmjerka.cpp:63:5: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
 int main()
     ^~~~
osmosmjerka.cpp:63:5: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]

• Subtask 1: 100 / 160