ドットちゃんたち [yukicoder No.675] - はまやんはまやんはまやん

解法

このサイトを見ると回転行列と平行移動行列がある事がわかる。
行列は行列通しを先に計算しておくことで、複数の行列を一気に適用することが出来る。
最初の答えは(PX, PY)にクエリ1, クエリ2, .. クエリNを適用する。
次の答えは(PX, PY)にクエリ2, .. クエリNを適用する。
次の答えは(PX, PY)にクエリ3, .. クエリNを適用する。
よって答えに適用するクエリの行列は後ろに行くほど少なくなる。
なので、後ろから答えを確定していくことにしよう。
i番目の答えを作るときは、クエリi, クエリi+1, ..., クエリNを適用する必要があるが、i+1番目の答えを作るための行列をm[i+1]とすると、クエリiとm[i+1]を掛け合わせることでm[i]が作れる。
これで後ろから順に答えを確定していって、最後にちゃんとした順番で答える。

int N, PX, PY, A[101010], B[101010];
ll ansx[101010], ansy[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> PX >> PY;
    rep(i, 0, N) {
        cin >> A[i];
        if (A[i] != 3) cin >> B[i];
    }

    Mat m(3, Vec(3, 0));
    rep(i, 0, 3) m[i][i] = 1;

    rrep(i, N - 1, 0) {
        Vec v(3, 0);
        v[0] = PX;
        v[1] = PY;
        v[2] = 1;

        Mat mm(3, Vec(3, 0));
        if (A[i] == 1) {
            mm[0][0] = 1;
            mm[0][2] = B[i];
            mm[1][1] = 1;
            mm[2][2] = 1;
        }
        else if (A[i] == 2) {
            mm[0][0] = 1;
            mm[1][1] = 1;
            mm[1][2] = B[i];
            mm[2][2] = 1;
        }
        else {
            mm[0][0] = 0;
            mm[0][1] = 1;
            mm[1][0] = -1;
            mm[1][1] = 0;
            mm[2][2] = 1;
        }

        m = mulMatMat(m, mm);
        v = mulMatVec(m, v);

        ansx[i] = v[0];
        ansy[i] = v[1];
    }

    rep(i, 0, N) printf("%lld %lld\n", ansx[i], ansy[i]);
}