P4369题解

· · 题解

作为一个以数竞为主的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;
}