差分序列

注意:从h0开始

例如求sigma(N^3),0<=N<=4,易知ans=100

因为表达式最高指数为3，所以第一行给出前4项，注意从h0开始

0 1 8 27 

1 7 19 

6 12 

6 

取第行第一个数字,一共是4行

ans=0*C(5,1)+1*C(5,2)+6*C(5,3)+6*C(5,4)=100

前N项和Sum=0*C(n+1,1)+1*C(n+1,2)+6*C(n+1,3)+6*C(n+1,4),于是整个算法只与N有关系了。

例题:Poj2515

求 1 + 2^m +3^m + 4^m +...+N^m

1 <= N <= 10 ^ 41 

3 <= M <= 100.

program ProblemB;

const
    inf =   '';
    ouf =   '';
    MaxK    =   101;
    maxLen  =   100;
    radix   =   10000;

type
    Bignum  =   array [ 0 .. MaxLen ] of longint;

var
    Com :   array [ 0 .. MaxK , 0 .. MaxK ] of Bignum;
    F   :   array [ 0 .. MaxK ] of Bignum;
    N   :   Bignum;
    K   :   longint;

procedure openFile;
    begin
    assign ( input , inf ) ; reset ( input );
    assign ( output , ouf ) ; rewrite ( output );
    end;

procedure closeFile;
    begin
    close ( input );
    close ( output );
    end;

procedure init;
    var
    s   :   string;
    ch  :   char;
    begin
    S := '' ; read ( ch );
    while ch <> ' ' do
    begin
        S := S + ch;
        read ( ch );
    end;
    readln ( K );

    fillchar ( N , sizeof ( N ) , 0 );
    while S <> '' do
    begin
        inc ( N [ 0 ] );
        if length ( S ) > 4 then
        begin
            val ( copy ( S , length ( S ) - 3 , 4 ) , N [ N [ 0 ] ] );
            delete ( S , length ( S ) - 3 , 4 );
        end else
        begin
            val ( S , N [ N [ 0 ] ] );
            S := '';
        end;
    end;
    end;

function max ( a , b : longint ) : longint;
    begin
    if a > b then max := a else max := b;
    end;

procedure add ( var A , B , C : Bignum );
    var
    i , x   :   longint;
    tmp :   Bignum;
    begin
    fillchar ( tmp , sizeof ( tmp ) , 0 );
    tmp [ 0 ] := max ( A [ 0 ] , B [ 0 ] ) + 1 ; x := 0;
    for i := 1 to tmp [ 0 ] do
    begin
        x := A [ i ] + B [ i ] + x div radix;
        tmp [ i ] := x mod radix;
    end;
    C := tmp;
    while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure sub ( var A , B , C : Bignum );
    var
    i , x   :   longint;
    tmp :   Bignum;
    begin
    fillchar ( tmp , sizeof ( tmp ) , 0 );
    tmp [ 0 ] := A [ 0 ] ; x := 0;
    for i := 1 to tmp [ 0 ] do
    begin
        x := A [ i ] - B [ i ] + x + radix;
        tmp [ i ] := x mod radix;
        x := x div radix - 1;
    end;
    C := tmp;
    while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure mul ( var A , B , C : Bignum );
    var
    i , j , x   :   longint;
    tmp     :   Bignum;
    begin
    fillchar ( tmp , sizeof ( tmp ) , 0 );
    tmp [ 0 ] := A [ 0 ] + B [ 0 ];
    for i := 1 to A [ 0 ] do
    begin
        x := 0;
        for j := 1 to B [ 0 ] + 1 do
        begin
            x := A [ i ] * B [ j ] + tmp [ i + j - 1 ] + x div radix;
            tmp [ i + j - 1 ] := x mod radix;
        end;
    end;
    C := tmp;
    while ( C [ 0 ] > 1 ) and ( C [ C [ 0 ] ] = 0 ) do dec ( C [ 0 ] );
    end;

procedure divK ( var num : Bignum ; k : longint );
    var
    i , x   :   longint;
    begin
    x := 0;
    for i := num [ 0 ] downto 1 do
    begin
        x := x * radix + num [ i ];
        num [ i ] := x div k;
        x := x mod k;
    end;
    while ( num [ 0 ] > 1 ) and ( num [ num [ 0 ] ] = 0 ) do dec ( num [ 0 ] );
    end;

procedure prepare;
    var
    i , j   :   longint;
    begin
    fillchar ( Com , sizeof ( Com ) , 0 );
    for i := 0 to MaxK do
    begin
        Com [ i , 0 , 0 ] := 1;
        Com [ i , 0 , 1 ] := 1;
        for j := 1 to i do
            add ( Com [ i - 1 , j - 1 ] , Com [ i - 1 , j ] , Com [ i , j ] );
    end;
    end;

procedure Main; 
    var
    i , j   :   longint;
    one :   Bignum;
    N_  :   Bignum;
    pow :   Bignum;
    tmp :   Bignum;
    begin
    fillchar ( one , sizeof ( one ) , 0 );
    one [ 0 ] := 1 ; one [ 1 ] := 1;

    F [ 0 ] := N;
    add ( N , one , N_ );
    pow := N_;

    for i := 1 to K do
    begin
        mul ( pow , N_ , pow );
        sub ( pow , one , F [ i ] );

        for j := 0 to i - 1 do
        begin
            mul ( F [ j ] , Com [ i + 1 , j ] , tmp );
            sub ( F [ i ] , tmp , F [ i ] );
        end;

        divK ( F [ i ] , i + 1 );
    end;
    end;

function hex ( x : longint ) : string;
    var
    s   :   string;
    begin
    str ( x + radix , s );
    hex := copy ( s , 2 , 4 );
    end;

procedure out;
    var
    i   :   longint;
    answer  :   Bignum;
    begin
    answer := F [ K ];

    write ( answer [ answer [ 0 ] ] );
    for i := answer [ 0 ] - 1 downto 1 do
        write ( hex ( answer [ i ] ) );
    writeln;
    end;

var
    data    :   longint;

begin
    openFile;

    prepare;
    readln ( data );
    for data := 1 to data do
    begin
        init;
        Main;
        out;
    end;

    closeFile;
end.