結果
問題 | No.1569 Nixoracci's Number |
ユーザー |
![]() |
提出日時 | 2021-06-28 15:34:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 447 ms / 2,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 912 ms |
コンパイル使用メモリ | 94,708 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 13:26:49 |
合計ジャッジ時間 | 4,374 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
/* -*- coding: utf-8 -*- * * 1569.cc: No.1569 Nixoracci's Number - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200; /* typedef */ typedef long long ll; typedef int mat[MAX_N][MAX_N]; /* global variables */ ll as[MAX_N]; mat ma, mb; /* subroutines */ inline void initmat(const int n, mat a) { memset(a, 0, sizeof(mat)); } inline void unitmat(const int n, mat a) { initmat(n, a); for (int i = 0; i < n; i++) a[i][i] = 1; } inline void copymat(const int n, const mat a, mat b) { memcpy(b, a, sizeof(mat)); } inline void mulmat(const int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] ^= a[i][k] * b[k][j]; } } inline void powmat(const int n, const mat a, ll b, mat c) { mat s, t; copymat(n, a, s); unitmat(n, c); while (b > 0) { if (b & 1) { mulmat(n, c, s, t); copymat(n, t, c); } mulmat(n, s, s, t); copymat(n, t, s); b >>= 1; } } /* main */ int main() { int n; ll k; scanf("%d%lld", &n, &k); for (int i = 0; i < n; i++) scanf("%lld", as + i); initmat(n, ma); for (int i = 0; i + 1 < n; i++) ma[i][i + 1] = 1; for (int j = 0; j < n; j++) ma[n - 1][j] = 1; powmat(n, ma, k - 1, mb); ll sum = 0; for (int i = 0; i < n; i++) sum ^= mb[0][i] * as[i]; printf("%lld\n", sum); return 0; }