文章

68

粉丝

691

获赞

26

访问

578.3k

头像
错排问题-C++实现
P1480
发布于2020年5月26日 13:09
阅读数 10.0k

https://blog.csdn.net/csyifanZhang/article/details/106353929

long long C[MAX][MAX], dp[MAX];//C[i][j]:在i个里面取j个

int main() {
	for (int i = 1; i < MAX; i++) {
		C[i][i] = C[i][0] = 1;
		for (int j = 1; j < i; j++) {
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
		}
	}
	dp[0] = 1; dp[1] = 0, dp[2] = 1, dp[3] = 2;//dp[i]:i个物品错排的组合数
	long long b = 6;
	for (int i = 4; i < MAX; i++) {
		b *= i; dp[i] = b;
		for (int j = 1; j <= i; j++)
			dp[i] -= C[i][j] * dp[i - j];
	}
	int n, t; cin >> n;
	while (n--) {
		cin >> t;
		cout << dp[t] << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发