#407645 (C++14) No.194 フィボナッチ数列の理解(1)

提出ソース

結果

問題	No.194 フィボナッチ数列の理解(1)
ユーザー	Red_Black_GPGPU
提出日時	2019-12-11 23:48:59
言語	C++14 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	7 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	4 ms 6,944 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	4 ms 6,944 KB
testcase_07	AC	5 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	5 ms 6,944 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	4 ms 6,940 KB
testcase_13	AC	3 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	6 ms 6,944 KB
testcase_16	AC	5 ms 6,940 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	5 ms 6,940 KB
testcase_19	AC	7 ms 6,944 KB
testcase_20	AC	12 ms 18,948 KB
testcase_21	AC	13 ms 19,020 KB
testcase_22	AC	12 ms 19,004 KB
testcase_23	AC	4 ms 6,944 KB
testcase_24	AC	8 ms 10,784 KB
testcase_25	AC	8 ms 10,028 KB
testcase_26	AC	8 ms 9,936 KB
testcase_27	AC	9 ms 11,764 KB
testcase_28	AC	4 ms 6,940 KB
testcase_29	AC	12 ms 17,556 KB
testcase_30	AC	7 ms 6,940 KB
testcase_31	AC	2 ms 6,944 KB
testcase_32	AC	4 ms 6,940 KB
testcase_33	AC	4 ms 6,940 KB
testcase_34	AC	4 ms 6,940 KB
testcase_35	AC	3 ms 6,940 KB
testcase_36	AC	6 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	6 ms 6,944 KB
testcase_39	AC	4 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード