Entries
Source
Codeforces Beta Round #93 DIV1 D問題 (2000pt)
Problem description
問題概要
フィボナッチ数とは
1, 2, 3, 5, 8, 13, ...
である.
正整数n (10^18以下) が与えられた時,それを異なるフィボナッチ数の和で書く方法は何通りあるかを求める問題.
テストケースの数は10^5以下.
解法
DP.
とりあえず,与えられた整数をフィボナッチ進数みたいなので適当に書いた表記を計算する.
19 = 1*13 + 0*8 + 1*5 + 0*3 + 0*2 + 1*1 = 101001(fib)
みたいなの.とりあえず,自分以下の最も大きいフィボナッチ数で引いていくことで得られる.
連続する2つの1を消し,その一つ上の桁に1を加える.
1を消し,1つ下と2つ下の桁に1ずつ加える.
という操作ができるので,適当に,上の桁から確定するとして,今何桁目かと,次の桁と次の次の桁の値を状態にしてDPする.
ある桁の値が3以上になる,-2以下になるなどしたら,それより下の桁で調整できないので,そういう状態遷移は行わない.
C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
int n;
ll fib[100];
ll dp[98][4][4];
char g[98];
ll solve(int depth, int now, int next){
int i,j,k;
ll res = 0;
int a, b, c;
if(depth==1 && now==1 && next==1) return 1;
if(depth==1) return 0;
if(dp[depth][now][next] >= 0) return dp[depth][now][next];
a = g[depth] + (now-1);
b = g[depth-1] + (next-1);
c = g[depth-2];
if(a==0 || a==1){
res += solve(depth-1, next, 1);
}
if(a==0 && b!=-1){
res += solve(depth-1, next-1, 0);
}
if( (a==1 || a==2) && b!=2 ){
res += solve(depth-1, next+1, 2);
}
return dp[depth][now][next] = res;
}
int main(){
int i,j,k,l,m,n;
ll in, res;
int size;
fib[0]=1;
fib[1]=2;
REP(i,2,100){
fib[i]=fib[i-1]+fib[i-2];
if(fib[i]>1000000000000000000LL){
n = i;
break;
}
}
scanf("%d",&size);
while(size--){
scanf("%I64d",&in);
rep(i,n+2) rep(j,4) rep(k,4) dp[i][j][k] = -1;
for(i=n-1;i>=0;i--){
g[i+2] = 0;
if(in >= fib[i]) in -= fib[i], g[i+2]++;
}
g[0] = g[1] = 0;
res = solve(n+1, 1, 1);
printf("%I64d\n",res);
}
return 0;
}
コメント
コメントの投稿
トラックバック
- トラックバック URL
- http://rsujskf.blog32.fc2.com/tb.php/2152-c1fadf1a
- この記事にトラックバックする(FC2ブログユーザー)