题意:给你一个无限大的棋盘,一个象棋中的马,问你这个马,飞n步后,可能的位置有多少种?

题解:看到题,就想先打表试试,于是先写个暴力(枚举每个位置,是马就飞周围8个格子,注意不要在同个循环里把格子的标记涂成相同的数字)

         然后打出来是9 41 109 205 325 473 649 853

        对于这种增长不快的,我一般是先直接两项相减

        得到 32 68  96  120 148 176 204

        这时就看到,这个数列的增长越来越有趣? 后面都加的是28?

        于是对于n>=5,我们有 f[n]=f[n-1]+120+(n-5)*28 = f[n-1]+28*n-20

        这种递推式很明显的 解法 f[n]  = f[n-1]+28*n-20

                                                 f[n-1]= f[n-2]+28*(n-1)-20

                                                 f[5]=f[4]+28*(5)-20

        左右相加,再抵消.

        f[n]=28*(n+n-1+...+5)-20*(n-5+1)=f[4]+28*(n+5)*(n-4)/2-20*(n-4)=(14*(n+5)-20)*(n-4)+205 = (14*n+50)*(n-4)+205

1 #include
     
       2 using namespace std; 3 typedef unsigned long long ll; 4 int main() 5 { 6     int caseCnt; 7     scanf("%d",&caseCnt); 8     for(int t=1;t<=caseCnt;++t) { 9         ll n;10         scanf("%llu",&n);11         ll ans;12         if(n==0) ans=1;13         else if(n==1) ans=9;14         else if(n==2) ans=41;15         else if(n==3) ans=109;16         else if(n==4) ans=205;17         else {18             ans=(14*n+50)*(n-4)+205;19         }20         printf("Case #%d: %llu\n",t,ans);21     }22     return 0;23 }