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

提出ソース

結果

問題	No.1811 EQUIV Ten
ユーザー	eQe
提出日時	2022-07-10 19:31:33
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	11,650 bytes
コンパイル時間	17,783 ms
コンパイル使用メモリ	526,380 KB
実行使用メモリ	4,356 KB
最終ジャッジ日時	2023-09-02 02:55:54
合計ジャッジ時間	15,808 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,332 KB
testcase_01	AC	2 ms 4,332 KB
testcase_02	AC	1 ms 4,332 KB
testcase_03	AC	2 ms 4,332 KB
testcase_04	AC	2 ms 4,332 KB
testcase_05	AC	1 ms 4,336 KB
testcase_06	AC	1 ms 4,336 KB
testcase_07	AC	1 ms 4,328 KB
testcase_08	AC	1 ms 4,332 KB
testcase_09	AC	1 ms 4,336 KB
testcase_10	AC	1 ms 4,328 KB
testcase_11	AC	2 ms 4,332 KB
testcase_12	AC	1 ms 4,328 KB
testcase_13	AC	1 ms 4,332 KB
testcase_14	AC	2 ms 4,332 KB
testcase_15	AC	2 ms 4,332 KB
testcase_16	AC	2 ms 4,328 KB
testcase_17	AC	1 ms 4,332 KB
testcase_18	AC	2 ms 4,332 KB
testcase_19	AC	1 ms 4,328 KB
testcase_20	AC	1 ms 4,332 KB
testcase_21	AC	2 ms 4,332 KB
testcase_22	AC	1 ms 4,332 KB
testcase_23	AC	1 ms 4,332 KB
testcase_24	AC	1 ms 4,332 KB
testcase_25	AC	1 ms 4,332 KB
testcase_26	AC	2 ms 4,328 KB
testcase_27	AC	2 ms 4,332 KB
testcase_28	AC	2 ms 4,328 KB
testcase_29	AC	2 ms 4,328 KB
testcase_30	AC	2 ms 4,356 KB
testcase_31	AC	2 ms 4,332 KB
testcase_32	AC	1 ms 4,332 KB
testcase_33	AC	2 ms 4,332 KB
testcase_34	AC	1 ms 4,332 KB
testcase_35	AC	2 ms 4,332 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("avx512f")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<atcoder/all>
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
using namespace atcoder;
using namespace std;
using namespace boost::multiprecision;
#define fst first
#define snd second
#define len(a) (ll)size(a)
#define ppc(a) (ll)__builtin_popcountll(a)
#define sq(a) ((a)*(a))
#define bit(a) (1LL<<(a))
#define fin(...) exit(pt(__VA_ARGS__))
#define pb() pop_back()
#define ep(...) emplace(__VA_ARGS__)
#define eb(...) emplace_back(__VA_ARGS__)
#define ef(...) emplace_front(__VA_ARGS__)
#define ei(...) else if(__VA_ARGS__)
#define el else
#define wh(...) while(__VA_ARGS__)
#define lb(...) lower_bound(__VA_ARGS__)
#define ub(...) upper_bound(__VA_ARGS__)
#define srt(...) sort(all(__VA_ARGS__))
#define rev(...) reverse(all(__VA_ARGS__))
#define uni(a) srt(a);a.erase(unique(all(a)),end(a))
#define join(a,b) copy(all(b),back_inserter(a))
#define ov3(a,b,c,d,...) d
#define ov4(a,b,c,d,e,...) e
#define ov5(a,b,c,d,e,f,...) f
#define ov6(a,b,c,d,e,f,g,...) g
#define bg begin
#define rbg rbegin
#define all1(v) bg(v),end(v)
#define all2(v,b) bg(v),bg(v)+b
#define all3(v,a,b) bg(v)+a,bg(v)+b
#define all(...) ov3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rll1(v) rbg(v),rend(v)
#define rll2(v,b) rbg(v),rbg(v)+b
#define rll3(v,a,b) rbg(v)+a,rbg(v)+b
#define rll(...) ov3(__VA_ARGS__,rll3,rll2,rll1)(__VA_ARGS__)
#define rep1(b) for(ll _i=0;_i<(ll)(b);_i++)
#define rep2(i,b) for(ll i=0;i<(ll)(b);i++)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c))
#define rep(...) ov4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(a) rep(a)
#define per2(i,a) for(ll i=(ll)(a)-1;i>=0;i--)
#define per3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--)
#define per4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c))
#define per(...) ov4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define foe1(a) rep(len(a))
#define foe2(a,v) for(auto&&a:v)
#define foe3(a,b,v) for(auto&&[a,b]:v)
#define foe4(a,b,c,v) for(auto&&[a,b,c]:v)
#define foe5(a,b,c,d,v) for(autoto&&[a,b,c,d]:v)
#define foe(...) ov5(__VA_ARGS__,foe5,foe4,foe3,foe2,foe1)(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__)
#define ST(...) str __VA_ARGS__;lin(__VA_ARGS__)
#define UL2(n,a) u1 a(n);lin(a)
#define UL3(n,a,b) u1 a(n),b(n);lin(a,b)
#define UL4(n,a,b,c) u1 a(n),b(n),c(n);lin(a,b,c)
#define UL5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);lin(a,b,c,d)
#define UL6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);lin(a,b,c,d,e)
#define UL(...) ov6(__VA_ARGS__,UL6,UL5,UL4,UL3,UL2)(__VA_ARGS__)
#define UV2(n,a) u1 a(n);vin(a)
#define UV3(n,a,b) u1 a(n),b(n);vin(a,b)
#define UV4(n,a,b,c) u1 a(n),b(n),c(n);vin(a,b,c)
#define UV5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);vin(a,b,c,d)
#define UV6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);vin(a,b,c,d,e)
#define UV(...) ov6(__VA_ARGS__,UV6,UV5,UV4,UV3,UV2)(__VA_ARGS__)
#define DL2(n,a) v1<ld>a(n);lin(a)
#define DL3(n,a,b) v1<ld>a(n),b(n);lin(a,b)
#define DL4(n,a,b,c) v1<ld>a(n),b(n),c(n);lin(a,b,c)
#define DL5(n,a,b,c,d) v1<ld>a(n),b(n),c(n),d(n);lin(a,b,c,d)
#define DL(...) ov5(__VA_ARGS__,DL5,DL4,DL3,DL2)(__VA_ARGS__)
#define DV2(n,a) v1<ld>a(n);vin(a)
#define DV3(n,a,b) v1<ld>a(n),b(n);vin(a,b)
#define DV4(n,a,b,c) v1<ld>a(n),b(n),c(n);vin(a,b,c)
#define DV5(n,a,b,c,d) v1<ld>a(n),b(n),c(n),d(n);vin(a,b,c,d)
#define DV(...) ov5(__VA_ARGS__,DV5,DV4,DV3,DV2)(__VA_ARGS__)
#define tm template
#define cl class
#define op operator
#define fn function
#define cons const
#define rt return
#define cont continue
#define endl "\n"
#define sp " "
#define as assert
using ll=long long;
using ld=long double;
using str=string;
tm<cl T>using v1=vector<T>;
tm<cl T>using v2=v1<v1<T>>;
tm<cl T>using v3=v1<v2<T>>;
tm<cl T>using v4=v1<v3<T>>;
tm<cl T>using mset=multiset<T>;
using u1=v1<ll>;
using u2=v1<u1>;
using u3=v1<u2>;
using u4=v1<u3>;
using pll=pair<ll,ll>;
using qll=queue<ll>;
using sll=set<ll>;
using msll=mset<ll>;
using mll=map<ll,ll>;
using mint=modint1000000007;
using is=istream;
using os=ostream;
ll inf=3e18;
ld pi=acosl(-1);
ld eps=1e-10;
tm<cl T>using max_heap=std::priority_queue<T>;
tm<cl T>using min_heap=std::priority_queue<T,v1<T>,greater<T>>;
tm<cl T>ll sig(cons T&a){rt(a>eps)-(a<-eps);}
tm<cl T>ll sig(cons T&a,cons T&b){rt sig(a-b);}
tm<cl T>v1<T>&op++(v1<T>&v){foe(x,v)x++;rt v;}
tm<cl T>v1<T>&op--(v1<T>&v){foe(x,v)x--;rt v;}
tm<cl T>v1<T>op++(v1<T>&v,int){auto r=v;++v;rt r;}
tm<cl T>v1<T>op--(v1<T>&v,int){auto r=v;--v;rt r;}
tm<cl T,cl U>v1<T>&op+=(v1<T>&v,cons U&a){foe(x,v)x+=a;rt v;}
tm<cl T,cl U>v1<T>&op-=(v1<T>&v,cons U&a){foe(x,v)x-=a;rt v;}
tm<cl T,cl U>v1<T>&op*=(v1<T>&v,cons U&a){foe(x,v)x*=a;rt v;}
tm<cl T,cl U>v1<T>&op/=(v1<T>&v,cons U&a){foe(x,v)x/=a;rt v;}
tm<cl T>v1<T>&op+=(v1<T>&v,cons v1<T>&u){rep(i,len(v))v[i]+=u[i];rt v;}
tm<cl T>v1<T>&op-=(v1<T>&v,cons v1<T>&u){rep(i,len(v))v[i]-=u[i];rt v;}
tm<cl T>v1<T>&op*=(v1<T>&v,cons v1<T>&u){rep(i,len(v))v[i]*=u[i];rt v;}
tm<cl T>v1<T>&op/=(v1<T>&v,cons v1<T>&u){rep(i,len(v))v[i]/=u[i];rt v;}
tm<cl T,cl U>bool cma(T&a,cons U&b){rt a<b?a=b,1:0;}
tm<cl T,cl U>bool cmi(T&a,cons U&b){rt a>b?a=b,1:0;}
tm<cl T>T max(cons v1<T>&a){rt *max_element(all(a));}
tm<cl T>T min(cons v1<T>&a){rt *min_element(all(a));}
tm<cl...T>auto max(T...a){rt max(initializer_list<common_type_t<T...>>{a...});}
tm<cl...T>auto min(T...a){rt min(initializer_list<common_type_t<T...>>{a...});}
tm<cl T,cl...A>T gcd(cons T&a,cons A&...b){rt gcd(a,gcd(b...));}
tm<cl T>T sum(cons v1<T>&a){rt accumulate(all(a),T(0));}
tm<cl T>ll lbs(cons v1<T>&a,cons T&b){rt lb(all(a),b)-bg(a);}
tm<cl T>ll ubs(cons v1<T>&a,cons T&b){rt ub(all(a),b)-bg(a);}
tm<cl T>pair<T,T>mima(cons T&a,cons T&b){rt{min(a,b),max(a,b)};}
tm<cl T>pair<T,T>mima(cons pair<T,T>&p){rt mima(p.fst,p.snd);}
tm<cl T>T at(cons v1<T>&v,cons ll&i){ll n=len(v);rt v[(i%n+n)%n];}
u1 iota(ll n,ll s=0){u1 a(n);iota(all(a),s);rt a;}
void emplace_front(u1&v,ll x=0){v.ep(bg(v),x);}
tm<cl T,cl U>auto keys(cons map<T,U>&m){v1<T>r;foe(k,_,m)r.eb(k);rt r;}
tm<cl T,cl U>auto vals(cons map<T,U>&m){v1<U>r;foe(_,v,m)r.eb(v);rt r;}


