結果

問題 No.1879 How many matchings?
コンテスト
ユーザー 杨娵隅
提出日時 2022-03-19 11:49:35
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,003 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,108 ms
コンパイル使用メモリ 257,940 KB
最終ジャッジ日時 2025-01-28 10:45:36
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint1000000007;
const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define endl "\n"
#define P pair<int, int>
template <typename A, typename B>
inline bool chmax(A &a, const B &b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename A, typename B>
inline bool chmin(A &a, const B &b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
vector<vector<mint>> mul(vector<vector<mint>> &A, vector<vector<mint>> &B)
{
  vector<vector<mint>> C(A.size(), vector<mint>(B[0].size()));
  rep(i, A.size()) rep(j, B[0].size()) rep(k, A[0].size()) C[i][j] += A[i][k] * B[k][j];
  return C;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  long long n;
  cin >> n;
  vector<vector<mint>> mans(8, vector<mint>(8));
  vector<vector<mint>> mpow(8, vector<mint>(8));
  rep(i, 8) mans[i][i] = 1;
  mpow[0] = {1, 2, 1, 1, 0, 0, 0, 0};
  mpow[1] = {0, 1, 0, 1, 0, 0, 0, 0};
  mpow[2] = {1, 0, 0, 0, 0, 0, 0, 0};
  mpow[3] = {0, 1, 0, 0, 0, 0, 0, 0};
  mpow[4] = {0, 0, 1, 0, 0, 0, 0, 0};
  mpow[5] = {0, 0, 0, 1, 0, 0, 0, 0};
  mpow[6] = {0, 0, 0, 0, 1, 0, 0, 0};
  mpow[7] = {0, 0, 0, 0, 0, 1, 0, 0};
  long long copyn = n;
  if (0 == copyn % 2)
    copyn++;
  copyn /= 2;
  while (copyn > 0)
  {
    if (1 == copyn % 2)
      mans = mul(mpow, mans);
    copyn /= 2;
    mpow = mul(mpow, mpow);
  }
  mint ans = 0;
  if (1 == n % 2)
    ans = mans[0][0] + mans[0][1];
  else
    ans = mans[1][0] + mans[1][1];
  cout << ans.val() << endl;
  return 0;
}
0