详情见:https://riteme.site/blog/2016-11-29/delta-and-stirling.html
注意:从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有关系了。
ZZ:https://blog.csdn.net/wu_tongtong/article/details/79115921
例题: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.
