#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 1000000007
#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, int> 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 >= 1; --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 <= n+n && j+k <= m+m)
ha[i][j] = add(ha[i][j], -mul(mat[whd][j+k] - 'a' + 1, pwmd[k]));
if(whd <= n + n + 1 && j + k - 1 > m && j + k - 1 <= m + m){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// cout << xx << '\n';
for(int i = n + n; i + k - 1 > n; --i)
for(int j = 1; j <= m + 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(whd <= n+n && j - k >= 1)
ha[i][j] = add(ha[i][j], -mul(mat[whd][j-k] - 'a' + 1, pwmd[k]));
if(whd <= n + n + 1 && j - k + 1 >= 1 && j - k + 1 <= m){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// cout << xx << '\n';
for(int i = 1; i - k + 1 <= n; ++i)
for(int j = m + m; j >= 1; --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 <= m+m)
ha[i][j] = add(ha[i][j], -mul(mat[whd][j+k] - 'a' + 1, pwmd[k]));
if(i - k + 1 >= 1 && j + k - 1 > m && j + k - 1 <= m + m){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// cout << xx << '\n';
for(int i = 1; i - k + 1 <= n; ++i)
for(int j = 1; j <= m + 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(whd >= 1 && j - k >= 1)
ha[i][j] = add(ha[i][j], -mul(mat[whd][j-k] - 'a' + 1, pwmd[k]));
if(i - k + 1 >= 1 && j - k + 1 >= 1 && j - k + 1 <= m){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// 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 + 1 >= 1){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// 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] << " ";
}
}
//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 + 1 >= 1){
lh[ha[i][j]]++, ++xx;
// cout << ha[i][j] << " ";
}
}
// 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] << " ";
}
}
// cout << xx << '\n';
ll num = 0;
ll den = 1LL * n * m * 8;
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;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
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]
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
1016 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 8 |
Incorrect |
1112 ms |
47280 KB |
Output isn't correct |
