求大佬指点!!!
by TonyinSZ @ 2024-03-27 12:58:30
最粗暴的做法:
展开 $\frac{1}{(1-x)(1-x^3)(1-x^7)}$后得到一个公式
于是可以得到一种dp做法,方程:
$dp_i = dp_{i-1} + dp_{i-3} + dp_{i-7}$
by kjhhjki @ 2024-03-27 13:06:18
@[kjhhjki](/user/241935) 粗暴的生成函数事吧
by lonely_seele @ 2024-03-27 13:10:32
@[TonyinSZ](/user/1066461) 可以dp,我们令前面一段是1,中间是3,后面是7,
记$f_{i,0/1/2}$ 表示已经选了多少,当前是1/3/7 的部分。
by __zaa__ @ 2024-03-27 13:13:00
$$\sum_{i=0}^{n/7}\biggl\lfloor\dfrac{n-7i}{3}\biggl\rfloor+1$$
是不是
by Adchory @ 2024-03-27 13:14:32
**逃~~**
设三种金币面值分别为 1,3,7,对应的生成函数分别为 (x^{1}),(x^{3}),=(x^{7})。那么我们想要求的就是将这三个生成函数相乘后,找到 (x^{n}) 的系数,即为组合出面值和为 (n) 的方案数。
将三个生成函数相乘得到:
$$
[ (1 + x + x^{2} + \ldots)(1 + x^{3} + x^{6} + \ldots)(1 + x^{7} + x^{14} + \ldots) ]
$$
展开后,我们找到 (x^{n}) 的系数即可得到答案。
by xxs12345 @ 2024-03-27 15:43:39
@[kjhhjki](/user/241935) 哥GF都出来了咋不直接通项还要 DP 呢
by Iniaugoty @ 2024-03-27 19:01:42
而且这题通项是不是有亿点难求
by Iniaugoty @ 2024-03-27 19:03:23