struct fio{
  fio(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(10);
  }
}fio;
is&op>>(is&i,mint&x){ll t;i>>t;x=t;rt i;}
os&op<<(os&o,cons mint&x){rt o<<x.val();}
tm<cl T,cl U>is&op>>(is&i,pair<T,U>&p){rt i>>p.fst>>p.snd;}
tm<cl T,cl U>os&op<<(os&o,cons pair<T,U>&p){rt o<<p.fst<<sp<<p.snd;}
tm<cl T>is&op>>(is&i,v1<T>&v){foe(x,v)i>>x;rt i;}
tm<cl T>os&op<<(os&o,cons v1<T>&v){foe(x,v)o<<x<<(&x==&*rbg(v)?"":sp);rt o;}
tm<cl T>os&op<<(os&o,cons v2<T>&v){foe(x,v)o<<x<<(&x==&*rbg(v)?"":endl);rt o;}
tm<cl T>os&op<<(os&o,cons set<T>&s){foe(x,s)o<<x<<(&x==&*rbg(s)?"":sp);rt o;}
tm<cl T>os&op<<(os&o,cons mset<T>&s){foe(x,s)o<<x<<(&x==&*rbg(s)?"":sp);rt o;}
tm<cl T,cl U>
os&op<<(os&o,cons map<T,U>&m){foe(p,m)o<<p<<(&p==&*rbg(m)?"":endl);rt o;}
tm<cl T>os&op<<(os&o,queue<T>q){wh(len(q))o<<q.front()<<sp,q.pop();rt o;}
tm<cl T>os&op<<(os&o,deque<T>q){wh(len(q))o<<q.front()<<sp,q.pop_front();rt o;}
tm<cl T>os&op<<(os&o,max_heap<T>q){wh(len(q))o<<q.top()<<sp,q.pop();rt o;}
tm<cl T>os&op<<(os&o,min_heap<T>q){wh(len(q))o<<q.top()<<sp,q.pop();rt o;}
ll pt(){cout<<endl;rt 0;}
ll db(){cerr<<endl;rt 0;}
tm<cl T,cl...A>ll pt(cons T&a,cons A&...b){cout<<a;((cout<<sp<<b),...);rt pt();}
tm<cl T,cl...A>ll db(cons T&a,cons A&...b){cerr<<a;((cerr<<sp<<b),...);rt db();}
tm<cl...T>void lin(T&...a){(cin>>...>>a);}
tm<cl...T>void vin(cons ll&i,T&...a){(cin>>...>>a[i]);}
tm<cl T,cl...A>void vin(v1<T>&a,A&...b){rep(i,len(a))vin(i,a,b...);}
str first(bool f=1){rt f?"first":"second";}
str First(bool f=1){rt f?"First":"Second";}
str yes(bool f=1){rt f?"yes":"no";}
str Yes(bool f=1){rt f?"Yes":"No";}
str YES(bool f=1){rt f?"YES":"NO";}
str no(){rt "no";}
str No(){rt "No";}
str NO(){rt "NO";}
str possible(bool f=1){rt f?"possible":"impossible";}
str Possible(bool f=1){rt f?"Possible":"Impossible";}
str POSSIBLE(bool f=1){rt f?"POSSIBLE":"IMPOSSIBLE";}


