補助的な盤面
回転や反転を愚直に実装すると， \(O(N^2)\) かかるので， クエリごとに計算しては間に合わない． そこで，回転や反転をどの程度行ったを記録しておいて， 盤面自体は回転させずに保持する．
つまり，
(実際の盤面) \(\leftrightarrow\) (補助的な盤面, (f,r))
と一対一対応させて，基本は右で計算する． クエリが全て終わったら左に戻す． ここで， \(f \in \mathbb{Z}/2\mathbb{Z}, r \in \mathbb{Z}/4\mathbb{Z}\) は，上下反転と反時計回りの回転の回数を表す． 左右反転もこれらで表せる．
二面体群
上下反転，反時計回りの回転，左右反転は，二面体群 \(G\) で表せる． 上下反転を \(t\) ， 反時計回りの回転を \(s\) とおけば， \(G\) の元は \(t^{f} s^{r}\) と書ける． ここで， \begin{align} t ^ 2 &= id, \\ s ^ 4 &= id,\\ t s t^{-1} &= s^{-1} \end{align} を満たす． ただしこの関係式は， 写像を左から掛ける という前提のもの．
実装
更新クエリ1のときに注意． 与えられるのは， 実際の盤面の座標 であるから，これを 補助的なの盤面の座標 に変換する．
(補助的な盤面) ---- \(t^{f} s^{r}\) -> 実際の盤面 であるから， \(t^{f} s^{r}\)の逆元 を掛けることになる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
template<typename T>
const long long N = mat.size(), M = mat[0].size(); // mat : NxM-matrix
if( rot == 1 ){ // left 90度 rotation
for(int i=0; i<M; i++)
for(int j=0; j<N; j++)
tmp[i][j] = mat[j][M-1-i];
return tmp;
}else if( rot == -1 ){ // right 90度 rotation
for(int i=0; i<M; i++)
for(int j=0; j<N; j++)
tmp[i][j] = mat[N-1-j][i];
return tmp;
}else{
}
}
int main() {
// 正しい盤面と，仮想的な盤面
// 今，どっちで考えているのかを区別するのが大事．
// vector に保存しているのは，仮想的な盤面．
ll n, q;
cin >> n >> q;
// Remark : 写像は左から，という前提での relation
ll f = 0;
ll r = 0;
// flip
f ^= 1;
};
// rotate
if(f == 1){
r += 3;
}else{
r++;
}
r %= 4;
};
vvll a(n, vll(n)); // 仮想的な盤面
rep(qi,q){
ll t; cin >> t ;
if(t == 1){
ll x,y ; cin >> x >> y; // 正しい盤面 の座標
--x, --y;
// Remark:
// x,yを仮想的な盤面の座標に変換
rep(i,f) x = n-1-x;
rep(i,(4-r)%4) {
ll tmp = x;
x = n-1-y;
y = tmp;
}
a[x][y] ^= 1;
}else if(t == 2){
char c; cin >> c;
if(c == 'A'){
}else{
}
}else{
char c; cin >> c;
else{
}
}
}
// Remark : 写像は左から
rep(i,r){
a = RotationMat(a);
}
if(f){
rep(i,n/2){
swap(a[i], a[n-1-i]);
}
}
rep(i,n){
rep(j,n){
cout << a[i][j];
}
cout << endl;
}
return 0;
}
