SPOJ 8 - Complete the Sequence![CMPLS]

张文泰 posted @ 2010年3月19日 03:39 in Art of Science with tags SPOJ 差分 , 5421 阅读

题目给出了一个数列的前若干项,要求推测后面的项。我们很容易想到拉格朗日插值法,但是精度就变成了一个大问题。这个问题虽然保证了所有的值都是整数,但是并没有保证其多项式的系数也是整数,因此在计算方面存在很大的困难。

除了插值法,求解这种数列问题我们有更好的差分方法,过程中完全不涉及浮点数操作。比如说,对于1 2 4 7 11 16 22 29这个数列,我们对于每一项做其和前一项的差,也就是2-1=1, 4-2=2, 7-4=3, ....这样,我们得到一个1阶差分:1, 2, 3, 4, 5, 6, 7。我们再求得2阶差分是:1, 1, 1, 1, 1, 1。这时,规律已经有些明显了。

也就是说,对于任意一个存在合理多项式通项的数列,用差分的方法是可以得到它的解的:只要求得这个n项数列的n-1阶差分,然后倒推回去就可以了。代码如下:

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 100+5;

int n,m,s[MAXN][MAXN];

int main() {
  int ncase;
  scanf("%d",&ncase);
  while (ncase--) {
    scanf("%d%d",&n,&m);
    for (int i = 0; i<n; i++)
      scanf("%d",&s[0][i]);
    for (int i = 1; i<n; i++)
      for (int j = 0; i+j<n; j++)
        s[i][j] = s[i-1][j+1]-s[i-1][j];
    for (int i = 1; i<=m; i++)
      s[n-1][i] = s[n-1][0];
    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];
    for (int i = 0; i<m-1; i++)
      printf("%d ",s[0][n+i]);
    printf("%d\n",s[0][n+m-1]);
  }
  return 0;
}

Your program in C++ from 2010-03-18 12:22:31 ran for 0.52 seconds and used 2576 KB of memory.


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License
lccycc 说:
2011年2月04日 10:36

拉格朗日了半天的泪流满面

Avatar_small
张文泰 说:
2011年4月17日 18:57

@lccycc: ...拉格朗日不靠谱


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter