Back Junアルゴリズム1788号:フィボナッチ数の拡張(失敗)
6888 ワード
リンク
( https://www.acmicpc.net/problem/1788 )
質問する
数学では,フィボナッチ数は上の点火式のように定義をまとめた数列である.上の式からも分かるように,フィボナッチ数F(n)は0より大きいnに対してのみ定義される.
しかし、フィボナッチ数F(n)をnが負の場合に拡張することもできる.上記式では、n>1の場合のみ成立するF(n)=F(n−1)+F(n−2)も、n<=1の場合に成立すると定義されている.例えば、n=1の場合、F(1)=F(0)+F(-1)が成立しなければならないので、F(-1)は1でなければならない.
nが与えられると,フィボナッチ数F(n)を求めるプログラムが記述される.nは負数であってもよい.
入力
最初の行はnです.nは、節価が1000000を超えない整数である.
しゅつりょく
1行目F(n)が正であれば1、0、0を出力し、負であれば−1を出力する.2行目はF(n)の節値を出力する.この数字は十分大きくなる可能性があるので、節電値を10000000に分けて余剰値を出力します.
入力と出力の例
プールコード（C++）
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <math.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define max 1000001
#define mod 1000000000
using namespace std;
int dp[max];
int main(){
fastio;
int n;
cin >> n;
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < max; i++){
dp[i] = (dp[i - 1]%mod + dp[i -2]%mod) % mod;
}
if(n%2 != 0){
printf("1\n");
}
else if(dp[-n] == 0){
printf("0\n");
}
else{
printf("-1\n");
}
printf("%d\n",abs(dp[-n]));
return 0;
}Reference
この問題について(Back Junアルゴリズム1788号:フィボナッチ数の拡張(失敗)), 我々は、より多くの情報をここで見つけました https://velog.io/@inwooleeme/백준-알고리즘-1788번-피보나치-수의-확장テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol