站外题 递推高精度 40pts求助
  • 板块灌水区
  • 楼主somek_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/11 19:22
  • 上次更新2024/7/11 20:20:29
查看原帖
站外题 递推高精度 40pts求助
1037054
somek_楼主2024/7/11 19:22

#include <bits/stdc++.h>
using namespace std;
int n, m, w, h, k;

struct bignum {
	int len, num[50];
	bignum() {
		len = 0;
		memset(num, 0, sizeof(num));
	}
	bignum operator * (const int &b) {
		bignum a = *this;
		for (int i = 1; i <= len; i ++)
			a.num[i] *= b;
		for (int i = 1; i <= len; i ++) {
			a.num[i + 1] += a.num[i] / 10;
			a.num[i] %= 10;
		}
		a.len = len;
		while (a.num[a.len + 1]) {
			a.len ++;
			a.num[a.len + 1] += a.num[a.len] / 10;
			a.num[a.len] %= 10;
		}
		return a;
	}
	void operator += (const bignum &b) {
		len = std::max(len, b.len);
		for (int i = 1; i <= len; i ++) {
			num[i] += b.num[i];
			num[i + 1] += num[i] / 10;
			num[i] %= 10;
		}
		while (num[len + 1]) {
			len ++;
			num[len + 1] += num[len] / 10;
			num[len] %= 10;
		}
	}
	void print() {
		if (!len) {
			puts("0");
		} else {
			for (int i = len; i >= 1; i --)
				printf("%d", num[i]);
			puts("");
		}
	}
} f[50][50], dp[50][50][50], ans;

int main() {
//	freopen("chess.in", "r", stdin);
//	freopen("chess.out", "w", stdout);
	cin >> n >> m >> w >> h >> k;
	if (w == 0 && h == 0) {
		f[0][0].len = 1;
		f[0][0].num[1] = 1;
		for (int i = 0; i < max(n, m); i++)
			for (int j = 0; j < max(n, m); j++) {
				f[i + 1][j + 1] += f[i][j + 1];
				f[i + 1][j + 1] += f[i][j] * (max(n, m) - j);
			}
		f[max(n, m)][k].print();
	} else {
		w = min(n, w);
		h = min(n, h);
		int L1 = w, L2 = n - w, L3 = m + w - n;
		dp[0][0][0].len = 1;
		dp[0][0][0].num[1] = 1;
		for (int ceng = 1; ceng <= h + m; ceng++)
			for (int x = min(L1, k); x >= 0; x--)
				for (int y = min(L2, k - x); y >= 0; y--)
					for (int z = min(L3, k - x - y); z >= 0; z--) {
						if (x && ceng <= n)
							dp[x][y][z] += dp[x - 1][y][z] * (L1 - (x - 1));
						if (y)
							dp[x][y][z] += dp[x][y - 1][z] * (L2 - (y - 1));
						if (z && ceng > h)
							dp[x][y][z] += dp[x][y][z - 1] * (L3 - (z - 1));
					}
		for (int i = 0; i <= k; i++)
			for (int j = 0; j <= k - i; j++)
				ans += dp[i][j][k - i - j];
		ans.print();
	}
}
2024/7/11 19:22
加载中...