背景 Background
母牛生小牛
描述 Description
设有一头小母牛，从出生第四年起每年生一头小母牛，按此规律，第N年时有几头母牛？
输入格式 Input Format
只有一行且只有一个正整数：n
输出格式 Output Format
只有一行且只有一个正整数：第n年时牛的数目。
样例输入 Sample Input
5
样例输出 Sample Output
3
哪位能帮忙看看啊！真道题好像用到高精度呢！！

#include<cstdio>
long long f[4],g[4];
int main()
{
int n;
long long ans=0;
scanf("%d",&n);
f[0]=1;
f[1]=f[2]=f[3]=0;
for (int i=1;i<=n;++i)
{
for (int j=0;j<4;++j)
g[j]=f[j];
f[0]=g[3];
for (int j=1;j<3;++j)
f[j]=g[j-1];
f[3]+=g[2];
}
for (int i=0;i<4;++i)
ans+=f[i];
printf("%I64d\n",ans);
}
(太弱求轻喷)

你都不说数据范围怎么知道要不要用高精度啊？

至于需不需要高精度嘛，这要看数据范围
数据范围大于200，就需要用高精度了，在递推版本上简单改一改就行了
至于n到了150000或更大时，就需要用矩阵乘法加速递推了
而当n大的到了下一个数量级的时候呢，矩阵乘法都太慢了，就需要用神犇说的PPT,FFT之类的算法了

C编译器无法通过cstdio。@wfwhl12

楼上@wfwhl12 和@4533大多数 两位犇不要再吵了，大家坐下来帮楼主想想既不超时又能承受大数据的算法吧

我是真·蒟蒻