组合数学+高精度 BZOJ2729 [HNOI2012]排队

2729: [HNOI2012]排队

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1787  Solved: 845
[Submit][Status][Discuss]

Description

某中学有 n 名男同学，m 名女同学和两名老师要排队参加体检。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？（注意：任意两个人都是不同的）

 

Input

只有一行且为用空格隔开的两个非负整数 n 和 m，其含义如上所述。

 

对于 30%的数据 n≤100,m≤100

 

对于 100%的数据 n≤2000,m≤2000

Output

输出文件 output.txt 仅包含一个非负整数，表示不同的排法个数。注意答案可能很大。

Sample Input

1 1

Sample Output

12

HINT

Source

day1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
const int mod=100000000;
struct data{
    long long num[100010];
    int len;
    void print(){
        printf("%lld",num[len]);
        for(int i=len-1;i>=1;i--) printf("%08lld",num[i]);
    }
}a;
void cheng(int x){
    for(int i=1;i<=a.len;i++) a.num[i]*=x;
    for(int i=1;i<=a.len;i++) a.num[i+1]+=a.num[i]/mod,a.num[i]%=mod;
    while(a.num[a.len+1]) a.len++,a.num[a.len+1]+=a.num[a.len]/mod,a.num[a.len]%=mod; 
}
int main(){
    scanf("%d%d",&n,&m);
    a.len=1;
    a.num[1]=1;
    for(int i=2;i<=n;i++) cheng(i);
    cheng(n+1);
    cheng((n+3)*n+2*m);
    for(int i=n+4-m;i<=n+2;i++) cheng(i);
    a.print();
    return 0;
}