题目大意：f[n]-n^3=f[n-2]-(n-1)^3 (n >=3),f[1]=1,f[2]=7,求f[n]。
题目思路：将n^3移到到等式右边化简的到：f[n]=f[n-2]+3n*(n-1)+1；
因为第n项与第n-2项有关，所以知道了f[1]与f[2]的值可以分奇偶打下表，找到循环节为4018。
#include<cstdio> #include<stdio.h> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 1000005 #define mod 1000000007 using namespace std; int v[MAX]; int main() { v[0]=0; v[1]=1; v[2]=7; int n,ans,num; for(n=3;n<=4018;n++)//打表 { if(n%2==0) { num=4；//从4开始 ans=0; while(num<=n) { int k=(num-2)/2; int a=(3*num)%2009; int b=(num-1)%2009; ans=(ans+((a*b)%2009+1)%2009)%2009; num+=2; } ans=(ans+7)%2009; } else { num=3;//从3开始 ans=0; while(num<=n) { int k=(num-2)/2; int a=(3*num)%2009; int b=(num-1)%2009; ans=(ans+((a*b)%2009+1)%2009)%2009; num+=2; } ans=(ans+1)%2009; } v[n]=ans; } while(scanf("%d",&n),n) { printf("%d\n",v[n%4018]); } return 0; }
原文：http://www.cnblogs.com/alan-W/p/5791630.html
