結果
問題 | No.344 ある無理数の累乗 |
ユーザー |
|
提出日時 | 2023-07-18 00:24:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 6,883 bytes |
コンパイル時間 | 4,704 ms |
コンパイル使用メモリ | 264,476 KB |
最終ジャッジ日時 | 2025-02-15 15:29:53 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>#endifnamespace ttl{using namespace std;using f80=long double;using i64=int64_t;using u64=uint64_t;template<int mod> struct mymodint{i64 vl;static constexpr i64 get_mod(){ return mod; }i64 val(){ return vl; }mymodint(i64 vl_=0):vl((vl_%mod+mod)%mod){}mymodint operator-(){ return (vl==0)?0:mod-vl; }mymodint operator+(mymodint rhs){ return mymodint(*this)+=rhs; }mymodint operator-(mymodint rhs){ return mymodint(*this)-=rhs; }mymodint operator*(mymodint rhs){ return mymodint(*this)*=rhs; }mymodint operator/(mymodint rhs){ return mymodint(*this)/=rhs; }mymodint pow(i64 rhs){mymodint res=1,now=(*this);while(rhs){res*=((rhs&1)?now:1),now*=now,rhs>>=1;}return res;}mymodint& operator+=(mymodint rhs){vl+=rhs.vl,vl-=((vl>=mod)?mod:0);return (*this);}mymodint& operator-=(mymodint rhs){vl+=((vl<rhs.vl)?mod:0),vl-=rhs.vl;return (*this);}mymodint& operator*=(mymodint rhs){vl=vl*rhs.vl%mod;return (*this);}mymodint& operator/=(mymodint rhs){ return (*this)*=rhs.pow(mod-2); }bool operator==(mymodint rhs){ return vl==rhs.vl; }bool operator!=(mymodint rhs){ return vl!=rhs.vl; }};template<u64 mod> using modint=mymodint<mod>;template<int mod> std::ostream& operator<<(std::ostream& os,modint<mod> x){return os<<(x.val());}template<int mod> std::istream& operator>>(std::istream& is,modint<mod>& x){i64 t;is>>t,x=t;return is;}template<class T> void scn_(T& a){ cin>>a; }template<class T,class U> void scn_(pair<T,U>& a){ scn_(a.first),scn_(a.second); }template<class T> void scn_(vector<T>& a){for(auto& v:a){scn_(v);}}template<class T> void scn_(vector<vector<T>>& a){for(auto& v:a){for(auto& u:v){scn_(u);}}}void scn(){}template<class T,class... Args> void scn(T& n,Args&... args){ scn_(n),scn(args...); }template<class T> void prt_(T a){ cout<<a; }template<class T,class U> void prt_(pair<T,U> a){ cout<<"{"<<a.first<<", "<<a.second<<"}"; }void prt_(f80 a){ printf("%.15Lf",a); }template<class T> void prt(vector<T> a){for(size_t i=0;i<a.size();++i){prt_(a[i]);cout<<" \n"[i==a.size()-1];}}template<class T> void prt(vector<vector<T>> a){for(auto& v:a){for(size_t i=0;i<v.size();++i){prt_(v[i]);cout<<" \n"[i==v.size()-1];}}}template<class T> void prt(T a){ prt_(a),cout<<"\n"; }template<class T,class... Args> void prt(T a,Args... args){ prt_(a),cout<<" ",prt(args...); }template<class Head,class... Tail> struct multi_dim_vector{ using type=vector<typename multi_dim_vector<Tail...>::type>; };template<class T> struct multi_dim_vector<T>{ using type=T; };template<class T,class Arg> vector<T> mvec(int n,Arg&& arg){ return vector<T>(n,arg); }template<class T,class... Args> class multi_dim_vector<Args...,T>::type mvec(int n,Args&&... args){return typename multi_dim_vector<Args...,T>::type(n,mvec<T>(args...));}template<class T> void rev(T& a){ reverse(a.begin(),a.end());}template<class T> void srt(T& a){ sort(a.begin(),a.end()); }template<class T> void rsrt(T& a){ sort(a.rbegin(),a.rend()); }template<class T> T revd(T a){reverse(a.begin(),a.end());return a;}template<class T> T srtd(T a){sort(a.begin(),a.end());return a;}template<class T> T rsrtd(T a){sort(a.rbegin(),a.rend());return a;}template<class T> void chmx(T& a,T b){ a=max(a,b); }template<class T> void chmn(T& a,T b){ a=min(a,b); }i64 pw(i64 a,i64 n){i64 res=1;while(n){if(n&1){ res*=a; }a*=a;n/=2;}return res;}template<class T> void zip(vector<T>& a){auto b=srtd(a);b.erase(unique(b.begin(),b.end()),b.end());map<T,int> mp;for(int i=0;i<b.size();++i){mp[b[i]]=i;}for(auto& v:a){v=mp[v];}}template<class T> auto runlng(T a) -> vector<pair<typename decltype(a)::value_type,i64>>{int n=a.size();vector<pair<typename decltype(a)::value_type,i64>> res;if(n==0){ return res; }typename decltype(a)::value_type now=a[0];i64 l=1;for(int i=1;i<n;++i){if(a[i-1]==a[i]){ l++; }else{res.emplace_back(now,l);now=a[i],l=1;}}res.emplace_back(now,l);return res;}template<class T> struct cmb{vector<T> fac,ifac;cmb(int mx=3000000):fac(mx+1,1),ifac(mx+1,1){for(int i=1;i<=mx;++i){ fac[i]=fac[i-1]*i; }ifac[mx]/=fac[mx];for(int i=mx;i>0;--i){ ifac[i-1]=ifac[i]*i; }}T operator()(i64 n,i64 k){if(n<0||k<0||n<k){ return 0; }return fac[n]*ifac[k]*ifac[n-k];}T f(i64 n){return n<0?T(0):fac[n];}T fi(i64 n){return n<0?T(0):ifac[n];}};}using namespace ttl;template<class T> T Identity(int n){T res(n,n);for(int i=0;i<n;++i){res[i][i]=1;}return res;}template<class T> struct Matrix{vector<vector<T>> val;int height,width;Matrix(int H,int W,T init=0):val(H,vector<T> (W,init)),height(H),width(W){}Matrix(vector<vector<T>> val_):val(val_),height(val_.size()),width(val_[0].size()){}vector<T> &operator[](int i){return val[i];}Matrix operator+(Matrix rhs){return Matrix(*this)+=rhs;}Matrix operator*(Matrix rhs){return Matrix(*this)*=rhs;}Matrix operator+=(Matrix rhs){for(int i=0;i<rhs.height;++i){for(int j=0;j<rhs.width;++j){(*this)[i][j]+=rhs[i][j];}}return (*this);}Matrix operator*=(Matrix rhs){Matrix<T> res(height,rhs.width,0);for(int i=0;i<this->height;++i){for(int j=0;j<rhs.width;++j){for(int k=0;k<this->width;++k){res[i][j]+=(*this)[i][k]*rhs[k][j];}}}return (*this)=res;}Matrix pow(i64 k){int n=(*this).height;Matrix res=Identity<Matrix<T>>(n),now=(*this);while(k>0){if(k%2==1){res*=now;}now*=now;k/=2;}return res;}T det(){int N=height;int rnk=0;T cff=1;for(int j=0;j<N;++j){if(rnk==N){break;}for(int i=rnk;i<N;++i){if(val[i][j]!=0){T C=val[i][j];cff*=C;for(auto& v:val[i]){v/=C;}swap(val[rnk],val[i]);if(i!=rnk){ cff*=-1; }break;}}if(val[rnk][j]==0){return T(0);}for(int i=0;i<N;++i){if(i!=rnk && val[i][j]!=0){T C=val[i][j]/val[rnk][j];for(int k=0;k<N;++k){val[i][k]-=val[rnk][k]*C;}}}rnk++;}return cff;}};int main(){constexpr int mod=1000;using mint=mymodint<mod>;cmb<mint> Cb;int N;scn(N);if(N==0){ prt(1); return 0; }Matrix<mint> M=vector<vector<mint>>{{1,1},{3,1}};M=M.pow(N);prt(M[0][0]*2+(N%2?0:-1));}