526互联

Luogu P3223 [HNOI2012] 排队

发布时间 2023-06-13 16:38:13作者: Joker__King

[HNOI2012] 排队

题目描述

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

输入格式

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

输出格式

仅一个非负整数，表示不同的排法个数。注意答案可能很大。

样例 #1

样例输入 #1

1  1

样例输出 #1

12

提示

对于 \(30\%\) 的数据 \(n\leq 100\)，\(m\leq 100\)。

对于 \(100\%\) 的数据 \(n\leq 2000\)，\(m\leq 2000\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

long long n, m;

struct HighPrecision {
	struct Number{
		int num[20000];
		int len;
	}tem;
	inline void Clear(Number &xxx) {
		xxx.len = 0;
		memset(xxx.num, 0, sizeof(xxx.num));
	}
	inline Number Change(long long a) {
		Clear(tem);
		int len = 0;
		while (a != 0) {
			len ++;
			tem.num[len] = a %10;
			a /= 10;
		}
		tem.len = len;
		return tem;
	}//低精转高精 
	inline Number Addition (Number &a, Number &b) {
		int len = max(a.len, b.len);
		Clear(tem);
		for (int i = 1; i <= len; ++ i) {
			tem.num[i] += (a.num[i] + b.num[i]);
			if (tem.num[i] >= 10) {
				tem.num[i + 1] += (tem.num[i] / 10);
				tem.num[i] %= 10;
			}
		}
		if (tem.num[len + 1] != 0) len ++;
		tem.len = len;
		return tem;
	}//高精加 
	inline Number Product(Number &a, Number b) {
		int len_a = a.len, len_b = b.len, len_c = 0;
		Clear(tem);
		for (int i = 1; i <= len_a + len_b; ++ i) {
			tem.num[i] = 0;
		}//记得初始化 
		for (int i = 1; i <= len_a; ++ i) {
			for (int j = 1; j <= len_b; ++ j) {
				tem.num[i + j - 1] += a.num[i] * b.num[j];
				len_c = max(len_c, i + j - 1);
			}
		}
		for (int i = 1; i <= len_c; ++ i) {
			tem.num[i + 1] += (tem.num[i] / 10);
			tem.num[i] %= 10;
			if (i == len_c && tem.num[i + 1] != 0) {
				len_c += 1;
			}
		}
		while (tem.num[len_c] == 0) {
			len_c --;
		}
		tem.len = len_c;
		return tem;
	}//高精乘法 
	inline void Print(Number &x) {
		for (int i = x.len; i >= 1; -- i) {
			cout << x.num[i];
		}
		cout << endl;
		return;
	}//输出 
}Use;

HighPrecision::Number a, b, c;

int main() {
	cin >> n >> m;
	if (n == 0 && m == 0) {
		cout << 0;
		return 0;
	}
	a = Use.Change(1);
	for (int i = 2; i <= n; ++ i) {
		a = Use.Product(a, Use.Change(i));
	}
	a = Use.Product(a, Use.Change(n));
	a = Use.Product(a, Use.Change(n + 1));
	for (int i = n + 3 - m + 1; i <= n + 3; ++ i) {
		a = Use.Product(a, Use.Change(i));
	}
	b = Use.Change(2 * m);
	for (int i = 2; i <= n + 1; ++ i) {
		b = Use.Product(b, Use.Change(i));
	}
	for (int i = n + 3 - m + 1; i <= n + 2; ++ i) {
		b = Use.Product(b, Use.Change(i));
	}
	c = Use.Addition(a, b);
	Use.Print(c);
	return 0;
}