結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-04-20 10:57:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 5,938 bytes
コンパイル時間 1,862 ms
コンパイル使用メモリ 178,856 KB
実行使用メモリ 19,036 KB
最終ジャッジ日時 2024-09-25 08:17:38
合計ジャッジ時間 3,112 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};
template<class T>
struct Matrix{
vector<vector<T>> mat;
Matrix(const int h,const int w):
mat(h,vector<T>(w,0))
{}
Matrix(const vector<vector<T>> &G):
mat(G)
{}
int height() const{
return mat.size();
}
int width() const{
return mat[0].size();
}
//
const vector<T> &operator[](int i) const{
assert(0<=i&&i<(int)mat.size());
return mat[i];
}
vector<T> &operator[](int i){
assert(0<=i&&i<(int)mat.size());
return mat[i];
}
//
Matrix I(int n,T x){
Matrix ret(n,n);
for(int i=0;i<n;i++){
ret[i][i]=x;
}
return ret;
}
//
Matrix &operator +=(const Matrix &_mat){
int h=(*this).height(),w=(*this).width();
assert(h==_mat.height()&&w==_mat.width());
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
(*this)[y][x]+=_mat[y][x];
}
}
return (*this);
}
Matrix operator +(const Matrix &_mat) const{
return Matrix(*this)+=_mat;
}
//
Matrix &operator -=(const Matrix &_mat){
int h=(*this).height(),w=(*this).width();
assert(h==_mat.height()&&w==_mat.width());
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
(*this)[y][x]-=_mat[y][x];
}
}
return (*this);
}
Matrix operator -(const Matrix &_mat) const{
return Matrix(*this)-=_mat;
}
//
Matrix &operator *=(const Matrix &_mat){
int h=(*this).height(),w=(*this).width();
int _h=_mat.height(),_w=_mat.width();
assert(w==_h);
vector<vector<T>> ret(h,vector<T>(_w,0));
for(int y=0;y<h;y++){
for(int x=0;x<_w;x++){
for(int k=0;k<w;k++){
ret[y][x]+=(*this)[y][k]*_mat[k][x];
}
}
}
mat=ret;
return (*this);
}
Matrix operator *(const Matrix &_mat) const{
return Matrix(*this)*=_mat;
}
//
Matrix pow(long long k){
Matrix ret=I((*this).height(),1);
while(k>0){
if(k&1) ret*=(*this);
(*this)*=(*this);
k>>=1ll;
}
(*this)=ret;
return (*this);
}
void debug(){
int h=height(),w=width();
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
cout<<mat[y][x]<<(x==w-1?"\n":" ");
}
}
}
};
using int64 = int_fast64_t;
template<int64 MOD>
struct ModInt{
int64 x;
ModInt():x(0){}
ModInt(int64 x):
x(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD)
{}
//
ModInt operator -() const{
return ModInt(-x);
}
//
ModInt &operator +=(const ModInt &rhs){
x+=rhs.x;
if(x>=MOD) x-=MOD;
return (*this);
}
ModInt operator +(const ModInt &rhs) const{
return ModInt(*this)+=rhs;
}
//
ModInt &operator -=(const ModInt &rhs){
x+=MOD-rhs.x;
if(x>=MOD) x-=MOD;
return (*this);
}
ModInt operator -(const ModInt &rhs) const{
return ModInt(*this)-=rhs;
}
//
ModInt &operator *=(const ModInt &rhs){
x*=rhs.x;
if(x>=MOD) x%=MOD;
return (*this);
}
ModInt operator *(const ModInt &rhs) const{
return ModInt(*this)*=rhs;
}
//
ModInt &operator /=(const ModInt &rhs){
(*this)*=rhs.inverse();
return (*this);
}
ModInt operator /(const ModInt &rhs) const{
return ModInt(*this)/=rhs;
}
//
bool operator ==(const ModInt &rhs){
return x==rhs.x;
}
bool operator !=(const ModInt &rhs){
return x!=rhs.x;
}
//
ModInt pow(int64 n){
int64 tmp=x;
x=1;
while(n>0){
if(n&1) x=x*tmp%MOD;
tmp=tmp*tmp%MOD;
n>>=1ll;
}
return (*this);
}
//
ModInt inverse(){
int64 a=x,b=MOD,s=1,t=0;
while(b>0){
int64 u=b/a;
b-=u*a;
t-=u*s;
swap(a,b);
swap(s,t);
}
return ModInt(s);
}
//
friend istream &operator >>(istream &lhs,ModInt<MOD> &rhs){
int64 x; lhs>>x;
rhs=ModInt<MOD>(x);
return lhs;
}
friend ostream &operator <<(ostream &lhs,const ModInt<MOD> &rhs){
return lhs<<rhs.x;
}
};
int main(){
const int MOD=1e9+7;
using mint=ModInt<MOD>;
long long n,k; cin>>n>>k;
//
if(k<=n){
mint f,sum=0;
for(int i=1;i<=k;i++){
cin>>f;
sum+=f;
}
cout<<f<<" "<<sum<<endl;
return 0;
}
// 1
if(n>30){
mint f[k+1],s[k+1];
for(int i=1;i<=n;i++){
cin>>f[i];
s[i]=f[i]+s[i-1];
}
for(int i=n+1;i<=k;i++){
f[i]=s[i-1]-s[i-n-1];
s[i]=f[i]+s[i-1];
}
cout<<f[k]<<" "<<s[k]<<endl;
return 0;
}
// 2
mint f[n+1],s[n+1];
for(int i=1;i<=n;i++){
cin>>f[i];
s[i]=f[i]+s[i-1];
}
Matrix<mint> mat(n+1,n+1);
mat[0][0]=2;
mat[0][n]=-1;
for(int y=1;y<n+1;y++){
mat[y][y-1]=1;
}
mat.pow(k-n);
mint sk,sk1;
for(int x=0;x<n+1;x++){
sk+=mat[0][x]*s[n-x];
sk1+=mat[1][x]*s[n-x];
}
cout<<sk-sk1<<" "<<sk<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0