poj2094

很不错的一道题，很让我见识到了差分序列的运用的神奇之处。。一下是从北邮BBS看到的题解，写得很清楚。。这边就直接转过来。

uRLhttp://bbs.byr.cn/#!article/ACM_ICPC/33403

**********************************************************************

其实是挺简单的一个题目，希望大家都看看 
   
给出一个多项式p(x)=a[n]*x^n+...+a[1]*x+a[0],并给初始x值L,和数m,k，求出从x=L,L+1,...L+k-1的 p(x)的最后m个数字的平方和(有点绕),即，若p(x)=34，则输出3*3+4*4=25，x的值从L到L+k-1.且初始值l和多项式的常数 a[i]可能很大，最大到10^1000.多项式最高次最大为10，总时限10秒，case time limit 两秒 
   
最初看到这个题目以为是纯高精，敲了个java上去超时，自己写裸的高精，超时，写FFT乘法，超时(=_=!!),然后以为有递推关系，用二项式定理搞了个递推，再加上自己写了个100000000进制的高精，勉强把复杂度降到10的8次方，卡了半天常数过掉了。晚上仔细翻了下书，其实有更方便的方法。 
   
先简单科普下差分序列，大家应该都在组合数学课上见这个东西 
如果有序列 
a[1][1] a[1][2] a[1][3] ... a[1][n] 
则有 
a[i][j]=a[i-1][j+1]-a[i-1][j] 
   
比如这个差分表： 
1 4   13 34 73 
3 9   21 39 
6 12 18 
6 6 
0 
除了第一行外，它的每一项是它上面一行的相邻两个数之差 
   
若一个差分表的第一行是多项式p(x) p(x+1) p(x+2)...且多项式的次数为n，则这个差分表有下面的性质可以让我们利用： 
1.差分表在第n+1行后的所有元素均为0,第n行为一个常数. 
    简要说下证明思路，设第i阶差分序列为p[i](x),则第i+1阶序列为p[i+1](x)=p[i](x+1)-p[i](x),这也是个确定的多项式，且次数减一.递推到n阶的时候次数为0，即为一个常数.可知n+1行以后均为0 
2.若知道差分表的第一列的前n+1项，则可以确定这个多项式. 
    很明显，知道这些项后，可以逆推出第一行的前n+1项，通过解线性方程可以确定各项系数。 
比如前面给的那个差分表，对应的多项式是p(x)=x^3+2*x+1 
   
回到题目，到这里其实应该很容易看出，只要知道差分表的前n+1列，那么根据a[i][j]=a[i-1][j]+a[i-1][j-1],以后的所有元素都可以推出来。而计算这前n+1列，需要p(L),p(L+1)...p(L+n),因为n最多为10，所以可以很快用最挫的方法暴力求出来。 
而最初始的表建好后，对每一项p(x)，可以从下往上递推a[i][j]=a[i-1][j]+a[i-1][j-1]，需要实现的只是几个基本高精计算的函数，最后把需要的东西求出来即可。 
   
建初始表的复杂度最大为O(10*10*1000+10*10*1000)~O(10^5),之后递推的复杂度为O(1000*10*1000)~O(10^7),对于每个case两秒的时限已经基本足够了，刚才提交的时候所有case运行时间在两秒左右:-) 
   
话说这是有屎以来卡得我最久的一道题了...orz orz...  
********************************************************************************

*********************************************************************************

这里补充说一下，第i阶-->第i + 1阶为什么多项式会降阶

假设：p(x) = an*x^n + an-1 * x^(n-1).......a1*x + a0

对于第一阶: p(x)        p(x+1)     p(x+2)     p(x+3)...

对于第二阶：p(x+1)-p(x)   p(x+2)-p(x+1).....

设y = x + 1， 则会有：p（y）- p(x) = an*(y^n - x^n) + an-1 * (y ^ (n -1)  - x ^ (n - 1)))...........a1*（y - x） + 1 *（a0- a0） = an*(y^n - x^n) + an-1 * (y ^ (n -1)  - x ^ (n - 1)))........... + a2 * (y ^ 2 - x ^ 2)  + a1

那么，这样一来，最后一项便消掉（因为a0 - a0）， 所以a1就变成了常数。。

由此可知，每多一阶，多项式便降一阶（这样说好像不大准确，不过大概可以这样理解）

