ac1145.pas

来自「同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料」· PAS 代码 · 共 82 行

program tju1145;
const
  maxn=300;
  count:array[0..6]of byte=(1,2,2,1,1,1,1);
  base=100000;
type
  bignum=array[-1..60]of longint;
var
  ans:array[1..maxn]of bignum;
  rem:array[boolean,0..6]of bignum;
  n,i,j,k:longint;
  c:bignum;
procedure add(var a,b:bignum);
  var
    i:longint;
  begin
    if b[-1]>a[-1] then a[-1]:=b[-1];
    for i:=0 to a[-1] do begin
      inc(a[i+1],(a[i]+b[i]) div base);
      a[i]:=(a[i]+b[i]) mod base;
    end;
    if a[a[-1]+1]>0 then inc(a[-1]);
  end;
procedure mul(var a:bignum;b:longint);
  var
    i:longint;
  begin
    for i:=0 to a[-1] do
      a[i]:=a[i]*b;
    for i:=0 to a[-1] do begin
      inc(a[i+1],a[i] div base);
      a[i]:=a[i] mod base;
    end;
    if a[a[-1]+1]>0 then inc(a[-1]);
  end;
procedure divide(var a:bignum;b:longint);
  var
    i:longint;
  begin
    for i:=a[-1] downto 0 do begin
      inc(a[i-1],a[i] mod b*base);
      a[i]:=a[i] div b;
    end;
    while a[a[-1]]=0 do dec(a[-1]);
  end;
procedure out(a:bignum);
  var
    i:longint;
  begin
    write(a[a[-1]]);
    for i:=a[-1]-1 downto 0 do
      write(a[i] div 10000,a[i] div 1000 mod 10,a[i] div 100 mod 10,a[i] div 10 mod 10,a[i] mod 10);
    writeln;
  end;
begin
  rem[false,0,0]:=1;
  for n:=1 to maxn do begin
    //Multiples of 7 not containing the digit 7
    fillchar(rem[odd(n)],sizeof(rem[odd(n)]),0);
    for i:=0 to 6 do
      for j:=0 to 6 do
        for k:=1 to count[j] do
          add(rem[odd(n),(i*10+j) mod 7],rem[not odd(n),i]);
    ans[n]:=rem[odd(n),0];

    //Numbers containing the digit 7
    fillchar(c,sizeof(c),0);c[0]:=1;
    for i:=1 to n do begin
      add(ans[n],c);//N-digit numbers containing (n+1-i) 7s
      if i<n then begin
        mul(c,(n+1-i)*9);
        divide(c,i);
      end;
    end;
  end;

  repeat
    read(n);
    out(ans[n]);
  until seekeof;
end.