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

    • 141通过
    • 232提交
  • 题目提供者 和泉正宗
  • 评测方式 云端评测
  • 标签 Special Judge
  • 难度 普及/提高-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    众所周知,小葱同学擅长计算,尤其擅长计算组合数,所以小葱给了你两个数 $x$ 和 $k$,希望你把 $x$ 分成恰好 $k$ 个不同的组合数的和。所谓不同,即对于两个组合数 $C(n_1,m_1)$ 和 $C(n_2,m_2)$,如果 $n_1\neq n_2$​​ 或者 $m_1\neq m_2$​,我们就称这两个组合数是不同的。为了使得计算不过于复杂,你需要保证你给出的任何一个组合数 $C(n,m)$ 满足 $0\leq m\leq n\leq x$。数据保证一定有解。

    输入输出格式

    输入格式:

    从标准输入读入数据。

    第一行两个整数 $x,k$。

    输出格式:

    输出到标准输出。

    $k$ 行,每行两个整数 $n,m$ 代表一个组合数 $C(n,m)$。如果有多种可能的答案,任意输出一组即可。

    输入输出样例

    输入样例#1: 复制
    6 2
    输出样例#1: 复制
    3 1
    3 2

    说明

    对于 $20\%$ 的数据,$k=1$。

    对于另外 $20\%$ 的数据,$x\leq 100$。

    对于另外 $20\%$ 的数据,$k=2$。

    对于 $100\%$ 的数据,$1\leq x\leq 10^9,1\leq k\leq 10^3.$

    Credit: https://www.luogu.org/discuss/show/38908

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。