結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-09-20 23:18:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 9,145 bytes |
コンパイル時間 | 2,097 ms |
コンパイル使用メモリ | 177,812 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 20:05:51 |
合計ジャッジ時間 | 3,065 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
コンパイルメッセージ
main.cpp:156:8: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 156 | mint<> operator""m(unsigned long long n){ return mint<>(n); } | ^~~~~~~~ main.cpp:157:17: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 157 | mint<998244353> operator""m9(unsigned long long n){ return mint<998244353>(n); } | ^~~~~~~~ main.cpp:158:15: warning: literal operator suffixes not preceded by '_' are reserved for future standardization [-Wliteral-suffix] 158 | mint<1000003> operator""m3(unsigned long long n){ return mint<1000003>(n); } | ^~~~~~~~
ソースコード
//#define _AOJ_/*vvv>zzzzzI.---. zzuzuI .vgggg&,.+++++= dAC:|I .WbbWo JMM9^```?TMB` ..&gNNg,. gggggggJ, qgggggggg] (&&&&&&&&[ c+OA&J, (&&&&&&+J, .cJeAA&-. (&&&&&&&&x .&AA&=-.+++++= dTqk|I Xpbpbp JM#` (M#^ ?MMp MM| +TMN. JMF ' |yk ` dVY 7Vk, Vy XV cVf ?Y! JM V$ `+++++= dcf:|I Xppppp dMN .MM+ .MM MM| MM] JMMMMMM+ |@tqkoh) ,y0 (V$ yyyyyyyV7 VV JMWyZWr TWVVVVW&,++++++ d7qk|0 Xppppp ^HMN, _.db WMm, .MMF MM| ..MM` JMF . |yk .WV&. .XW' yy 4yn. jyn +. JM #S`++++` ?ZZZX= ?WWWW= -THMMMMH9^ (TMMMMM9! MMMMMMM"" JMMMMMMMME |UU. ?TUUUUY= UU. (UU- ^7TUUUV7! JUUUUUUUU 7TUNKO*///Ricty Diminished#include "bits/stdc++.h"using namespace std;typedef long long lint;typedef vector<lint> liv;//#define rep(i,n) for(int i=0;i<n;++i)#define all(v) v.begin(),v.end()#define pb push_back#define _vcppunko4(tuple) _getname4 tuple#define _getname4(_1,_2,_3,_4,name,...) name#define _getname3(_1,_2,_3,name,...) name#define _trep2(tuple) _rep2 tuple#define _trep3(tuple) _rep3 tuple#define _trep4(tuple) _rep4 tuple#define _rep1(n) for(lint i=0;i<n;++i)#define _rep2(i,n) for(lint i=0;i<n;++i)#define _rep3(i,a,b) for(lint i=a;i<b;++i)#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)#define _trrep2(tuple) _rrep2 tuple#define _trrep3(tuple) _rrep3 tuple#define _trrep4(tuple) _rrep4 tuple#define _rrep1(n) for(lint i=n-1;i>=0;--i)#define _rrep2(i,n) for(lint i=n-1;i>=0;--i)#define _rrep3(i,a,b) for(lint i=b-1;i>=a;--i)#define _rrep4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)template<class T>istream& operator>>(istream& is,vector<T>& vec);template<class T,size_t size>istream& operator>>(istream& is,array<T,size>& vec);template<class T,class L>istream& operator>>(istream& is,pair<T,L>& p);template<class T>ostream& operator<<(ostream& os,vector<T>& vec);template<class T,class L>ostream& operator<<(ostream& os,pair<T,L>& p);template<class T>istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }template<class T,class L>istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }//template<class T>//ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }//template<class T>//ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }template<class T,class L>ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }inline void in(){}template <class Head,class... Tail>inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }template <class T>inline bool out(T t){ cout<<t<<'\n';return 0; }inline bool out(){ cout<<'\n';return 0; }template <class Head,class... Tail>inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))#define rrep(...) _vcppunko4((__VA_ARGS__,_trrep4,_trrep3,_trrep2,_rrep1))((__VA_ARGS__))#define each(v) for(auto &i:v)#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)#define vin(type,name,size) vector<type> name(size);in(name)#define fi e.first#define se e.second#define YES(c) cout<<((c)?"YES\n":"NO\n"),0#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0#define o(p) cout<<p<<endl,0#define sp(p) cout<<p<<" "#define no(p) cout<<p#ifdef __ENV_TQK__#define deb(p) cout<<p<<endl,0#else#define deb(p) 0#endif#define dd(n) cout<<fixed<<setprecision(n)//mint#define md_tmp template<uint_fast64_t md=1000000007>md_tmp class mint{using u64=uint_fast64_t;public:u64 a;constexpr mint(const u64 x=0) noexcept: a(x%md){}constexpr u64 &value() noexcept{ return a; }constexpr const u64 &value() const noexcept{ return a; }constexpr mint operator+(const mint rhs) const noexcept{return mint(*this)+=rhs;}constexpr mint operator-(const mint rhs) const noexcept{return mint(*this)-=rhs;}constexpr mint operator*(const mint rhs) const noexcept{return mint(*this)*=rhs;}constexpr mint operator^(const lint rhs) const noexcept{return mint(*this)^=rhs;}constexpr mint operator/(const mint rhs) const noexcept{return mint(*this)/=rhs;}constexpr mint &operator+=(const mint rhs) noexcept{a+=rhs.a;if(a>=md)a-=md;return *this;}constexpr mint &operator-=(const mint rhs) noexcept{if(a<rhs.a)a+=md;a-=rhs.a;return *this;}constexpr mint &operator*=(const mint rhs) noexcept{a=a*rhs.a%md;return *this;}constexpr mint &operator^=(const lint rhs) noexcept{if(!rhs)return *this=1;u64 exp=rhs-1;mint base=this->a;while(exp){if(exp&1)*this*=base;base*=base;exp>>=1;}return *this;}constexpr mint &operator/=(const mint rhs) noexcept{a=(*this*(rhs^(md-2))).a;return *this;}};md_tmp istream& operator>>(istream& os,mint<md>& m){os>>m.a,m.a%=md;return os;}md_tmp ostream& operator<<(ostream& os,const mint<md>& m){return os<<m.a;}md_tmp mint<md> ncr(lint n,lint r){if(n<r||n<0||r<0)return mint<md>(0);mint<md>ncr_res=1,ncr_div=1;rep(r)ncr_res*=(n-i),ncr_div*=(r-i);return ncr_res/ncr_div;}#ifndef _AOJ_mint<> operator""m(unsigned long long n){ return mint<>(n); }mint<998244353> operator""m9(unsigned long long n){ return mint<998244353>(n); }mint<1000003> operator""m3(unsigned long long n){ return mint<1000003>(n); }#endifusing mi=mint<>;//Pclass P{ public:lint f,s; constexpr P(lint a,lint b):f(a),s(b){};constexpr P():f(0),s(0){}; };istream& operator>>(istream& is,P& p){ is>>p.f>>p.s;return is; }ostream& operator<<(ostream& os,const P& p){ return os<<p.f<<" "<<p.s<<endl; }bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }struct C{ lint f,s,t; };bool operator<(const C& l,const C& r){ return l.t<r.t; }bool operator>(const C& l,const C& r){ return l.t>r.t; }#define linf 1152921504606846976#define inf linf//INT_MAX#define MAXN 200100#define md_1e9_7 1000000007#define md_998244353 998244353//#define mod md_1e9_7const int d4[5]={0,1,0,-1,0};template< class T >struct Matrix{vector< vector< T > > A;Matrix(){}Matrix(size_t n,size_t m): A(n,vector< T >(m,0)){}Matrix(size_t n): A(n,vector< T >(n,0)){};size_t height() const{return (A.size());}size_t width() const{return (A[0].size());}inline const vector< T > &operator[](int k) const{return (A.at(k));}inline vector< T > &operator[](int k){return (A.at(k));}static Matrix I(size_t n){Matrix mat(n);for(int i = 0; i < n; i++) mat[i][i] = 1;return (mat);}Matrix &operator+=(const Matrix &B){size_t n = height(),m = width();assert(n == B.height() && m == B.width());for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)(*this)[i][j] += B[i][j];return (*this);}Matrix &operator-=(const Matrix &B){size_t n = height(),m = width();assert(n == B.height() && m == B.width());for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)(*this)[i][j] -= B[i][j];return (*this);}Matrix &operator*=(const Matrix &B){size_t n = height(),m = B.width(),p = width();assert(p == B.height());vector< vector< T > > C(n,vector< T >(m,0));for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)for(int k = 0; k < p; k++)C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);A.swap(C);return (*this);}Matrix &operator^=(long long k){Matrix B = Matrix::I(height());while(k > 0){if(k & 1) B *= *this;*this *= *this;k >>= 1LL;}A.swap(B.A);return (*this);}Matrix operator+(const Matrix &B) const{return (Matrix(*this) += B);}Matrix operator-(const Matrix &B) const{return (Matrix(*this) -= B);}Matrix operator*(const Matrix &B) const{return (Matrix(*this) *= B);}Matrix operator^(const long long k) const{return (Matrix(*this) ^= k);}friend ostream &operator<<(ostream &os,Matrix &p){size_t n = p.height(),m = p.width();for(int i = 0; i < n; i++){os << "[";for(int j = 0; j < m; j++){os << p[i][j] << (j + 1 == m ? "]\n" : ",");}}return (os);}T determinant(){Matrix B(*this);assert(width() == height());T ret = 1;for(int i = 0; i < width(); i++){int idx = -1;for(int j = i; j < width(); j++){if(B[j][i] != 0) idx = j;}if(idx == -1) return (0);if(i != idx){ret *= -1;swap(B[i],B[idx]);}ret *= B[i][i];T vv = B[i][i];for(int j = 0; j < width(); j++){B[i][j] /= vv;}for(int j = i + 1; j < width(); j++){T a = B[j][i];for(int k = 0; k < width(); k++){B[j][k] -= B[i][k] * a;}}}return (ret);}};int main(){mint<> a,b;lint n; in(a,b,n);Matrix<mint<>> A;A.A={{a,1m},{b,0m}};if(n<=1)return o(n);o((A^(n-1))[0][0]);}//sub-EOF