2729:[HNOI2012]排队

题目描述 Description
某中学有n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）
输入描述 Input Description
输入文件只有一行且为用空格隔开的两个非负整数n 和m，其含义如上所述。
输出描述 Output Description
仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。
样例输入 Sample Input
样例输入1
1 1

样例输入2
7 3
样例输出 Sample Output
样例输出1
12

样例输出2
220631040
数据范围及提示 Data Size & Hint
对于30%的数据n≤100,m≤100
对于100%的数据n≤2000,m≤2000

先把老师和男同学放在一起，把女生插进来
再减去两个老师在一起的情况，经过化简
ANS=(n+1)!A(n+2,m-1)*(n^2+3*n+2*m)
然后就是高精度了

const
    h=1000000;
var
    a:array[0..10000]of int64;
    n,m:longint;

procedure cheng(x:int64);
var
    i:longint;
begin
    for i:=1 to a[0] do
      a[i]:=a[i]*x;
    for i:=1 to a[0] do
      begin
        inc(a[i+1],a[i]div h);
        a[i]:=a[i]mod h;
      end;
    i:=a[0]+1;
    while a[i]>0 do
      begin
        inc(a[0]);
        inc(a[i+1],a[i] div h);
        a[i]:=a[i]mod h;
        inc(i);
      end;
end;

procedure main;
var
    i,k:longint;
begin
    read(n,m);
    a[0]:=1;
    a[1]:=n*n+3*n+2*m;
    for i:=2 to n+1 do
      cheng(i);
    for i:=1 to m-1 do
      cheng(n+3-i);
    write(a[a[0]]);
    for i:=a[0]-1 downto 1 do
      begin
        k:=h div 10;
        while k>1 do
          begin
            if a[i]<k then write(0);
            k:=k div 10;
          end;
        write(a[i]);
      end;
end;

begin
    main;
end.