tm<cl V,cl T>void rs(v1<V>&v,cons T&a){v.resize(a);}
tm<cl V,cl T,cl...A>void rs(v1<V>&u,cons T&a,cons A&...b){
  rs(u,a);
  foe(v,u)rs(v,b...);
}
tm<cl V,cl T>void fl(V&v,cons T&x){v=x;}
tm<cl V,cl T>void fl(v1<V>&u,cons T&x){foe(v,u)fl(v,x);}
void zi(cons u1&v,u1&h){foe(x,h)x=lbs(v,x);}
tm<cl...T>void zi(cons u1&v,u1&h,T&...t){zi(v,h);zi(v,t...);}
tm<cl...T>u1 zip(T&...a){u1 v;foe(e,{a...})join(v,e);uni(v);zi(v,a...);rt v;}
tm<cl T>void vs(cons u1&o,v1<T>&a){auto c=a;rep(i,len(a))a[i]=c[o[i]];}
tm<cl T,cl...A>void vs(cons u1&o,v1<T>&a,A&...b){vs(o,a);vs(o,b...);}
tm<cl...T>pair<u1,u1>vsrt(cons fn<bool(ll,ll)>&f,T&...a){
  ll n=0;
  foe(e,{a...})n=len(e);
  u1 o=iota(n),p(n);
  sort(all(o),f);
  rep(i,n)p[o[i]]=i;
  vs(o,a...);
  rt{o,p};
}
tm<cl T>T bs(cons fn<bool(T)>&j,T o,T n){
  T d=(T)eps?eps:1;
  wh(abs(o-n)>d)(j((o+n)/2)?o:n)=(o+n)/2;
  rt o;
}


tm<cl T>auto zt(v1<T>a){rep(i,1,len(a))a[i]+=a[i-1];rt a;}
tm<cl T>auto mb(v1<T>a){per(i,len(a),1)a[i]-=a[i-1];rt a;}
tm<cl T>auto zt(v2<T>a){foe(v,a)v=zt(v);rep(i,1,len(a))a[i]+=a[i-1];rt a;}
tm<cl T>auto mb(v2<T>a){foe(v,a)v=mb(v);per(i,len(a),1)a[i]-=a[i-1];rt a;}
u1 dvs(ll n){mll m;rep(i,1,n/i+1)if(n%i==0)m[i]++,m[n/i]++;rt keys(m);}
mll fct(ll n){mll m;rep(i,2,n/i+1)wh(n%i==0)m[i]++,n/=i;if(n>1)m[n]++;rt m;}
ll pom(ll x,ll n,ll m=inf){ll r=1;wh(n){if(n&1)r*=x,r%=m;x*=x,x%=m,n/=2;}rt r;}
ll inm(ll a,ll m){
  ll b=m,u=1,v=0;
  wh(b)u-=a/b*v,swap(u,v),a-=a/b*b,swap(a,b);
  rt(u%m+m)%m;
}
ll sqr(ll x){ll r=sqrtl(x)-1;wh(r+1<=x/(r+1))r++;rt r;}
ll lg2(ll n){ll r=0;wh(n){n/=2;r++;}rt r;}
mint ham(mint a){rt (a+1346)*(a+9185);}
u1 dx={-1,0,1,0,-1,1,1,-1};
u1 dy={0,-1,0,1,-1,-1,1,1};
using S=ll;
S ema(){rt -inf;}
S emi(){rt inf;}
S oad(S a,S b){rt a+b;}
S ead(){rt 0;}
S ope(S a,S b){rt a+b;}
S ein(){rt 0;}
using sgma=segtree<S,max,ema>;
using sgmi=segtree<S,min,emi>;
using sgad=segtree<S,oad,ead>;
using sgt=segtree<S,ope,ein>;


