Luogu P4369 [Code+#4]组合数问题 题解

Luogu P4369 [Code+#4]组合数问题

题目分析:

题目大意为把 (x) 分成 (k) 个组合数 (C(n_i,m_i))

(C(n_1,m_1))(C(n_2,m_2))

首先,我们要明确什么是组合数。

(n) 个不同元素中每次取出 (m) 个不同元素 ((0leq mleq n)),不管其顺序合成一组,所有这样的组合的种数称为组合数。在线性写法中被写作 (C(n,m))

看到这个题,我们可以想到组合数的一些互补性质:(C(n,0)=1) , $ C(n,n)=1 $ , $ C(n,1)=n$ 。

那么,我们可以先假设要把 (x) 分成 (x) 个组合数,这样每个组合数就等于 1 。想要让每个组合数不相等,就可以使 (x) 被分成:(C(1,0)+C(2,0)+C(3,0)+~...~+C(x,0))

但是,题目中说让分成 (k) 个组合数。我们可以先分配 (k-1) 个组合数给 (C(i,0)) ,这样,(x) 这个数里没有被分配的值为 (x-k+1) 。由$ C( n,1)=n$,我们可以把最后的一个组合数用 (C( x-k+1,1)) 来表示。

综上,把 (x) 分成 (k) 个组合数可以分为:

[sum ^{k-1}_{i=1} binom{i}{0} + binom{x-k+1}{1} ]

代码

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int x,k;
	cin>>x>>k;
	for(int i=1;i<=k-1;++i)
	printf("%d 0
",i,i);
	printf("%d 1",x-k+1);
	return 0;
}
原文地址:https://www.cnblogs.com/EdisonBa/p/13725790.html