自动搬运

查看原文

来自洛谷，原作者为

	Flokirie **

搬运于2025-08-24 21:59:27，当前版本为作者最后更新于2018-06-23 21:39:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为一个以数竞为主的OIer，怎能不来写一发与组合数有关的题解？（尽管Flokirie的组合数学一塌糊涂）
看题：

题目大意

将x写成k个组合数的和，要求：在组合数 $C _n ^m$中，$n\le x$。

题目分析

我们先列出杨辉三角的前几行：

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5   10 10   5   1
1   6  15  20  15   6   1

写到这里我们发现：其实任何一个数都是某个组合数：
$n=C_n^1=C_n^{n-1}$

而且1还有多种表示形式：

$1=C_n^0=C_n^n$

那我们就可以把x写成下面的形式了：
$x=\sum _{i=1} ^{k-1} 1+(x-k+1)$
$\ \ \ =\sum _{i=1} ^{k-1} C_i^0+C_{x-k+1}^1$
容易验证这样构造的$k$个组合数都满足下标限制且两两不同。证毕。

代码

什么？分析得这么明白你还想要代码？

#include <bits/stdc++.h>

using namespace std;

int main(){
	int x,k;
	scanf("%d %d",&x,&k);
	for (int i=1;i<k;i++){
		printf("%d 0\n",i);
	}
	printf("%d 1\n",x-k+1);
	return 0;
}