結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー | Tqk |
提出日時 | 2019-09-20 23:18:49 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 2 ms
5,376 KB |
testcase_41 | AC | 2 ms
5,376 KB |
コンパイルメッセージ
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); } #endif using mi=mint<>; //P class 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_7 const 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