結果
| 問題 | No.194 フィボナッチ数列の理解(1) |
| ユーザー |
 nikollson
|
| 提出日時 | 2015-04-28 21:14:01 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 2,146 bytes |
| コンパイル時間 | 767 ms |
| コンパイル使用メモリ | 80,912 KB |
| 実行使用メモリ | 8,576 KB |
| 最終ジャッジ日時 | 2024-07-05 05:06:17 |
| 合計ジャッジ時間 | 7,255 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
コンパイルメッセージ
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
ソースコード
#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 && false){
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 += sum;
b.pb(next);
ll front = b[0];
b.pop_front();
sum = (sum + next - front + MOD)%MOD;
}
ansF = b[n-1];
ansS = allsum;
}
cout<<ansF<<" "<<ansS<<endl;
}
/*
3 6
1 1 1
5 8
1 2 3 4 5
*/