結果

問題 No.1879 How many matchings?
ユーザー cureskolcureskol
提出日時 2022-05-30 14:36:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,463 bytes
コンパイル時間 2,850 ms
コンパイル使用メモリ 221,016 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 00:51:53
合計ジャッジ時間 3,589 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 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 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef __LOCAL
 #include <debug>
#else
 #define debug(...) void(0)
#endif

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()

template<typename T>
istream& operator>>(istream&is,vector<T>&v){
  for(T&p:v)is>>p;
  return is;
}
template<typename T>
ostream& operator<<(ostream&os,const vector<T>&v){
  if(&os==&cerr)os<<"[";
  for(int i=0;i<v.size();i++){
    os<<v[i];
    if(i+1<v.size())os<<(&os==&cerr?",":" ");
  }
  if(&os==&cerr)os<<"]";
  return os;
}

template<typename T,T MOD=998244353>
struct Mint{
  inline static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0)v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1)res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator+() const{return *this;}
  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }

  friend ostream& operator<<(ostream&os,const Mint &m){os<<m.v;return os;}
  friend istream& operator>>(istream&is,Mint &m){is>>m.v;m.v%=MOD;if(m.v<0)m.v+=MOD;return is;}
};

using ll=long long;
using mint=Mint<ll,1000000007>;

#define REP_(i,n) for(int i=0;i<(n);i++)
#define REP2_(i,s,n) for(int i=(s);i<(n);i++)
template<typename K>
struct Matrix{
  typedef vector<K> vec;
  typedef vector<vec> mat;
  size_t r,c;
  mat M;

  Matrix(size_t r,size_t c):r(r),c(c),M(r,vec(c,K())){}
  Matrix(mat A):M(A),r(A.size()),c(A[0].size()){}

  vec& operator[](size_t k){return M[k];}
  const vec& operator[](size_t k)const{return M[k];}

  friend Matrix operator+(const Matrix &A,const Matrix &B){
    assert(A.r==B.r&&A.c==B.c);
    Matrix res(A);
    REP_(i,A.r)REP_(j,A.c)res[i][j]+=B[i][j];
    return res;
  }

  Matrix& operator+=(const Matrix &B){
    assert(r==B.r&&c==B.c);
    REP_(i,r)REP_(j,c)M[i][j]+=B[i][j];
    return *this;
  }

  friend Matrix operator*(const Matrix &A,const Matrix &B){
    assert(A.c==B.r);
    Matrix res(A.r,B.c);
    REP_(i,A.r)REP_(k,A.c)REP_(j,B.c)res[i][j]+=A[i][k]*B[k][j];
    return res;
  }

  Matrix& operator*=(const Matrix &B){
    M=((*this)*B).M;
    return *this;
  }

  static Matrix I(size_t n){
    Matrix res(n,n);
    REP_(i,n)res[i][i]=K(1);
    return res;
  }

  Matrix pow(long long n)const{
    assert(n>=0&&r==c);
    Matrix A(M),res=I(r);
    while(n){
      if(n&1)res*=A;
      A*=A;
      n>>=1;
    }
    return res;
  }

  int rank() const{
    Matrix A(M);
    int res=0;
    REP_(k,c){
      for(int i=res+1;i<r&&A[res][k]==0;i++)
        if(A[i][k]!=0)swap(A[i],A[res]);
      if(A[res][k]==0)continue;
      REP2_(l,k+1,c)A[res][l]/=A[res][k];
      REP2_(j,res+1,r)REP2_(l,k+1,c)A[j][l]-=A[j][k]*A[res][l];
      res++;
    }
    return res;
  }

  K det() const{
    assert(r==c);
    Matrix A=M;
    K res(1);
    REP_(i,r){
      for(int j=i+1;j<c&&A[i][i]==0;j++)
        if(A[j][i]!=0)swap(A[i],A[j]),res=-res;
      if(A[i][i]==0)return 0;
      res*=A[i][i];
      REP2_(k,i+1,c)A[i][k]/=A[i][i];
      REP2_(j,i+1,r)REP2_(k,i+1,c)A[j][k]-=A[j][i]*A[i][k];
    }
    return res;
  }
};
#undef REP_
#undef REP2_

/**
* @docs //docs/matrix.md
*/

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  ll n;cin>>n;
  if(n&1){
    Matrix<mint> A(8,8);
    A[4][6]=A[6][7]=A[4][5]=A[7][5]=A[5][4]=A[1][0]=A[3][1]=A[0][1]=A[5][2]=A[0][2]=A[2][3]=A[4][3]=A[7][3]=1;
    A=A.pow(n);
    cout<<A[4][0]+A[2][0]+A[1][0]<<endl;
  }
  else{
    Matrix<mint> A(4,4);
    A[0][2]=A[2][3]=A[0][1]=A[3][1]=A[1][0]=1;
    A=A.pow(n);
    cout<<A[0][0]<<endl;
  }
}
0