/*设f[i]表示长度为i的以0结尾的合法队列个数 *设g[i]表示长度为i的以1结尾的合法队列个数 *显然有 *f[i]=f[i-1]+g[i-1]; (1) *g[i]=f[i-1]; (2) *(2)代入(1)即 *f[i]=f[i-1]+f[i-2]; *最终合法队列总个数为f[n]+g[n]即f[n]+f[n-1]=f[n+1] *即求斐波那契数列的第n+1项 *1,2,3,5,8,13,21.............*/ #include<cstdio> using namespace std; long long f[47]={1,1}; int main() { int n,i,temp; for (i=2;i<=46;i++) f[i]=f[i-1]+f[i-2]; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&temp); if(f[0]==0) printf("Scenario #%d:/n0/n/n",i); else printf("Scenario #%d:/n%lld/n/n",i,f[temp+1]); } }
