結果
| 問題 | No.891 隣接3項間の漸化式 |
| ユーザー |
 Tqk
|
| 提出日時 | 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); }
#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