結果
問題 | No.1595 The Final Digit |
ユーザー |
👑 ![]() |
提出日時 | 2021-07-09 21:30:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,745 bytes |
コンパイル時間 | 3,135 ms |
コンパイル使用メモリ | 160,916 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 15:18:11 |
合計ジャッジ時間 | 3,811 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
ソースコード
#include <atcoder/all> #include <iostream> #include <vector> #include <algorithm> #include <set> using namespace atcoder; using namespace std; using ll = long long; using ull = unsigned long long; using mll = static_modint<998244353>; #define rep(i,n) for(int i=0; i<(n); i++) template<class Elem, size_t matrix_sz> struct static_matrix { Elem X[matrix_sz][matrix_sz] = {}; static static_matrix id() { static_matrix res; rep(i, matrix_sz) res[i][i] = 1; return res; } Elem* operator[](int x) { return X[x]; } const Elem* operator[](int x) const { return X[x]; } static_matrix operator+(const static_matrix& r) const { static_matrix res; rep(i, matrix_sz) rep(j, matrix_sz) res[i][j] = X[i][j] + r[i][j]; return res; } static_matrix operator-(const static_matrix& r) const { static_matrix res; rep(i, matrix_sz) rep(j, matrix_sz) res[i][j] = X[i][j] - r[i][j]; return res; } static_matrix operator*(const static_matrix& r) const { static_matrix res; rep(i, matrix_sz) rep(j, matrix_sz) rep(k, matrix_sz) res[i][j] += X[i][k] * r[k][j]; return res; } static_matrix pow(ll N) const { if (N == 0) return id(); static_matrix res = pow(N / 2); res = res * res; if (N % 2 == 1) res = res * *this; return res; } }; using Mat = static_matrix<static_modint<10>,3>; int main(){ ll p,q,r,k; cin >> p >> q >> r >> k; k -= 3; Mat G; G[1][0] = 1; G[2][1] = 1; G[0][2] = 1; G[1][2] = 1; G[2][2] = 1; G = G.pow(k); auto ans = (G[0][2] * p + G[1][2] * q + G[2][2] * r).val(); cout << ans << endl; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_inst;