結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー nikollsonnikollson
提出日時 2015-04-28 21:24:20
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 2,197 bytes
コンパイル時間 880 ms
コンパイル使用メモリ 83,564 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-05 05:06:33
合計ジャッジ時間 2,044 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void print(P&)’:
main.cpp:95:34: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
   95 |                         printf("%d ",a[i][j]);
      |                                 ~^
      |                                  |
      |                                  int
      |                                 %lld
main.cpp: In function ‘void print(V&)’:
main.cpp:101:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’} [-Wformat=]
  101 |                 printf("%d ",a[i]);
      |                         ~^
      |                          |
      |                          int
      |                         %lld

ソースコード

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

#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<deque>
#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)
#define pb push_back
using namespace std;
#ifdef __BORLANDC__
typedef __int64 ll;
#else
typedef long long ll;
#endif
const ll MOD = 1000000007;
class P:public vector<vector<ll> >{
public:
P(int n){
rep(i,n){
vector<ll> dat(n);
this->pb(dat);
}
}
};
class V:public vector<ll>{
public:
V(int n){
rep(i,n)this->pb(0);
}
};
P multi(P& a, P& b){
int n = a.size();
P ret(n);
rep(i,n){
rep(j,n){
int num = 0;
rep(k,n){
num = (num+a[i][k]*b[k][j])%MOD;
}
ret[i][j] = num;
}
}
return ret;
}
V multi(P& a, V& b){
int n = a.size();
V ret(n);
rep(i,n){
int num = 0;
rep(j,n){
num = (num+a[i][j]*b[j])%MOD;
}
ret[i] = num;
}
return ret;
}
P getP(int n){
P ret(n+1);
rep(i,n-1){
rep(j,n){
if(j-1==i)ret[i][j]=1;
else ret[i][j] = 0;
}
}
rep(i,n)ret[n-1][i]=1;
rep(i,n)ret[i][n]=0;
rep(i,n+1)ret[n][i]=1;
return ret;
}
void print(P& a){
rep(i,a.size()){
rep(j,a.size()){
printf("%d ",a[i][j]);
}puts("");
}
}
void print(V& a){
rep(i,a.size()){
printf("%d ",a[i]);
}puts("");
}
int main(){
ll n,k;
cin>>n>>k;
vector<ll> a(n);
rep(i,n)cin>>a[i];
ll ansF = -1;
ll ansS = -1;
if(n<=30){
const int T = 50;
vector<P> b;
b.pb(getP(n));
reps(i,1,T){
b.pb(multi(b[i-1], b[i-1]));
}
V vec(n+1);
rep(i,n)vec[i] = a[i];
rep(i,n)vec[n] = (vec[n]+a[i])%MOD;
ll tk = k-n;
ll sc = 1;
rep(i,T){
if((tk&sc)>0){
vec = multi(b[i], vec);
}
sc*=2;
}
ansF = vec[n-1];
ansS = vec[n];
}else{
deque<ll> b;
rep(i,n)b.pb(a[i]);
ll sum = 0;
rep(i,n)sum += b[i];
ll allsum = sum;
rep(i,k-n){
ll next = sum;
allsum = (allsum+sum)%MOD;
ll front = b[0];
sum = (sum + next - front + MOD)%MOD;
//rep(j,b.size())cout<<b[j]<<" ";cout<<endl;
b.pop_front();
b.pb(next);
}
ansF = b[n-1];
ansS = allsum;
}
cout<<ansF<<" "<<ansS<<endl;
}
/*
3 6
1 1 1
5 8
1 2 3 4 5
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0