abc189, E - Rotate and Flip, アフィン変換, 累積積

前提知識として、二次関数、三角比、三角関数、行列、ベクトルの知識が必要になります。
私はここ１年間で集合、二次関数、三角比、確率、整数問題、図形の性質、三角関数、数列、行列、ベクトルを復習しています。

#アフィン変換
2Dにおける平行移動、回転は以下の行列になります。

##平行移動

```math
\begin{pmatrix}
x' \\
y' \\
1
\end{pmatrix}
=
\begin{pmatrix}
1 & 0 & dx \\
0 & 1 & dy \\
0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
1
\end{pmatrix}
```

##回転

```math
\begin{pmatrix}
x' \\
y' \\
1
\end{pmatrix}
=
\begin{pmatrix}
cosθ & -sinθ & 0 \\
sinθ & cosθ & 0 \\
0 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
x \\
y \\
1
\end{pmatrix}
```

##直線 x=p について対称な位置に移動

```math
(移動前x + 移動後X) / 2 = p \\
移動後X = 2p - 移動前x
```

###[E - Rotate and Flip](https://atcoder.jp/contests/abc189/tasks/abc189_e)

上記の知識を持って実装します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
#define DegreesToRads( degrees ) ((degrees) * (M_PI/ 180.0f))
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
typedef struct {
    ll index[3];
} Matrix3X1;
 
typedef struct {
    ll index[3][3];
} Matrix3X3;
 
Matrix3X3 CreateFixed3X3Matrix(ll v){
    Matrix3X3 temp;
    rep(i, 3){
        rep(j, 3){
            temp.index[i][j] = v;
        }
    }
    return temp;
}
 
Matrix3X1 multiplyMatrixNxM(Matrix3X3 a, Matrix3X1 b){
    Matrix3X1 temp;
    temp.index[0] = 0; temp.index[1] = 0; temp.index[2] = 0;
 
    rep(i, 3){
        rep(j, 3){
            temp.index[i] += (a.index[i][j] * b.index[j]);
        }
    }
    return temp;
}
 
Matrix3X1 translate2DByMultiplication(Matrix3X1 start, ll dx, ll dy){
    Matrix3X3 temp;
    Matrix3X1 result;
 
    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = 1;
    temp.index[1][1] = 1;
    temp.index[2][2] = 1;
 
    temp.index[0][2] = dx;
    temp.index[1][2] = dy;
 
    result = multiplyMatrixNxM(temp, start);
    return result;
}
 
