首页 > 技术文章 > Luogu P4369 [Code+#4]组合数问题 题解

EdisonBa 2020-09-24 18:54 原文

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

题目分析:

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

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

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

\(n\) 个不同元素中每次取出 \(m\) 个不同元素 \((0\leq m\leq 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}\tbinom{i}{0} + \tbinom{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\n",i,i);
	printf("%d 1",x-k+1);
	return 0;
}

推荐阅读