#768979 (C++17) No.1811 EQUIV Ten

• 問題: No.1811 EQUIV Ten
• ユーザー: eQe
• 提出日時: 2022-06-08 14:39:46
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 6,831 bytes
• コンパイル時間: 4,797 ms
• コンパイル使用メモリ: 271,904 KB
• 最終ジャッジ日時: 2025-01-29 19:01:45
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

#include<atcoder/all>
#include<bits/stdc++.h>
using namespace atcoder;
using namespace std;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fin(a) return pt(a)
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using ll=long long;
using ld=long double;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using pll=pair<ll,ll>;
using mll=map<ll,ll>;
ll inf=3e18;
ld pi=acos(-1);
ld eps=1e-10;
template<class T>using max_priority_queue=std::priority_queue<T>;
template<class T>using min_priority_queue=std::priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
template<class T>T max(const vector<T>&a){return *max_element(all(a));}
template<class T>T min(const vector<T>&a){return *min_element(all(a));}
template<class T>T sum(const vector<T>&a){return accumulate(all(a),T(0));}
template<class T>T popcnt(T a){return __builtin_popcountll(a);}
template<class T>ll lbp(const vector<T>&a,const T&b){return lower_bound(all(a),b)-a.begin();}
template<class T>ll ubp(const vector<T>&a,const T&b){return upper_bound(all(a),b)-a.begin();}
template<class T>pll mima(const T&a,const T&b){return {min(a,b),max(a,b)};}
template<class T>void sort(vector<T>&v){sort(all(v));}
template<class T,class F>void sort(vector<T>&v,const F&f){sort(all(v),f);}
template<class T>void rev(vector<T>&v){reverse(all(v));}
template<class T>void usort(vector<T>&v){sort(all(v));v.erase(unique(all(v)),v.end());}
ostream&operator<<(ostream&os,const modint1000000007&x){return os<<x.val();}
ostream&operator<<(ostream&os,const modint998244353&x){return os<<x.val();}
ostream&operator<<(ostream&os,const modint&x){return os<<x.val();}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){return is>>p.first>>p.second;}
template<class T1,class T2>ostream&operator<<(ostream&os,const pair<T1,T2>&p){return os<<p.first<<" "<<p.second;}
template<class T>istream&operator>>(istream&is,vector<T>&v){for(T&x:v)is>>x;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&v){for(ll i=0;i<(ll)v.size();i++)os<<v[i]<<(i+1==(ll)v.size()?"":" ");return os;}
template<class...A>ll pt_rest(){cout<<'\n';return 0;}
template<class...A>ll pt(){cout<<'\n';return 0;}
template<class T,class...A>ll pt_rest(const T&first,const A&...rest){cout<<" "<<first;pt_rest(rest...);return 0;}
template<class T,class...A>ll pt(const T&first,const A&...rest){cout<<first;pt_rest(rest...);return 0;}
template<class V,class H>void resize(vector<V>&vec,const H head){vec.resize(head);}
template<class V,class H,class...T>void resize(vector<V>&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);}
template<class V,class T>void fill(V&x,const T&val){x=val;}
template<class V,class T>void fill(vector<V>&vec,const T&val){for(auto&v:vec)fill(v,val);}
template<class H>void vin(istream&is,const ll idx,vector<H>&head){is>>head[idx];}
template<class H,class...T>void vin(istream&is,const ll idx,vector<H>&head,T&...tail){vin(is>>head[idx],idx,tail...);}
template<class H,class...T>void vin(istream&is,vector<H>&head,T&...tail){for(ll i=0;i<(ll)head.size();i++)vin(is,i,head,tail...);}
template<class H,class...T>void vin(vector<H>&head,T&...tail){vin(cin,head,tail...);}
template<class H>void sin(istream&is,H&head){is>>head;}
template<class H,class...T>void sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);}
template<class H,class...T>void sin(H&head,T&...tail){sin(cin,head,tail...);}
template<class T>void printv2(vector<vector<T>>&a){for(ll i=0;i<a.size();i++){for(ll j=0;j<a.size();j++)cout<<a[i][j]<<" ";pt();}}
v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++){if(n%i==0){m[i]++;m[n/i]++;}}v1 v;for(auto[x,_]:m)v.emplace_back(x);return v;}
mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++){while(n%i==0){m[i]++;n/=i;}}if(n>1)m[n]++;return m;}
ll lpow(ll x,ll n,ll m=0){ll r=1;while(n>0){if(n&1){if(m)r=r*x%m;else r*=x;}x*=x;n>>=1;}return r;}
ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while(r+1<=x/(r+1))r++;return r;}
ll llog2(ll n){ll r=0;while(n)n>>=1,r++;return r;}
ll bit(ll n){return 1LL<<n;}
v1 dx={0,-1,0,1},dy={-1,0,1,0};
using S=ll;
S op(S a,S b){return a+b;}
S e(){return 0;}

