不少童鞋，得到了本题的递推关系：if(n&1) a[n]=2*a[n-1]-1;else a[n]=2*a[n-1]+1;这

牵涉到大数，如果用c或c++ dp上去的话，有可能会超时。我们可以耍一个小聪明。

把式子统一起来：a[n]=2*a[n-1]+(-1)^n。设它可以写成这样的形式:a[n]+k*(-1)^n=2*(

a[n-1]+k*(-1)^(n-1))，可以解的k=-1/3，所以a[n]-(-1)^n/3是一个等比数列，然后易得

a[n]=(2^(n-1)+(-1)^n)/3。n可以达到1000，所以对这么简单的式子，不用想，java！

注意多用一些shift操作。

• 好家伙， 从递推式得到通项公式 (0) tzkq 2010-07-13 08:37:54