【BZOJ4517】排列计数（排列组合）

题意：1-n的一个序列，其中有m个a[i]=i，求方案数

n,m<=1000000

题意：显然ANS=c(n,m)*d[n-m]

d[i]为错排方案数=d[i-1]*n+(-1)^n

 const mo=;

 var fac,exf,d:array[..]of int64;

     cas,i,n,m:longint;

 function c(x,y:longint):int64;

 begin

  exit(fac[x]*exf[y] mod mo*exf[x-y] mod mo);

 end;

 begin

  assign(input,'bzoj4517.in'); reset(input);

  assign(output,'bzoj4517.out'); rewrite(output);

  d[]:=;

  for i:= to  do

  begin

   d[i]:=d[i-]*i;

   if i and = then inc(d[i])

    else dec(d[i]);

   d[i]:=d[i] mod mo;

  end;

  fac[]:=; exf[]:=; exf[]:=;

  for i:= to  do fac[i]:=fac[i-]*i mod mo;

  for i:= to  do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo;

  for i:= to  do exf[i]:=exf[i-]*exf[i] mod mo;

  readln(cas); d[]:=;

  for i:= to cas do

  begin

   readln(n,m);

   writeln(c(n,m)*d[n-m] mod mo);

  end;

  close(input);

  close(output);

 end.