python蓝桥杯POJ-980 斐波那契数列问题求解

Question

问题描述
　　斐波那契串由下列规则生成：
　　F[0] = "0";
　　F[1] = "1";
　　F[n] = F[n-1] + F[n-2] （n≥2，+表示连接）
　　给出一个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。
输入格式
　　第一行一个数n。
　　第二行一个01串S。
输出格式
　　答案。
样例输入
96
10110101101101
样例输出
7540113804746346428
数据规模和约定
　　n≤263-1，子串长≤10000，答案≤263-1。

Answer 1

递归问题
python

def f(num):
  if num == 0 or num ==1:
    return num
  else:
    return f(num-1)+f(num-2)