結果
問題 | No.1879 How many matchings? |
ユーザー |
![]() |
提出日時 | 2022-03-18 23:19:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,867 bytes |
コンパイル時間 | 4,903 ms |
コンパイル使用メモリ | 256,824 KB |
最終ジャッジ日時 | 2025-01-28 10:40:51 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 7 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; typedef int64_t lint; #define rep(i, n) for(int i=0; i<n; i++) #define repx(i, l, n) for(int i=l; i<n; i++) #define all(v) v.begin(), v.end() #define show(x) cout << #x << ": " << x << endl; #define list(x) cout << #x << ": " << x << " "; #define pb push_back using vi = vector<lint>; using vvi = vector<vector<lint>>; template<class T> inline void vin(vector<T>& v) { rep(i, v.size()) cin >> v.at(i); } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template<class T> inline void drop(T x) { cout << x << endl; exit(0); } template<class T> void vout(vector<T> v) { rep(i, v.size()) { cout << v.at(i) << ' '; } cout << endl; } constexpr lint LINF = LLONG_MAX/2; using mint = modint1000000007; using vm = vector<mint>; using vvm = vector<vector<mint>>; vvm matrix_mul(vvm A, vvm B) { vvm C(A.size(), vm(B[0].size())); rep(i, A.size()) { rep(k, B.size()) { rep(j, B[0].size()) { C[i][j] += A[i][k] * B[k][j]; } } } return C; } vvm matrix_pow(vvm A, lint k) { vvm B(A.size(), vm(A.size())); // rep(i, A.size()) B[i][i] = 1; B[0][0] = 1; while (k > 0) { if (k & (lint)1) B = matrix_mul(B, A); A = matrix_mul(A, A); k >>= 1; } return B; } int main() { lint N; cin >> N; if (N == 1) drop(1); mint a=0, b=0, c=0, x, y, z; vvm A(5, vm(5)); A[0][0] = 1; A[1][0] = 1; A[0][1] = 1; A[1][2] = 1; A[0][3] = 1; A[3][3] = 1; A[1][4] = 1; A[4][4] = 1; vvm B = matrix_pow(A, N/2); // rep(i, 5) std::cout << B[0][i].val() << '\n'; if (N%2 == 0) { std::cout << B[0][0].val() << '\n'; } else if (N%2 == 1) { a = B[0][0]; b = B[0][3] * 2; c = B[0][4] * 4; std::cout << (b+c).val() << '\n'; } }