LEM6 - BIRTHDAY

Tác giả: ladpro98

Ngôn ngữ: Pascal

program lem6;
uses    math,sysutils;
type    big=string;
const   maxn=1234;
        fi='';
var     sieve:array[1..maxn] of boolean;
        prime,a:array[1..maxn] of longint;
        n,sum,d,m:longint;
        res:big;
procedure input;
var     inp:text;
        i,j,c:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,m);
        for i:=1 to m do
        begin
                read(inp,c);
                inc(sum,c);
        end;
        close(inp);
end;

procedure init;
var     i,j:longint;
begin
        fillchar(sieve,sizeof(sieve),true);
        for i:=2 to maxn do
        begin
                if sieve[i] then
                begin
                        j:=i*i;
                        while j<=maxn do
                        begin
                                sieve[j]:=false;
                                inc(j,i);
                        end;
                end;
        end;
        for i:=2 to maxn do
        if sieve[i] then
        begin
                inc(d);
                prime[d]:=i;
        end;
end;

procedure up(n:longint);
var     i,t:longint;
begin
        for i:=1 to d do
        if prime[i]>n then break
        else
        begin
                t:=prime[i];
                while n>=t do
                begin
                        inc(a[i],n div t);
                        t:=t*prime[i];
                end;
        end;
end;

procedure down(n:longint);
var     i,t:longint;
begin
        for i:=1 to d do
        if prime[i]>n then break
        else
        begin
                t:=prime[i];
                while n>=t do
                begin
                        dec(a[i], n div t);
                        t:=t*prime[i];
                end;
        end;
end;

function mul(a:big; b:longint):big;
var     i,carry,s:longint;
        c:big;
begin
        c:='';
        carry:=0;
        for i:=length(a) downto 1 do
        begin
                s:=(ord(a[i])-48)*b+carry;
                carry:=s div 10;
                c:=chr(s mod 10+48)+c;
        end;
        if carry>0 then
        c:=inttostr(carry)+c;
        exit(c);
end;

function pow(x,i:longint):longint;
var     t:longint;
begin
        if i=1 then exit(x);
        t:=pow(x,i div 2);
        if odd(i) then
                exit(sqr(t)*x);
        exit(sqr(t));

end;

procedure process;
var     k,q,i,p:longint;
begin
        k:=m;
        q:=n-sum+1;
        if k>q then
        begin
                res:='0';
                exit;
        end;
        up(q);
        down(k);
        down(q-k);
        res:='1';
        for i:=1 to d do
        begin
                if a[i]=0 then continue;
                p:=pow(prime[i],a[i]);
                res:=mul(res,p);
        end;
end;

begin
        input;
        init;
        process;
        write(res);
end.

Download