题意：一个马在无限大的棋盘中跳，问跳n步能跳到多少个不同的格子。
首先写个打表程序打一下n比较小的时候的表：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=50+10,mod=998244353; 5 const int dx[]= {-2,-1,1,2,2,1,-1,-2}; 6 const int dy[]= {-1,-2,-2,-1,1,2,2,1}; 7 typedef pair<int,int> P; 8 set<P> st[2]; 9 int n=20,a[N]; 10 int main() { 11 st[0].insert({0,0}); 12 for(int i=0; i<n; ++i) { 13 for(P p:st[i&1]) { 14 st[i&1^1].insert(p); 15 for(int j=0; j<8; ++j)st[i&1^1].insert({p.first+dx[j],p.second+dy[j]}); 16 } 17 a[i]=st[i&1].size(); 18 } 19 for(int i=0; i<n; ++i)printf("%d ",a[i]); 20 return 0; 21 }
打印结果：
1 9 41 109 205 325 473 649 853 1085 1345 1633 1949 2293 2665 3065 3493 3949 4433 4945
把元素差分两次后，成了这个亚子：
1 7 24 36 28 24 28 28 28 28 28 28 28 28 28 28 28 28 28 28
发现了什么？当n比较大的时候，经过二次差分后的数组的每一项都是28！因此可以猜测答案是一个关于n的二次多项式，现在要做的是把这个多项式推出来。
手算当然可以，但有没有一个可以不用动脑子就算出来的代码吗？答案是肯定的。拉格朗日插值大法好！
核心代码：(只需要写三个函数，前两个函数的作用是封装多项式的加法和乘法，第三个函数的作用是插值)
1 typedef double db; 2 typedef vector<db> Poly; 3 Poly operator*(Poly a,Poly b) { 4 Poly c; 5 c.resize(a.size()+b.size()-1); 6 for(int i=0; i<a.size(); ++i) 7 for(int j=0; j<b.size(); ++j)c[i+j]+=a[i]*b[j]; 8 return c; 9 } 10 Poly operator+(Poly a,Poly b) { 11 Poly c; 12 c.resize(max(a.size(),b.size())); 13 for(int i=0; i<c.size(); ++i) { 14 if(i<a.size())c[i]+=a[i]; 15 if(i<b.size())c[i]+=b[i]; 16 } 17 return c; 18 } 19 Poly Lagrange(Poly X,Poly Y) { 20 Poly c; 21 int n=X.size(); 22 for(int i=0; i<n; ++i) { 23 Poly x({1}); 24 for(int j=0; j<n; ++j)if(j!=i) { 25 x=x*Poly({-X[j],1}); 26 x=x*Poly({1.0/(X[i]-X[j])}); 27 } 28 c=c+x*Poly({Y[i]}); 29 } 30 return c; 31 }
这样一来，只要输入X向量和Y向量，就能直接求出原多项式了，非常方便。比如输入如下两个向量：
1 Poly a({1,2,3}),b({1,3,7}); 2 Poly c=Lagrange(a,b); 3 for(db x:c)printf("%f ",x);
输出的结果为
1.000000 -1.000000 1.000000
也就是说，三个点$(1,2),(2,3),(3,7)$所确定的多项式为$f(x)=x^2-x+1$
现在我们在打印的结果中任取三个点比如$(10,1345),(11,1633),(12,1949)$，得到的结果为：
5.000000 -6.000000 14.000000
即答案关于n的多项式为$f(n)=14n^2-6n+5$。当n比较大时的答案就可以通过这个式子算出来了，n比较小的时候直接输出结果即可。最终提交上去的代码应该是这个亚子：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned long long ll; 4 const int N=1000+10,inf=0x3f3f3f3f; 5 const int a[]= {1,9,41,109,205,325,473,649,853,1085,1345}; 6 int ka,n; 7 int main() { 8 int T; 9 for(scanf("%d",&T); T--;) { 10 printf("Case #%d: ",++ka); 11 scanf("%d",&n); 12 if(n<=10)printf("%d ",a[n]); 13 else printf("%llu ",5-(ll)6*n+(ll)14*n*n); 14 } 15 return 0; 16 }
注意要用unsigned long long，OK了~
ps:如果对精度要求高的话，也可以用分数版的：
1 struct Frac { 2 int x,y; 3 Frac(int _x=0,int _y=1):x(_x),y(_y) { 4 int g=__gcd(x,y); 5 x/=g,y/=g; 6 if(y<0)x=-x,y=-y; 7 } 8 Frac operator-() {return Frac(-x,y);} 9 Frac operator+(Frac b) {return Frac(x*b.y+y*b.x,y*b.y);} 10 Frac operator+=(Frac b) {return *this=(*this)+b;} 11 Frac operator-(Frac b) {return Frac(x*b.y-y*b.x,y*b.y);} 12 Frac operator-=(Frac b) {return *this=(*this)-b;} 13 Frac operator*(Frac b) {return Frac(x*b.x,y*b.y);} 14 Frac operator*=(Frac b) {return *this=(*this)*b;} 15 Frac operator/(Frac b) {return Frac(x*b.y,y*b.x);} 16 Frac operator/=(Frac b) {return *this=(*this)/b;} 17 }; 18 typedef Frac db; 19 typedef vector<db> Poly; 20 Poly operator*(Poly a,Poly b) { 21 Poly c; 22 c.resize(a.size()+b.size()-1); 23 for(int i=0; i<a.size(); ++i) 24 for(int j=0; j<b.size(); ++j)c[i+j]+=a[i]*b[j]; 25 return c; 26 } 27 Poly operator+(Poly a,Poly b) { 28 Poly c; 29 c.resize(max(a.size(),b.size())); 30 for(int i=0; i<c.size(); ++i) { 31 if(i<a.size())c[i]+=a[i]; 32 if(i<b.size())c[i]+=b[i]; 33 } 34 return c; 35 } 36 Poly Lagrange(Poly X,Poly Y) { 37 Poly c; 38 int n=X.size(); 39 for(int i=0; i<n; ++i) { 40 Poly x({Frac(1)}); 41 for(int j=0; j<n; ++j)if(j!=i) { 42 x=x*Poly({-X[j],Frac(1)}); 43 x=x*Poly({Frac(1)/(X[i]-X[j])}); 44 } 45 c=c+x*Poly({Y[i]}); 46 } 47 return c; 48 }