結果

問題 No.3226 2×2行列累乗
コンテスト
ユーザー jiangxinyang
提出日時 2025-08-08 23:07:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,245 bytes
コンパイル時間 1,627 ms
コンパイル使用メモリ 195,624 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-08 23:07:49
合計ジャッジ時間 2,856 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
struct Mat {
    ll a, b, c, d;
};
ll cal(ll x, ll k) {
    return (x % k + k) % k;
}
Mat mul(Mat A, Mat B, ll K) {
    Mat C;
    C.a = (ll)(((__int128)A.a * B.a + (__int128)A.b * B.c) % K);
    C.b = (ll)(((__int128)A.a * B.b + (__int128)A.b * B.d) % K);
    C.c = (ll)(((__int128)A.c * B.a + (__int128)A.d * B.c) % K);
    C.d = (ll)(((__int128)A.c * B.b + (__int128)A.d * B.d) % K);
    return C;
}
Mat powmod(Mat x, unsigned long long y, ll K) {
    Mat res = {1 % K, 0, 0, 1 % K};
    while (y) {
        if (y & 1) res = mul(res, x, K);
        x = mul(x, x, K);
        y >>= 1;
    }
    return res;
}
int main() {
    ll A, B, C, D;
    ll S, T;
    unsigned long long n;
    ll K;
    cin >> A >> B >> C >> D;
    cin >> S >> T;
    cin >> n >> K;
    A = cal(A, K);
    B = cal(B, K);
    C = cal(C, K);
    D = cal(D, K);
    S = cal(S, K);
    T = cal(T, K);

    Mat M = {A, B, C, D};
    Mat r = powmod({A, B, C, D}, n, K);
    cout << cal((ll)(((__int128)r.a * S + (__int128)r.b * T) % K), K) << " " << cal((ll)(((__int128)r.c * S + (__int128)r.d * T) % K), K) << "\n";
    return 0;
}
0