Matrix3X1 Rotate2D(Matrix3X1 start, ll theta){
    Matrix3X3 temp;
    Matrix3X1 result;
 
    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = cos(DegreesToRads(theta));
    temp.index[1][1] = cos(DegreesToRads(theta));
    temp.index[2][2] = 1;
    temp.index[0][1] = -1 * sin(DegreesToRads(theta));
    temp.index[1][0] = sin(DegreesToRads(theta));
 
    result = multiplyMatrixNxM(temp, start);
    return result;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<vector<Matrix3X1>> piece(1, vector<Matrix3X1>(n));
    rep(i, n){
        cin >> piece[0][i].index[0] >> piece[0][i].index[1];
        piece[0][i].index[2] = 1;
    }
 
    int m;
    cin >> m;
    rep(i, m){
        int a, b;
        cin >> a;
 
        vector<Matrix3X1> copy = piece[i];
 
        if(a == 1){
            rep(j, n){
                copy[j] = Rotate2D(copy[j], 270);
            }
        }else if(a == 2){
            rep(j, n){
                copy[j] = Rotate2D(copy[j], 90);
            }
        }else if(a == 3){
            cin >> b;
            rep(j, n){
                copy[j] = translate2DByMultiplication(copy[j], (b - copy[j].index[0]) * 2, 0);
            }
        }else if(a == 4){
            cin >> b;
            rep(j, n){
                copy[j] = translate2DByMultiplication(copy[j], 0, (b - copy[j].index[1]) * 2);
            }
        } 
 
        piece.push_back(copy);
    }
 
    int q;
    cin >> q;
 
    rep(i, q){
        int a, b;
        cin >> a >> b;
        b--;
        cout << piece[a][b].index[0] << " " <<  piece[a][b].index[1] << endl;
    }
 
    return 0;
}
```

TLEになりました。
計算量はO(M^N+q)です。
ここで累積積という考え方が必要になります。
行列の合成（合成変換）を行っていきます。
q_a個目の操作という情報から変換行列を取り出し、q_b個目の最初の座標と計算すると答えが計算できるようになります。
計算量はO(N＋M＋Q)です。

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
#define DegreesToRads( degrees ) ((degrees) * (M_PI/ 180.0f))

using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

typedef struct {
    ll index[3];
} Matrix3X1;

typedef struct {
    ll index[3][3];
} Matrix3X3;

Matrix3X3 CreateFixed3X3Matrix(ll v){
    Matrix3X3 temp;
    rep(i, 3){
        rep(j, 3){
            temp.index[i][j] = v;
        }
    }
    return temp;
}

Matrix3X1 multiplyMatrixNxM(Matrix3X3 a, Matrix3X1 b){
    Matrix3X1 temp;
    temp.index[0] = 0; temp.index[1] = 0; temp.index[2] = 0;

    rep(i, 3){
        rep(j, 3){
            temp.index[i] += (a.index[i][j] * b.index[j]);
        }
    }
    return temp;
}

Matrix3X3 multiply3X3Matrices(Matrix3X3 a, Matrix3X3 b)
{
    Matrix3X3 temp = CreateFixed3X3Matrix(0);

    for(int i = 0;i<3;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                temp.index[i][j] += (a.index[i][k] * b.index[k][j]);
            }
        }
    }
    return temp;
}

Matrix3X3 translate2DByMultiplication(ll dx, ll dy){
    Matrix3X3 temp;

    temp = CreateFixed3X3Matrix(0);
    if(dy==0) temp.index[0][0] = -1;
    else temp.index[0][0] = 1;
    if(dx==0) temp.index[1][1] = -1;
    else temp.index[1][1] = 1;
    temp.index[2][2] = 1;

    temp.index[0][2] = dx;
    temp.index[1][2] = dy;

    return temp;
}

Matrix3X3 Rotate2D(ll theta){
    Matrix3X3 temp;

    temp = CreateFixed3X3Matrix(0);
    temp.index[0][0] = cos(DegreesToRads(theta));
    temp.index[1][1] = cos(DegreesToRads(theta));
    temp.index[2][2] = 1;
    temp.index[0][1] = -1 * sin(DegreesToRads(theta));
    temp.index[1][0] = sin(DegreesToRads(theta));

    return temp;
}

int main() {
    int n;
    cin >> n;

    vector<Matrix3X1> piece(n);
    rep(i, n){
        cin >> piece[i].index[0] >> piece[i].index[1];
        piece[i].index[2] = 1;
    }

    int m;
    cin >> m;
    
    vector<Matrix3X3> mat(1);
    mat[0].index[0][0] = 1;
    mat[0].index[1][1] = 1;
    mat[0].index[2][2] = 1;
    mat[0].index[0][2] = 0;
    mat[0].index[1][2] = 0;

    rep(i, m){
        int op;
        cin >> op;

        if(op == 1){
            Matrix3X3 m = Rotate2D(270);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else if(op == 2){
            Matrix3X3 m = Rotate2D(90);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else if(op == 3){
            int p;
            cin >> p;
            Matrix3X3 m = translate2DByMultiplication(2 * p, 0);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }else{
            int p;
            cin >> p;
            Matrix3X3 m = translate2DByMultiplication(0, 2 * p);
            m = multiply3X3Matrices(m, mat.back());
            mat.push_back(m);
        }
    }
   
    int q;
    cin >> q;

    rep(i, q){
        int a, b;
        cin >> a >> b;
        b--;

        Matrix3X1 m = multiplyMatrixNxM(mat[a], piece[b]);
        cout << m.index[0] << " " <<  m.index[1] << endl;
    }

    return 0;
}
```

##感想
この問題が簡単になってD問題などになったら解けそうです。