結果
問題 | No.2441 行列累乗 |
ユーザー |
![]() |
提出日時 | 2023-08-25 21:37:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,375 bytes |
コンパイル時間 | 2,957 ms |
コンパイル使用メモリ | 196,456 KB |
最終ジャッジ日時 | 2025-02-16 13:49:13 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <iostream> // cout, endl, cin #include <string> // string, to_string, stoi #include <vector> // vector #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound #include <utility> // pair, make_pair #include <tuple> // tuple, make_tuple #include <cstdint> // int64_t, int*_t #include <cstdio> // printf #include <map> // map #include <queue> // queue, priority_queue #include <set> // set #include <stack> // stack #include <deque> // deque #include <unordered_map> // unordered_map #include <unordered_set> // unordered_set #include <bitset> // bitset #include <cctype> // isupper, islower, isdigit, toupper, tolower #include <iomanip>//fixed,setprecision //#include <limits.n>//INT_MAX //#include <math.n>//M_PI #include <random> #include <regex> // 正規表現 #include <time.h> #include <fstream> //#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; //using mint = modint1000000007; // using mint = modint998244353; // using mint=modint; #define ll long long #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) //文字列が含まれるかどうか bool aru(){ string s; cin>>s; vector<string>t={"ACE","BDF","CEG","DFA","EGB","FAC","GBD"}; return find(t.begin(),t.end(),s)!=t.end(); } struct Matrix { long long p[2][2] = { {0, 0}, {0, 0} }; }; Matrix Multiplication(Matrix A, Matrix B) { Matrix C; for (int i = 0; i < 2; i++) { for (int k = 0; k < 2; k++) { for (int j = 0; j < 2; j++) { C.p[i][j] += A.p[i][k] * B.p[k][j]; //C.p[i][j] %= 1000000000; } } } return C; } Matrix Power(Matrix A, long long n) { Matrix P = A, Q; bool flag = false; for (int i = 0; i < 60; i++) { if ((n & (1LL << i)) != 0LL) { if (flag == false) { Q = P; flag = true; } else { Q = Multiplication(Q, P); } } P = Multiplication(P, P); } return Q; } int main() { // 入力 ~ 累乗の計算(N>=3 でなければ正しく動作しないので注意) long long N=3; //cin >> N; Matrix A; cin>>A.p[0][0]; cin>>A.p[0][1]; cin>>A.p[1][0]; cin>>A.p[1][1]; Matrix B = Multiplication( A, A); Matrix C=Multiplication( B, A); // 出力(下から 9 桁目が 0 の場合、最初に 0 を含まない形で出力していることに注意) cout<<C.p[0][0] <<" "<< C.p[0][1]<<endl; cout << C.p[1][0] <<" "<< C.p[1][1]<<endl; return 0; }