题目叙述 n只小猫来到了freda 的城堡做客!freda很高兴,拿出了蛋糕和饼干来招待它们,每一 只小猫都可以吃到蛋糕或者饼干,当然,每只小猫具体拿到的是蛋糕还是饼干是由 freda决 定的. 小猫们看到蛋糕比饼干大之后,普遍认为蛋糕比饼干要好..所以,如果 freda给了第 i 只小猫蛋糕且这个小猫是第一个吃到蛋糕的,那么就必须给第 i+2,i+4,i+6......只小猫蛋 糕.也就是说,如果存在正整数 i,满足: 1,对于所有的 0 2,第 i只小猫吃到的是蛋糕 那么就必须有: 对于所有的 i 小猫的数目一多,freda就忙不过来了.请你帮忙计算,freda一共有多少种可能的方法来招 待这 n只小猫? 输入格式 一行一个整数 n表示小猫的数目. 输出格式 一行一个整数表示 freda可能招待这 n只小猫的方法数. 由于这个数可能很大,你只需要输出它 mod  的值. 输入样例 4 输出样例 10 样例解释 d 表示蛋糕,b表示饼干,freda 共有如下10种可能的招待方法. bbbb bbbd bbdb bbdd bdbd bddd dbdb dbdd dddb dddd 数据范围与约定 对于 30%的数据,n=20 对于 60%的数据,n= 对于 100%的数据,0 只考虑第一只喵喵吃饼干,有1种情况 第n只蛋糕:...bbbbbd 1 第n-1只蛋糕:...bbbbd* 1*2 n-2 :...bbbd*b 1*2 n-3 :...bbd*d* 1*2*2 n-4 :...bd*d*d 1*2*2 n-5 :...d*d*d* 1*2*2*2 ans=1+1+2+2+4+4+...+2^k ,因为有全吃饼干所以n+1项 [n+1为偶数时 ans=2*(1+2+4+...+2^k) 从2^0到2^k共(n+1)2项,用等比数列求和公式 ans=2*(1-2^((n+1)2))(1-2)=2^((n+3)2)-2 [n+1为奇数时 ans=2*(1+2+4+...+2^(k-1))+2^k 括号里共n2项包括2^0~2^(k-1)所以k-1=n2-1即k=n2 求和 ans=2*(2^(n2)-1)+2^(n2)=3*2^(n2)-2 [可爱的式子... f[n]:=f[n-1]+2^(n div 2) f[n-1]:=f[n-2]+2^((n-1) div 2) . . f[3]:=f[2]+2; f[2]:=f[1]+2; f[1]:=2; 这个学过等比数列的完全so easy... f nction k ai(x,y:int64):int64; var i,j:int64; begin i:=x; j:=y; if j then exit(k[j]); k ai:=k ai(i,j shr 1)*k ai(i,j-(j shr 1)) mod ; end;