AcWing 3506. 斐波那契之和
原题链接
简单
作者:
lyxcqupt
,
2024-04-09 14:31:23
,
所有人可见
,
阅读 12
注意不需要便利所有!!!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;
public class 小x的第一题 {
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader((System.in))));
static BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static List<Long> fib = new ArrayList<>();
static List<Long> sum = new ArrayList<>();
static int n;
static int ans = 0;//表示方案数目!
static long res = 0;//表示当前选取的那些斐波那契数的和
static int cnt = 2;
public static void main(String[] args) throws IOException{
n = getInt();
fib.add((long) 0);
fib.add((long) 1);
fib.add((long) 2);
sum.add((long) 0);
sum.add((long) 1);
sum.add((long) 3);
while(getfib(cnt) <= n) {
cnt++;
fib.add(getfib(cnt));
sum.add(sum.get(cnt-1) + fib.get(fib.size()-1));
}
dfs(cnt);
pw.println(ans);
pw.flush();
pw.close();
}
private static int getInt() throws IOException{
st.nextToken();
return (int)st.nval;
}
public static long getfib(long n) {
long[][] a = new long[][] {{1,1},{0,0}};
long[][] f = new long[][] {{0,1},{1,1}};
while(n != 0) {
if((n & 1) == 1) a = mul(a,f);
f = mul(f,f);
n >>= 1;
}
return a[0][0];
}
public static long[][] mul(long[][] a,long[][] b){
long[][] c = new long[2][2];
for(int i = 0;i < 2;i++) {
for(int j = 0;j < 2;j++) {
for(int k = 0;k < 2;k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]);
}
}
}
return c;
}
public static void dfs(int cnt) {
if(res + sum.get(cnt) < n) return;//剪枝!都选完前面的依然小,返回!
if(res > n) return;
if(cnt == 0) {
if(res == n) ans++;
return;
}
res += fib.get(cnt);//选择
dfs(cnt-1);
res -= fib.get(cnt);//不选择
dfs(cnt-1);
}
}