BZOJ3287 Mato刷屏计划

program bzoj3287;
 
const tpi=extended(2*3.14159265358979323846264);
      maxlen=270017;
      maxdig=270017;
      base=10000;
      ulen=4;
      s0='0000';
 
type compnum=record x,y:extended; end;
     poly=array[0..maxlen] of compnum;
     int=array[0..maxdig] of int64;
 
const f0:array[1..$f] of longint=(
        1,2,3,4,5,6,9,12,16,20,27,36,48,64,81
      );
 
var n,l,e,r:longint;
    a,b,c,t:int;
    ta,tb,tc:poly;
    tmp:array[0..maxdig] of int64;
 
function max(i,j:longint):longint; begin
if i>j then exit(i) else exit(j);  end;
 
function add(a,b:compnum):compnum; inline;      begin
add.x:=a.x+b.x; add.y:=a.y+b.y;                 end;
 
function sub(a,b:compnum):compnum; inline;      begin
sub.x:=a.x-b.x; sub.y:=a.y-b.y;                 end;
 
function mul(a,b:compnum):compnum; inline;              begin
mul.x:=(a.x*b.x-a.y*b.y); mul.y:=(a.x*b.y+b.x*a.y);     end;
 
procedure fft_init(m:longint);
begin
l:=0; n:=1; while n<m<<1 do begin
        inc(l); n:=n<<1;
end;
end;
 
procedure bit_rev(var a:poly);
var i,j,u,v:longint;
    t:compnum;
begin
for i:=0 to n-1 do begin
        u:=0; v:=i; for j:=1 to l do begin
                u:=(u<<1)or(v and 1); v:=v>>1;
        end; if u<i then begin
                t:=a[u]; a[u]:=a[i]; a[i]:=t;
        end;
end;
end;
 
procedure dft(var a:poly);
var i,j,k,m:longint;
    w,wm,u,v:compnum;
begin
bit_rev(a); for i:=1 to l do begin m:=1<<i;
        wm.x:=cos(tpi/m); wm.y:=sin(tpi/m);
        j:=0; while j<n do begin
                w.x:=1; w.y:=0; for k:=0 to m>>1-1 do begin
                        u:=a[j+k];              v:=mul(w,a[j+k+m>>1]);
                        a[j+k]:=add(u,v);       a[j+k+m>>1]:=sub(u,v);
                        w:=mul(w,wm);
                end; inc(j,m);
        end;
end;
end;
 
procedure idft(var a:poly);
var i,j,k,m:longint;
    w,wm,u,v:compnum;
begin
bit_rev(a); for i:=1 to l do begin m:=1<<i;
        wm.x:=cos(tpi/m); wm.y:=-sin(tpi/m);
        j:=0; while j<n do begin
                w.x:=1; w.y:=0; for k:=0 to m>>1-1 do begin
                        u:=a[j+k];              v:=mul(w,a[j+k+m>>1]);
                        a[j+k]:=add(u,v);       a[j+k+m>>1]:=sub(u,v);
                        w:=mul(w,wm);
                end; inc(j,m);
        end;
end; for i:=0 to n-1 do a[i].x:=a[i].x/n;
end;
 
procedure convolution(var a,b,c:poly);
var i:longint;
begin
dft(a); dft(b); for i:=0 to n-1 do c[i]:=mul(a[i],b[i]); idft(c);
end;
 
procedure mulbrute(var a,b,c:int);
var i,j:longint;
begin
fillchar(c,(a[0]+b[0])<<4,0); c[0]:=a[0]+b[0]-1;
for i:=1 to a[0] do for j:=1 to b[0] do begin
        inc(c[i+j-1],a[i]*b[j]); inc(c[i+j],c[i+j-1] div base); c[i+j-1]:=c[i+j-1] mod base;
end; if c[c[0]+1]<>0 then inc(c[0]);
end;
 
procedure mul(var a,b,c:int);
var i:longint;
begin
if max(a[0],b[0])<200 then begin mulbrute(a,b,c); exit; end;
fft_init(max(a[0],b[0])); for i:=0 to n-1 do begin
        ta[i].x:=a[i+1]; ta[i].y:=0;
        tb[i].x:=b[i+1]; tb[i].y:=0;
end; convolution(ta,tb,tc); c[0]:=n;
for i:=0 to n-1 do c[i+1]:=round(tc[i].x);
for i:=1 to n do begin
        inc(c[i+1],c[i] div base); c[i]:=c[i] mod base;
end; while c[c[0]+1]>=base do begin
        inc(c[0]); c[c[0]+1]:=c[0] div base; c[c[0]]:=c[c[0]] mod base;
end; while c[c[0]]=0 do dec(c[0]);
end;
 
procedure mul(var a:int;b:longint;var c:int);
var i:longint;
begin
fillchar(c,sizeof(c),0); c[0]:=a[0]+40;
for i:=1 to c[0] do begin
        inc(c[i],a[i]*b); inc(c[i+1],c[i] div base); c[i]:=c[i] mod base;
end; while c[c[0]]=0 do dec(c[0]);
end;
 
procedure print(var a:int);
var i,j,k:longint;
    s:string[ulen];
begin
write(a[a[0]]); for i:=a[0]-1 downto 1 do begin
        k:=ulen; j:=a[i]; s:=s0; while j>0 do begin
                s[k]:=chr(j mod 10+48); j:=j div 10; dec(k);
        end; write(s);
end; writeln;
end;
 
procedure exp(var a:int;n:longint;var b:int);
begin
fillchar(b,sizeof(b),0); b[0]:=1; b[1]:=1;
while n>1 do begin
        if n and 1 = 1 then begin mul(a,b,t); b:=t; end;
        mul(a,a,t); a:=t; n:=n>>1;
end; mul(a,b,t); b:=t;
end;
 
procedure work;
var i,j:longint;
begin
readln(n);
if n<16 then begin writeln(f0[n]); exit; end;
e:=(n-15)div 5+byte((n-15)mod 5>0); r:=n-5*e;
a[0]:=1; a[1]:=4; exp(a,e,b);
mul(b,f0[r],c); print(c);
end;
 
begin
work;
end.