結果
問題 |
No.1569 Nixoracci's Number
|
ユーザー |
|
提出日時 | 2025-08-26 11:10:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,757 bytes |
コンパイル時間 | 3,517 ms |
コンパイル使用メモリ | 286,444 KB |
実行使用メモリ | 15,816 KB |
最終ジャッジ日時 | 2025-08-26 11:10:11 |
合計ジャッジ時間 | 7,336 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | WA * 1 TLE * 1 -- * 19 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using mint = atcoder::static_modint<2>; using namespace std; template <class T> struct Matrix : public std::vector<std::vector<T>> { Matrix() = default; Matrix(int h, int w, const T& v) : std::vector<std::vector<T>>(h, std::vector<T>(w, v)) {} Matrix(int h, int w) : Matrix(h, w, T{}) {} Matrix(const std::vector<std::vector<T>>& V) : std::vector<std::vector<T>>(V) {} Matrix(std::vector<std::vector<T>>&& V) : std::vector<std::vector<T>>(std::move(V)) {} static Matrix eye(int sz) { Matrix res(sz, sz); for (int i = 0; i < sz; i++) res[i][i] = 1; return res; } int height() const { return this->size(); } int width() const { return this->size() ? (*this)[0].size() : 0; } bool is_square() const { return height() == width(); } Matrix& operator+=(const Matrix& other) { assert(height() == other.height() && width() == other.width()); for (int i = 0; i < height(); i++) for (int j = 0; j < width(); j++) { (*this)[i][j] += other[i][j]; } return *this; } Matrix& operator-=(const Matrix& other) { assert(height() == other.height() && width() == other.width()); for (int i = 0; i < height(); i++) for (int j = 0; j < width(); j++) { (*this)[i][j] -= other[i][j]; } return *this; } Matrix& operator*=(const Matrix& other) { assert(width() == other.height()); Matrix res(height(), other.width()); for (int i = 0; i < height(); i++) { for (int k = 0; k < width(); k++) { for (int j = 0; j < other.width(); j++) { res[i][j] += (*this)[i][k] * other[k][j]; } } } return *this = std::move(res); } Matrix& operator*=(T s) { for (int i = 0; i < height(); i++) { for (int j = 0; j < width(); j++) { (*this)[i][j] *= s; } } return *this; } friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) += rhs; } friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) -= rhs; } friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) *= rhs; } friend Matrix operator*(const Matrix& lhs, T rhs) { return Matrix(lhs) *= rhs; } friend Matrix operator*(int lhs, const Matrix& rhs) { return Matrix(rhs) *= lhs; } Matrix pow(long long b) const { Matrix a = *this, res = eye(height()); while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } Matrix transpose() const { Matrix res(width(), height()); for (int i = 0; i < height(); i++) { for (int j = 0; j < width(); j++) { res[j][i] = (*this)[i][j]; } } return res; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::fixed(std::cout).precision(16); long long N, K; cin >> N >> K; vector<long long> A(N); for (int i = 0; i < N; i++) cin >> A[i]; if (K <= N) cout << (A[K - 1]) << "\n"; else { long long ans = 0; for (int it = 0; it <= 60; it++) { Matrix<mint> a(N, N); for (int j = 0; j < N; j++) a[0][j] = 1; for (int j = 0; j < N - 1; j++) a[j + 1][j] = 1; a = a.pow(K - N); mint t = 0; for (int i = 0; i < N; i++) t += a[0][i] * (A[i] >> it & 1); if (t.val()) ans += 1LL << it; } cout << ans << "\n"; } return 0; }