思路：利用差分思想，计算有规律序列 参考博客： http://blog.csdn.net/wangjie_wang/article/details/9149683 http://rchardx.is-programmer.com/posts/16142.html
题外话，：拉格朗日插值法也是希望找出n个数背后的通项公式。 差分的意思就是指，前一个数减去后一个数。 比如题中序列 1 2 4 7 11 16 22.这是原始序列，称之为0阶差分， 用前一个数减去后一个数得到：1 2 3 4 5 6 ,这种操作进行一次，我们称之为1阶差分. 在一阶差分基础上再进行差分运算。 得到1 1 1 1 1 这是2阶差分 如此循环下去，进行n-1次，也就是计算n-1阶差分 通过差分定义（后面的数-前面的数）发现，i阶差分序列的个数等于i-1阶差分的数目减一。 等于 n-i。 n是原始序列，0阶差分序列的个数。 所以求差分的公式如下：
for(int i=0;i<n;i++){ scanf("%d",&s[0][i]); } // calculate the cha fen for(int i=1;i<n;i++){ for(int j=0;j<n-i;j++){ s[i][j]=s[i-1][j+1]-s[i-1][j]; } }对于n-1阶差分，由于只有一个数，而题目中要求求出后面的m个数。所以需要对n-1阶差分进行补齐操作。也就是n-1阶差分，是一个由相同数字组成的序列。
// make the same length of n-1 for(int i=1;i<=m;i++){ s[n-1][i]=s[n-1][0]; }最后进行倒推操作，求出0阶差分序列的m个数。 由于i阶差分已经有了n-i个数了，所以下面从n-i开始，接着求m个数
// because the i-th chafen has have n-i elements.so the start is n-i for(int i=n-2;i>=0;i--){ for(int j=0;j<m;j++){ s[i][n-i+j]=s[i][n-i+j-1]+s[i+1][n-i+j-1]; } }最后输出结果就好了。 AC代码：
#include <iostream> #include<cstdio> using namespace std; const int MAX=100+5; int s[MAX][MAX]; int main() { int t; scanf("%d",&t); int n,m; // n is the s , m is the c while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%d",&s[0][i]); } // calculate the cha fen for(int i=1;i<n;i++){ for(int j=0;j<n-i;j++){ s[i][j]=s[i-1][j+1]-s[i-1][j]; } } // make the same length of n-1 for(int i=1;i<=m;i++){ s[n-1][i]=s[n-1][0]; } // back up // because the i-th chafen has have n-i elements.so the start is n-i for(int i=n-2;i>=0;i--){ for(int j=0;j<m;j++){ s[i][n-i+j]=s[i][n-i+j-1]+s[i+1][n-i+j-1]; } } //output for(int i=0;i<m-1;i++){ printf("%d ",s[0][n+i]); } printf("%d\n",s[0][n+m-1]); } return 0; }