#3694. 9 月 13 日第六题

9 月 13 日第六题

提醒:如果你只是想做这道题,可以直接跳转到最后一行。但是生成函数是提高组初赛中较为难且重要的一部分内容,对于完全没接触过的同学,可以根据下面的内容简单学习一下。

母函数(生成函数)通过多项式来计算组合数学题目,比如现在有 11 克砝码、22 克砝码、33 克砝码每种重量各有几种可能的获取方案?

对于 11 克砝码,我们可以取或不取,得到的重量贡献分别是 1100,对应的母函数是 x0+x1=x+1x^0 + x^1 = x+1,其中 11 表示不取砝码产生的贡献,xx 表示取砝码产生的贡献。

对于 22 克砝码,对应的母函数是 x0+x2=x2+1x^0 + x^2 = x^2+1,其中 11 表示不取砝码产生的贡献,x2x^2 表示取砝码产生的贡献。

对于 33 克砝码,对应的母函数是 x0+x3=x3+1x^0 + x^3 = x^3+1,其中 11 表示不取砝码产生的贡献,x3x^3 表示取砝码产生的贡献。

将三者的母函数相乘,(x+1)(x2+1)(x3+1)=1+x+x2+2x3+x4+x5+x6(x+1)(x^2+1)(x^3+1) = 1+x+x^2+2x^3+x^4+x^5+x^6,所以可得到 77 种重量。再作深一些的解析,三者母函数相乘产生的 2x32x^3,代表三者可组成两种不同情况总重量为 33 的砝码。

x3x^3 可以由 1×1×x31\times 1\times x^3 得到,代表 1,21,2 克砝码不取,33 克砝码取;也可以由 x1×x2×1x^1\times x^2\times 1 得到,代表 1,21,2 克砝码,33 克砝码不取。

问:各位数字之和等于 1111 的三位数个数是?

{{ select(1) }}

  • 5959
  • 6262
  • 6060
  • 6161