Submission #2441643
Source Code Expand
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
#define vv(a,b,c,d) vector<vector<a> >(b,vector<a>(c,d))
#define vvv(a,b,c,d,e) vector<vector<vector<a> > >(b,vv(a,c,d,e))
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
template<int MOD>
class ModInt {
public:
ModInt() :value(0) {}
ModInt(long long val) :value((int)(val<0 ? MOD + val%MOD : val%MOD)) { }
ModInt& operator+=(ModInt that) {
value = value + that.value;
if (value >= MOD)value -= MOD;
return *this;
}
ModInt& operator-=(ModInt that) {
value -= that.value;
if (value<0)value += MOD;
return *this;
}
ModInt& operator*=(ModInt that) {
value = (int)((long long)value * that.value % MOD);
return *this;
}
ModInt &operator/=(ModInt that) {
return *this *= that.inverse();
}
ModInt operator+(ModInt that) const {
return ModInt(*this) += that;
}
ModInt operator-(ModInt that) const {
return ModInt(*this) -= that;
}
ModInt operator*(ModInt that) const {
return ModInt(*this) *= that;
}
ModInt operator/(ModInt that) const {
return ModInt(*this) /= that;
}
ModInt pow(long long k) const {
if (value == 0)return 0;
ModInt n = *this, res = 1;
while (k) {
if (k & 1)res *= n;
n *= n;
k >>= 1;
}
return res;
}
ModInt inverse() const {
long long a = value, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
return ModInt(u);
}
int toi() const { return value; }
private:
int value;
};
typedef ModInt<1000000007> mint;
ostream& operator<<(ostream& os, const mint& x) {
os << x.toi();
return os;
}
const int C = 31;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(20);
mint invC = mint(1) / C;
int N;
while (cin >> N) {
vector<string> S(N);
rep(a, N)cin >> S[a];
int re = 0;
deque<mint> hr(N), hc(N), pw(N);
pw[0] = 1;
rep(a, N - 1)pw[a + 1] = pw[a] * C;
rep(a, N) {
fill(all(hc), 0);
fill(all(hr), 0);
rep(r, N) {
int row = (a + r) % N;
rep(c, N) {
hr[r] += pw[c] * S[row][c];
hc[c] += pw[r] * S[row][c];
}
}
rep(b, N) {
bool ok = true;
rep(c, N) {
if (hr[c].toi() != hc[c].toi()) {
ok = false;
break;
}
}
hc.push_back(hc[0]);
hc.pop_front();
rep(r, N) {
int row = (a + r) % N;
hr[r] = (hr[r] - S[row][b]) * invC + pw[N - 1] * S[row][b];
}
if (ok)re++;
}
}
cout << re << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - Find Symmetries |
User |
paruki |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
3738 Byte |
Status |
AC |
Exec Time |
1095 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
869 ms |
384 KB |
subtask_1_04.txt |
AC |
774 ms |
384 KB |
subtask_1_05.txt |
AC |
472 ms |
384 KB |
subtask_1_06.txt |
AC |
290 ms |
384 KB |
subtask_1_07.txt |
AC |
572 ms |
384 KB |
subtask_1_08.txt |
AC |
946 ms |
384 KB |
subtask_1_09.txt |
AC |
828 ms |
384 KB |
subtask_1_10.txt |
AC |
840 ms |
384 KB |
subtask_1_11.txt |
AC |
785 ms |
384 KB |
subtask_1_12.txt |
AC |
776 ms |
384 KB |
subtask_1_13.txt |
AC |
773 ms |
384 KB |
subtask_1_14.txt |
AC |
790 ms |
384 KB |
subtask_1_15.txt |
AC |
1032 ms |
384 KB |
subtask_1_16.txt |
AC |
786 ms |
384 KB |
subtask_1_17.txt |
AC |
779 ms |
384 KB |
subtask_1_18.txt |
AC |
774 ms |
384 KB |
subtask_1_19.txt |
AC |
785 ms |
384 KB |
subtask_1_20.txt |
AC |
1035 ms |
384 KB |
subtask_1_21.txt |
AC |
1045 ms |
384 KB |
subtask_1_22.txt |
AC |
1048 ms |
384 KB |
subtask_1_23.txt |
AC |
1066 ms |
384 KB |
subtask_1_24.txt |
AC |
1093 ms |
384 KB |
subtask_1_25.txt |
AC |
1043 ms |
384 KB |
subtask_1_26.txt |
AC |
1051 ms |
384 KB |
subtask_1_27.txt |
AC |
1094 ms |
384 KB |
subtask_1_28.txt |
AC |
1095 ms |
384 KB |
subtask_1_29.txt |
AC |
1064 ms |
384 KB |
subtask_1_30.txt |
AC |
1063 ms |
384 KB |