当然，最后一行为什么都是相等的常数，而且每一行都的系数的绝对值都符合杨辉三角（指的是p（x），p（x+1）...之前的系数）。

我太弱了，到现在还没理解，也不会证明，（跪求大神指教）

但是，把表打出来你会发现一个规律，当 最高次为x^1，x^2, x^3,...是，最后一行常数分别为1！，2！，3！.....

当然，这里是认为最高项系数为1的情况，当系数不为1，该常数还要乘以系数。。

不会java的渣渣只能写出这种code了。。

/*
 * Author:  yzcstc
 * Created Time:  2013/10/9 0:38:51
 * File Name: poj2094.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<utility>
#define M0(x) memset(x, 0, sizeof(x))
#define Inf 0x7fffffff
#define PB push_back
#define SZ(v) ((int)(v).size())
using namespace std;
int c[20010];
int n, k, m;
struct Biginteger{
       int d[20010], sz;
       void clr(){
            for (int i = 0; i <= sz; ++i)
               d[i] = 0;
            sz = 0;
       }
       void changenum(const char s[]){
              sz = strlen(s);
              for (int i = 1; i <= sz; ++i)
                  d[i] = s[sz - i] -'0';
       }
       void plus(const Biginteger & b){
            sz = max(sz, b.sz);
            if (sz > m) sz = m;
            int x = 0;
            for (int i = 1; i <= sz; ++i){
                x = x + d[i] + b.d[i];
                d[i] = x % 10;
                x /= 10;
            }
            while (sz < m && x) d[++sz] = x % 10, x /= 10;
       }
       void sub(const Biginteger & b){
            sz = max(sz, b.sz);
            if (sz > m) sz = m;
            int x = 0;
            for (int i = 1; i <= sz; ++i){
                x = d[i] - b.d[i] - x;
                d[i] = (x + 10) % 10;
                if (x < 0) x = 1;
                else x = 0;
            }
       }
       void multiply(const Biginteger & b){
            for (int i = 0; i <= sz + b.sz; ++i)
                 c[i] = 0;
            for (int i = 1; i <= sz; ++i)
                for (int j = 1; j <= b.sz; ++j)
                     c[i + j - 1] += d[i] * b.d[j];
            int x = 0;
            sz += b.sz;
            if (sz > m) sz = m;
            for (int i = 1; i <= sz; ++i){
                  x = x + c[i];
                  d[i] = x % 10;
                  x /= 10;
            }
            while (sz >= 1 && d[sz] == 0) --sz;
       }
} a[15], q[12][12], l, one, t;

char s[1200];

void init(){
    l.changenum(s);
    for (int i = 0; i <= n; ++i){
         scanf("%s", &s);
         a[i].changenum(s);
    }
}

void outans(const Biginteger & a){
      int ans = 0;
      for (int i = 1; i <= min(a.sz, m); ++i)
        ans += a.d[i] * a.d[i];
      printf("%d
", ans); 
}

void solve(){
      for (int i = 0; i <= min(n, k); ++i){
            t = a[0];
            for (int j = 1; j <= n; ++j){
                 t.multiply(l); 
                 t.plus(a[j]); 
            }
            q[n][i] = t;
            outans(t);
            l.plus(one);
      }
      if (k > n){
            for (int i = n - 1; i >= 0; --i)
               for (int j = 0; j <= i; ++j){
                  q[i][j] = q[i + 1][j + 1];
                  q[i][j].sub(q[i + 1][j]);    
               }
            for (int i = 1; i <= n; ++i)
               q[0][i] = q[0][0];
            int p = 1, rw1, rw2;  
            for (int i = n + 1; i < k; ++i){
                for (int j = 1; j <= n; ++j){
                   rw1 = (j + p) % (n + 1);
                   rw2 = (j + p - 1) % (n + 1);
                   q[j][rw1] = q[j][rw2];
                   q[j][rw1].plus(q[j - 1][rw2]);
                }
                outans(q[n][rw1]);
                l.plus(one);
                ++p;
            }
      }
}

int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    one.sz = one.d[1] = 1;
    while (scanf("%d%s%d%d", &n, &s, &k, &m) == 4){
         init();
         solve();
    }
    fclose(stdin); fclose(stdout);
    return 0;
}