COJ 1082 Farmer John’s Cow

本来想水过的，结果提交了2次都是WA，就沉下心了；

类似fib数列，写出几项，可以猜测递推公式为f[n] = f[n-1] + 2×f[n-2]，稍加分析：正确；

稍作变形有：

1.  f[n] + f[n-1] = 2×(f[n-1] + f[n-2])

2.  f[n] - 2×f[n-1] = -(f[n-1] - 2×f[n-2])

所以可以求出 f[n]，这里使用第一个式子得到了f[n] + f[n-1] = 2^(n-1)，所以 f[n] = 2^(n-1) - f[n-1]，2的幂可以使用移位，没问题吧；

题目中0<n<65，所以这样做会遇到2^63，超出了long long int，当然使用第2个式子相加的话是不会溢出的，改用unsigned long long int，问题来了：这样改了再提交将仍然是WA；

问题出在移位运算上，实际上之前也碰到过了，这次又忘了：移位运算只限定在 int 型以内！，虽然没在书上看过，但这是实践的结论……

# include <stdio.h>
 
int main()
{
    int n;
    unsigned long long int t = 1, f[65];
 
    f[1] = 1;
    for(n = 1; n < 64; ++n) 
        f[n+1] = (t *= 2)-f[n];
 
    while (~scanf("%d", &n))
        printf("%llu\n", f[n]);
 
    return 0;
}