結果

問題 No.1105 Many Triplets
ユーザー ateate
提出日時 2020-07-11 00:46:24
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,831 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 81,424 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 21:36:22
合計ジャッジ時間 1,844 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<cassert>

template<int64_t MOD>
struct mod_int{
  int64_t val;
  constexpr mod_int():val(0){}
  constexpr mod_int(int64_t x)noexcept:val(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD){}
  constexpr int64_t value()const noexcept{return val;}
  constexpr int64_t get_MOD()const noexcept{return MOD;}
  constexpr mod_int operator+(mod_int const& rhs){
    return mod_int(*this)+=rhs;
  }
  constexpr mod_int operator-(mod_int const& rhs){
    return mod_int(*this)-=rhs;
  }
  constexpr mod_int operator*(mod_int const& rhs){
    return mod_int(*this)*=rhs;
  }
  constexpr mod_int operator/(mod_int const& rhs){
    return mod_int(*this)/=rhs;
  }
  constexpr mod_int &operator+=(mod_int const& rhs)noexcept{
    val += rhs.val;
    if(val>=MOD)val-=MOD;
    return *this;
  }
  constexpr mod_int &operator-=(mod_int const& rhs)noexcept{
    if(val<rhs.val)val+=MOD;
    val-=rhs.val;
    return *this;
  }
  constexpr mod_int &operator*=(mod_int const& rhs)noexcept{
    (val*=rhs.val)%=MOD;
    return *this;
  }
  constexpr mod_int &operator/=(mod_int rhs)noexcept{
    *this*=rhs.inverse();
    return *this;
  }
  constexpr bool operator==(mod_int const& rhs)const{
    return val==rhs.val;
  }
  constexpr bool operator!=(mod_int const& rhs)const{
    return !(val==rhs.val);
  }
  constexpr bool operator<(mod_int const& rhs)const{
    return val<rhs.val;
  }
  constexpr bool operator>(mod_int const& rhs)const{
    return val>rhs.val;
  }
  constexpr bool operator<=(mod_int const& rhs)const{
    return !(val>rhs.val);
  }
  constexpr bool operator>=(mod_int const& rhs)const{
    return !(val<rhs.val);
  }
  constexpr friend std::ostream &operator<<(std::ostream& os, mod_int const& mi){
    return os<<mi.val;
  }
  constexpr friend std::istream &operator>>(std::istream& is, mod_int & mi){
    int64_t t=0;is>>t;
    mi = mod_int<MOD>(t);
    return is;
  }
  constexpr mod_int inverse(){
    int64_t a=val,b=MOD,u=1,v=0,t=0;
    while(b>0){
      t=a/b;
      std::swap(a-=t*b,b);
      std::swap(u-=t*v,v);
    }
    return mod_int(u);
  }
  constexpr mod_int mpow(int64_t n)const{
    mod_int res(1),e(*this);
    while(n){
      if(n&1)res*=e;
      e*=e;
      n>>=1;
    }
    return res;
  }
};
using mint = mod_int<1000000007>;
mint mpow(int64_t p,int64_t n){
  mint res=1;
  mint e = p;
  while(n){
    if(n&1)res*=e;
    e*=e;
    n>>=1;
  }
  return res;
}

template<class T>
struct matrix{
  int row,col;
  T add_identity,mul_identity;
  std::vector<std::vector<T>> data;
  constexpr matrix(){}
  constexpr matrix(int n,T ai,T mi):row(n),col(n),add_identity(ai),mul_identity(mi),data(n,std::vector<T>(n,ai)){}
  constexpr matrix(int r,int c,T ai,T mi):row(r),col(c),add_identity(ai),mul_identity(mi),data(r,std::vector<T>(c,ai)){}
  constexpr matrix(int r,int c,T v,T ai,T mi):row(r),col(c),add_identity(ai),mul_identity(mi),data(r,std::vector<T>(c,v)){}
  std::vector<T>& operator[](int r){return data[r];}
  constexpr const inline std::vector<T>& operator[](int r)const{return data[r];}
  constexpr inline std::vector<T>& at(int r){return data.at(r);}
  constexpr matrix identity_matrix()const{
    assert(row==col);
    matrix ide(row,col,add_identity,add_identity,mul_identity);
    for(int i=0;i<row;++i)ide[i][i]=mul_identity;
    return ide;
  }
  constexpr matrix operator + (matrix const& another){
    assert(row==another.row&&col==another.col);
    matrix res(row,col,add_identity,mul_identity);
    for(int i=0;i<row;++i)
      for(int j=0;j<col;++j)
        res[i][j] = data[i][j]+another[i][j];
    return res;
  }
  constexpr matrix operator * (matrix const& another){
    assert(col==another.row);
    matrix res(row,another.col,add_identity,mul_identity);
    for(int i=0;i<row;++i)
      for(int j=0;j<another.col;++j)
        for(int k=0;k<col;++k)
          res[i][j] = res[i][j]+(data[i][k]*another[k][j]);
    return res;
  }
  constexpr bool operator==(matrix const& another)const{
    return data==another.data;
  }
  friend std::ostream& operator<<(std::ostream& os,matrix const& mat){
    for(int i=0;i<mat.row;++i)
      for(int j=0;j<mat.col;++j)
        os<<mat[i][j]<<" \n"[j+1<mat.col];
    return os;
  }
  friend std::iostream& operator>>(std::iostream& is,matrix& mat){
    for(int i=0;i<mat.row;++i)
      for(int j=0;j<mat.col;++j)
        is>>mat.data[i][j];
    return is;
  }
  constexpr matrix pow(int64_t n){
    matrix a = *this;
    matrix res = identity_matrix();
    while(n){
      if(n&1)res=res*a;
      a=a*a;
      n>>=1;
    }
    return res;
  }
};

signed main(){
  using namespace std;
  
  matrix<mint> a(3,3,0,1);
  matrix<mint> b(3,1,0,1);
  a[0][0] = a[1][1] = a[2][2] = 1;
  a[0][1] = a[1][2] = a[2][0] = -1;
  int64_t n;
  cin>>n;
  a = a.pow(n-1);
  //cin>>b;
  cin>>b[0][0]>>b[1][0]>>b[2][0];
  cout<< a*b <<endl;

}
0