NOIP2016全国信息学分区联赛提高组第二试 组合问题

组合问题(problem)
【问题描述】

【题解】

将这个“草稿”转一转，可以发现这是一个杨辉三角形，然后mod k，统计一下即可。

【代码】

var
  t,k,n,m:longint;
  f,a:array [0..2001,0..2001] of longint;
procedure try1;
var
  i,j:longint;
begin
  fillchar(a,sizeof(a),255);
  for i:=2 to 2000 do
    for j:=1 to i-1 do
      if (j=1) or (i-j=1) then a[i,j]:=i mod k
                          else a[i,j]:=(a[i-1,j-1]+a[i-1,j]) mod k;
end;

procedure try2;
var
  i,j:longint;
begin
  fillchar(f,sizeof(f),0);
  for i:=1 to 2000 do
    for j:=1 to 2000 do
      begin
        f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1];
        if a[i,j]=0 then
          f[i,j]:=f[i,j]+1;
      end;
end;

begin
  readln(t,k);
  try1;
  try2;
  while t>0 do
    begin
      readln(n,m);
      writeln(f[n,m]);
      dec(t);
    end;
end.