template<class T>struct mat{
  vector<vector<T>>m;
  ll h,w;
  mat(ll h):h(h),w(h){resize(m,h,h);}
  mat(ll h,ll w):h(h),w(w){resize(m,h,w);}
  mat(ll h,ll w,T x):h(h),w(w){resize(m,h,w);fill(m,x);}
  mat(vector<vector<T>>v):h(v.size()),w(v[0].size()){resize(m,h,w);rep(i,h)rep(j,w)m[i][j]=v[i][j];}
  
  vector<T>operator[](const ll i)const{return m[i];}
  vector<T>&operator[](const ll i){return m[i];}
  
  mat&operator=(const mat&a){h=a.h;w=a.w;resize(m,h,w);rep(i,h)rep(j,w)m[i][j]=a[i][j];return *this;}
  mat&operator+=(const mat&a){assert(h==a.h and w==a.w);rep(i,h)rep(j,w)m[i][j]+=a[i][j];return *this;}
  mat&operator-=(const mat&a){assert(h==a.h and w==a.w);rep(i,h)rep(j,w)m[i][j]-=a[i][j];return *this;}
  mat&operator*=(const mat&a){
    assert(w==a.h);
    mat m2(h,a.w);
    rep(i,h)rep(j,a.w)rep(k,w)m2[i][j]+=m[i][k]*a[k][j];
    w=a.w;
    resize(m,h,w);
    rep(i,h)rep(j,w)m[i][j]=m2[i][j];
    return *this;
  }
  
  //行列
  mat operator+(const mat&a)const{return mat(*this)+=a;}
  mat operator-(const mat&a)const{return mat(*this)-=a;}
  mat operator*(const mat&a)const{return mat(*this)*=a;}
  bool operator==(const mat&a){assert(h==a.h and w==a.w);rep(i,h)rep(j,w)if(m[i][j]!=a[i][j])return 0;return 1;}
  
  //スカラ
  mat&operator+=(const T&a){rep(i,h)rep(j,w)m[i][j]+=a;return *this;}
  mat&operator-=(const T&a){rep(i,h)rep(j,w)m[i][j]-=a;return *this;}
  mat&operator*=(const T&a){rep(i,h)rep(j,w)m[i][j]*=a;return *this;}
  mat&operator/=(const T&a){rep(i,h)rep(j,w)m[i][j]/=a;return *this;}
  mat operator+(const T&a)const{return mat(*this)+=a;}
  mat operator-(const T&a)const{return mat(*this)-=a;}
  mat operator*(const T&a)const{return mat(*this)*=a;}
  mat operator/(const T&a)const{return mat(*this)/=a;}
  
  mat pow(ll n){
    assert(h==w);
    mat x(*this);
    mat r(h);rep(i,h)r[i][i]=1;
    while(n){
      if(n&1)r*=x;
      x*=x;
      n>>=1;
    }
    return r;
  }
  
  void transpose(){
    mat m2(w,h);
    rep(i,h)rep(j,w)m2[j][i]=m[i][j];
    swap(h,w);
    resize(m,h,w);
    rep(i,h)rep(j,w)m[i][j]=m2[i][j];
  }
  
  friend ostream&operator<<(ostream&os,const mat&m){
    rep(i,m.h){
      rep(j,m.w)os<<m[i][j]<<(j<m.w-1?" ":"");
      if(i<m.h-1)os<<'\n';
    }
    return os;
  }
};

int main(void){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll N;cin>>N;
  
  using mint=modint1000000007;
  mat<mint>a(
    {{1,0,1,0,0},
    {1,1,0,1,0},
    {0,1,0,0,0},
    {0,0,1,0,0},
    {0,0,0,1,2}});
  
  mat<mint>v({{1,0,0,0,0}});
  v.transpose();
  a=a.pow(N);
  a*=v;
  pt(a[4][0]);
}