結果
| 問題 |
No.194 フィボナッチ数列の理解(1)
|
| コンテスト | |
| ユーザー |
 Red_Black_GPGPU
|
| 提出日時 | 2019-12-11 23:48:59 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 13 ms / 5,000 ms |
| コード長 | 6,330 bytes |
| コンパイル時間 | 1,759 ms |
| コンパイル使用メモリ | 176,264 KB |
| 実行使用メモリ | 19,020 KB |
| 最終ジャッジ日時 | 2024-06-24 08:07:59 |
| 合計ジャッジ時間 | 3,183 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
ll n,k,x,y;
class modint {
public:
long long value;
//+
const modint operator + (modint mtmp) const{
modint mdnt;
mdnt.value=(this->value+mtmp.value);
if (mdnt.value>=MOD)mdnt.value-=MOD;
return mdnt;
}
const modint operator + (long long ltmp) const{
modint mdnt;
long long tmp=ltmp%MOD;
if (tmp<0)tmp+=MOD;
mdnt.value=(this->value+tmp);
if (mdnt.value>=MOD)mdnt.value-=MOD;
return mdnt;
}
//-
const modint operator - (modint mtmp) const{
modint mdnt;
mdnt.value=(this->value-mtmp.value+MOD);
if (mdnt.value>=MOD)mdnt.value-=MOD;
return mdnt;
}
const modint operator - (long long ltmp) const{
modint mdnt;
long long tmp=ltmp%MOD;
if (tmp<0)tmp+=MOD;
mdnt.value=(this->value-tmp+MOD);
if (mdnt.value>=MOD)mdnt.value-=MOD;
return mdnt;
}
//*
const modint operator * (modint mtmp) const{
modint mdnt;
mdnt.value=(this->value*mtmp.value)%MOD;
return mdnt;
}
const modint operator * (long long ltmp) const{
modint mdnt;
long long ltmpm=ltmp%MOD;
if (ltmpm<0)ltmpm+=MOD;
mdnt.value=(this->value*ltmpm)%MOD;
return mdnt;
}
///
const modint operator / (long long ltmp) const{
modint mdnt;
long long ltmpm=ltmp%MOD;
if (ltmpm<0)ltmpm+=MOD;
long long mdnv=this->value;
long long x0=MOD,x1=ltmpm,x2,n0=0LL,n1=1LL,n2,t=mdnv%ltmpm,m,ans;
if (t==0){
mdnt.value=mdnv/ltmpm;
return mdnt;
}
for(int i=0;i<900;i++){
m=x0/x1;
x2=x0-x1*m;
n2=(n0-m*n1)%MOD;
if (x2==1){
ans=(n2+MOD)%MOD;
break;
}
x0=x1;x1=x2;
n0=n1;n1=n2;
}
mdnt.value=(mdnv+((t*ans)%MOD)*ltmpm-t)/ltmpm;
return mdnt;
}
const modint operator / (modint mtmp) const{
return (*this)/mtmp.value;
}
//%
const modint operator % (long long ltmp) const{
modint mdnt;
mdnt.value=(this->value%ltmp);
return mdnt;
}
//代入演算子のオーバーロード
modint &operator = (const modint mtmp)
{
this->value = mtmp.value;
return *this;
}
modint &operator = (const long long ltmp)
{
this->value = ltmp%MOD;
if ((this->value)<0)this->value+=MOD;
return *this;
}
//+=
modint &operator += (const modint mtmp)
{
this->value = (this->value+mtmp.value);
if (this->value>=MOD)this->value-=MOD;
return *this;
}
modint &operator += (long long ltmp)
{
long long tmp=ltmp%MOD;
if (tmp<0)tmp+=MOD;
this->value=(this->value+tmp);
if (this->value>=MOD)this->value-=MOD;
return *this;
}
//-=
modint &operator -= (const modint mtmp)
{
this->value = (this->value-mtmp.value+MOD);
if (this->value>=MOD)this->value-=MOD;
return *this;
}
modint &operator -= (long long ltmp)
{
long long tmp=ltmp%MOD;
if (tmp<0)tmp+=MOD;
this->value=(this->value-tmp+MOD);
if (this->value>=MOD)this->value-=MOD;
return *this;
}
//*=
modint &operator *= (const modint mtmp)
{
this->value = this->value*mtmp.value%MOD;
return *this;
}
modint &operator *= (long long ltmp)
{
this->value = this->value*(ltmp%MOD)%MOD;
if (this->value<0)this->value+=MOD;
return *this;
}
///=
modint &operator /= (const modint mtmp)
{
modint tmp=(*this)/mtmp.value;
this->value = tmp.value;
return *this;
}
modint &operator /= (long long ltmp)
{
modint tmp=(*this)/ltmp;
this->value = tmp.value;
return *this;
}
//%=
modint &operator %= (long long ltmp)
{
this->value%=ltmp;
return *this;
}
//exp関数
//aのn乗 mod c
modint exp(long long n){
long long ans=1LL,aa=this->value,beki=n;
for(int i=0;i<64;i++){
if (beki%2==1) ans=ans*aa%MOD;
aa=aa*aa%MOD;
beki/=2;
if (beki==0)break;
}
modint mdnt;
mdnt.value=ans;
return mdnt;
}
//friend ostream& operator << (ostream& os, const modint& m);
};
ostream& operator << (ostream& os, const modint& m)
{
os << m.value;
return os;
}
using vi = vector<modint>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
//行列累乗
void matmul(vvi &C,vvi A,vvi B)
{
int lpnm=A.size();
REP(i,lpnm){
REP(j,lpnm){
C[i][j]=0;
REP(l,lpnm){
C[i][j]=C[i][j]+A[l][j]*B[i][l];
}
}
}
}
void matpow(vvi &matans,vvi &imat,ll num){
int lpnm=imat.size();
vvi updmat(lpnm, vi(lpnm)); // k * k の正方行列
REP(i,lpnm) matans[i][i]=1;//単位行列 I
REP(i,lpnm)REP(j,lpnm)updmat[i][j]=imat[i][j];
while(num)
{
if (num%2==1)
{
matmul(matans,matans,updmat);
}
num/=2;
matmul(updmat,updmat,updmat);
}
return;
}
int main(){
modint ans;
ans=0;
cin >> n >> k;
vi a(n);
REP(i,n){
ll x;
cin>>x;
a[i]=x;
}
if (k<=1000000){
vi f(k),s(k);
REP(i,n)
{
f[i]=a[i];
if (i!=0){
s[i]=s[i-1]+f[i];
}else{
s[0]=f[0];
}
}
REP(i,n)
f[n]+=f[i];
s[n]=s[n-1]+f[n];
for (int i = n+1; i < k; i++)
{
f[i]=f[i-1]+(f[i-1]-f[i-1-n]);
s[i]=s[i-1]+f[i];
}
cout<<f[k-1]<<" "<<s[k-1]<<endl;
}else{
modint sm;sm=0;
REP(i,n-1)
sm+=a[i];
vvi mat2d(n+1, vi(n+1)); // k * k の正方行列
REP(i,n)
mat2d[i][0]=1;
REP(i,n-1)
mat2d[i][i+1]=1;
mat2d[n][n]=1;
mat2d[0][n]=1;
vvi ansmat(n+1, vi(n+1)); // k * k の正方行列
matpow(ansmat,mat2d,k-n);
REP(i,n){
ans+=ansmat[i][0]*a[n-1-i];
}
ans+=ansmat[n][0]*sm;
modint s;s=0;
REP(i,n){
s+=ansmat[i][n]*a[n-1-i];
}
s+=ansmat[n][n]*sm;
s+=ans;
cout<<ans<<" "<<s<<endl;
}
return 0;
}