結果

問題 No.2443 特殊線形群の標準表現
コンテスト
ユーザー MasKoaTS
提出日時 2023-08-12 15:49:15
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 13,980 KB
最終ジャッジ日時 2024-11-25 13:31:42
合計ジャッジ時間 27,933 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

//愚直解

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <stdio.h>
#define MAX_DATA 100000
#define ll long long

int main(void) {
    int n, b, q;
    scanf("%d", &n);    scanf("%d", &b);    scanf("%d", &q);

    ll A[MAX_DATA][2][2];
    for(int i = 0; i < n; ++i){
        scanf("%lld", &A[i][0][0]);    scanf("%lld", &A[i][0][1]);
        scanf("%lld", &A[i][1][0]);    scanf("%lld", &A[i][1][1]);
    }

    int l[MAX_DATA];    int r[MAX_DATA];
    ll x[MAX_DATA];     ll y[MAX_DATA];
    for(int i = 0; i < q; ++i){
        scanf("%d", &l[i]);
        scanf("%d", &r[i]);
        scanf("%lld", &x[i]);
        scanf("%lld", &y[i]);
    }

    for(int i = 0; i < q; ++i){
        ll P[2][2] = {{1, 0}, {0, 1}};
        for(int j = l[i]; j < r[i]; ++j){
            ll Q[2][2] = {{P[0][0], P[0][1]}, {P[1][0], P[1][1]}};
            P[0][0] = P[0][1] = P[1][0] = P[1][1] = 0;
            for(int ii = 0; ii < 2; ++ii){
                for(int jj = 0; jj < 2; ++jj){
                    for(int kk = 0; kk < 2; ++kk){
                        P[ii][jj] += A[j][ii][kk] * Q[kk][jj];
                        P[ii][jj] %= b;
                    }
                }
            }
        }
        ll vec[2] = { P[0][0] * x[i] + P[0][1] * y[i], P[1][0] * x[i] + P[1][1] * y[i] };
        vec[0] %= b;  vec[1] %= b;
        if(vec[0] < 0){
            vec[0] += b;
        }
        if(vec[1] < 0){
            vec[1] += b;
        }
        printf("%lld %lld\n", vec[0], vec[1]);
    }

	return 0;
}
0