tm<cl T>struct mat{
  v2<T>m;
  ll h,w;
  mat(ll k):h(k),w(k){rs(m,k,k);}
  mat(ll h,ll w):h(h),w(w){rs(m,h,w);}
  mat(ll h,ll w,T x):h(h),w(w){rs(m,h,w);fl(m,x);}
  mat(v2<T>a):h(len(a)),w(len(a[0])),m(a){}
  
  v1<T>op[](cons ll&i)cons{rt m[i];}
  v1<T>&op[](cons ll&i){rt m[i];}
  
  mat&op+=(cons mat&a){as(h==a.h and w==a.w);rep(i,h)m[i]+=a[i];rt*this;}
  mat&op-=(cons mat&a){as(h==a.h and w==a.w);rep(i,h)m[i]-=a[i];rt*this;}
  mat&op*=(cons mat&a){
    as(w==a.h);
    mat m2(h,a.w);
    rep(i,h)rep(k,w)rep(j,a.w)m2[i][j]+=m[i][k]*a[k][j];
    rt *this=m2;
  }
  
  //行列
  mat op+(cons mat&a)cons{rt mat(*this)+=a;}
  mat op-(cons mat&a)cons{rt mat(*this)-=a;}
  mat op*(cons mat&a)cons{rt mat(*this)*=a;}
  bool op==(cons mat&a){rt m==a.m;}
  
  //スカラ
  mat&op+=(cons T&a){foe(v,m)v+=a;rt*this;}
  mat&op-=(cons T&a){foe(v,m)v-=a;rt*this;}
  mat&op*=(cons T&a){foe(v,m)v*=a;rt*this;}
  mat&op/=(cons T&a){foe(v,m)v/=a;rt*this;}
  mat op+(cons T&a)cons{rt mat(*this)+=a;}
  mat op-(cons T&a)cons{rt mat(*this)-=a;}
  mat op*(cons T&a)cons{rt mat(*this)*=a;}
  mat op/(cons T&a)cons{rt mat(*this)/=a;}
  
  mat pow(ll n){
    as(h==w);
    mat x=*this;
    mat r(h);rep(i,h)r[i][i]=1;
    wh(n){
      if(n&1)r*=x;
      x*=x;
      n/=2;
    }
    rt r;
  }
  
  void trs(){
    mat m2(w,h);
    rep(i,h)rep(j,w)m2[j][i]=m[i][j];
    *this=m2;
  }
  
  friend is&op>>(is&i,mat&m){rt i>>m.m;}
  friend os&op<<(os&o,cons mat&m){rt o<<m.m;}
};

int main(){
  LL(N);
  
  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.trs();
  a=a.pow(N);
  a*=v;
  pt(a[4][0]);
}

yukicoder

結果

テストケース

ソースコード