题意：一个马在无限大的棋盘中跳，问跳n步能跳到多少个不同的格子。
首先写个打表程序打一下n比较小的时候的表：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,mod=;
const int dx[]= {-,-,,,,,-,-};
const int dy[]= {-,-,-,-,,,,};
typedef pair<int,int> P;
set<P> st[];
int n=,a[N];
int main() {
st[].insert({,});
for(int i=; i<n; ++i) {
for(P p:st[i&]) {
st[i&^].insert(p);
for(int j=; j<; ++j)st[i&^].insert({p.first+dx[j],p.second+dy[j]});
}
a[i]=st[i&].size();
}
for(int i=; i<n; ++i)printf("%d ",a[i]);
return ;
}
打印结果：
把元素差分两次后，成了这个亚子：
发现了什么？当n比较大的时候，经过二次差分后的数组的每一项都是28！因此可以猜测答案是一个关于n的二次多项式，现在要做的是把这个多项式推出来。
手算当然可以，但有没有一个可以不用动脑子就算出来的代码吗？答案是肯定的。拉格朗日插值大法好！
核心代码：(只需要写三个函数，前两个函数的作用是封装多项式的加法和乘法，第三个函数的作用是插值)
typedef double db;
typedef vector<db> Poly;
Poly operator*(Poly a,Poly b) {
Poly c;
c.resize(a.size()+b.size()-);
for(int i=; i<a.size(); ++i)
for(int j=; j<b.size(); ++j)c[i+j]+=a[i]*b[j];
return c;
}
Poly operator+(Poly a,Poly b) {
Poly c;
c.resize(max(a.size(),b.size()));
for(int i=; i<c.size(); ++i) {
if(i<a.size())c[i]+=a[i];
if(i<b.size())c[i]+=b[i];
}
return c;
}
Poly Lagrange(Poly X,Poly Y) {
Poly c;
int n=X.size();
for(int i=; i<n; ++i) {
Poly x({});
for(int j=; j<n; ++j)if(j!=i) {
x=x*Poly({-X[j],});
x=x*Poly({1.0/(X[i]-X[j])});
}
c=c+x*Poly({Y[i]});
}
return c;
}
这样一来，只要输入X向量和Y向量，就能直接求出原多项式了，非常方便。比如输入如下两个向量：
Poly a({,,}),b({,,});
Poly c=Lagrange(a,b);
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比较小的时候直接输出结果即可。最终提交上去的代码应该是这个亚子：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=+,inf=0x3f3f3f3f;
const int a[]= {,,,,,,,,,,};
int ka,n;
int main() {
int T;
for(scanf("%d",&T); T--;) {
printf("Case #%d: ",++ka);
scanf("%d",&n);
if(n<=)printf("%d\n",a[n]);
else printf("%llu\n",-(ll)*n+(ll)*n*n);
}
return ;
}
注意要用unsigned long long，OK了~
ps:如果对精度要求高的话，也可以用分数版的：
struct Frac {
int x,y;
Frac(int _x=,int _y=):x(_x),y(_y) {
int g=__gcd(x,y);
x/=g,y/=g;
if(y<)x=-x,y=-y;
}
Frac operator-() {return Frac(-x,y);}
Frac operator+(Frac b) {return Frac(x*b.y+y*b.x,y*b.y);}
Frac operator+=(Frac b) {return *this=(*this)+b;}
Frac operator-(Frac b) {return Frac(x*b.y-y*b.x,y*b.y);}
Frac operator-=(Frac b) {return *this=(*this)-b;}
Frac operator*(Frac b) {return Frac(x*b.x,y*b.y);}
Frac operator*=(Frac b) {return *this=(*this)*b;}
Frac operator/(Frac b) {return Frac(x*b.y,y*b.x);}
Frac operator/=(Frac b) {return *this=(*this)/b;}
};
typedef Frac db;
typedef vector<db> Poly;
Poly operator*(Poly a,Poly b) {
Poly c;
c.resize(a.size()+b.size()-);
for(int i=; i<a.size(); ++i)
for(int j=; j<b.size(); ++j)c[i+j]+=a[i]*b[j];
return c;
}
Poly operator+(Poly a,Poly b) {
Poly c;
c.resize(max(a.size(),b.size()));
for(int i=; i<c.size(); ++i) {
if(i<a.size())c[i]+=a[i];
if(i<b.size())c[i]+=b[i];
}
return c;
}
Poly Lagrange(Poly X,Poly Y) {
Poly c;
int n=X.size();
for(int i=; i<n; ++i) {
Poly x({Frac()});
for(int j=; j<n; ++j)if(j!=i) {
x=x*Poly({-X[j],Frac()});
x=x*Poly({Frac()/(X[i]-X[j])});
}
c=c+x*Poly({Y[i]});
}
return c;
}