按照题意打表 1e9 一定超时，所以一定存在规律，将上述公式化简为 f(n)=f(n-2)+3*n*(n-1)+1 后进行打表，找到循环节之后，问题就解决了
const int N=1e5+5; const ll mod=2009; int n,m,t; int i,j,k; int a[N]; ll dp[N],cur; void init() { dp[1]=1; dp[2]=7; for(i=3;i<=100000;i++){ k=i%mod; dp[i]=(dp[i-2]+3*k*(k-1)+1)%mod; //根据模运算性质，防止爆 int if(dp[i]==7 && dp[i-1]==1){ cur=i-2; //循环节 break; } } } int main() { IOS; init(); while(cin>>n,n){ cout<<dp[n%cur]<<endl; } //PAUSE; return 0; }
