易混 2010 年黑龙江预赛 第 19 题 · P010585
把按结果分组的总和改成按基本对象数贡献,常能绕开逐项闭式;但每个对象究竟出现一次还是出现多次,必须由原索引范围决定,不能一律当作普通子集数。
前题求导产生递减线性权重,一个数列项会进入若干个部分和;后题对全部正目标和求方案数,每个有身份的非空牌子集恰好落入一个目标,标数相同也不能合并身份。
盒中装有红色和蓝色纸牌各 张,每色纸牌都含标数为 的牌各一张,两色纸牌的标数总和记为 。对于给定的正整数 ,若能从盒中取出若干张牌,使其标数之和恰为 ,便称为一种取牌 方案,不同的 方案种数记为 。试求 的值。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
不逐个求每个目标和的方案数,而把所有正目标对应方案合在一起:每个非空牌子集恰贡献一次。
两种颜色的每一张牌都是有身份的对象,共二百张。任意非空子集的标数和为某个正整数 ,因而恰计入 一次;反过来每个取牌方案正是这样一个非空子集。所以分目标和计数与直接数非空子集等价,得到
所有牌标数为正,所以只有空子集的和为零,其他方案均在题目求和范围。两色同标数牌仍不同,取红牌一或蓝牌一是不同方案,不应按标数值把它们合并。
对所有可能目标累加方案数,常可绕开逐目标的表达,直接数每个方案在全部目标中出现几次。
逐目标计数复杂,需换成对全部非空方案的整体计数,证明求和无重无漏且保留两色牌身份。
易混 2010 年黑龙江预赛 第 19 题 · P010585
把按结果分组的总和改成按基本对象数贡献,常能绕开逐项闭式;但每个对象究竟出现一次还是出现多次,必须由原索引范围决定,不能一律当作普通子集数。
前题求导产生递减线性权重,一个数列项会进入若干个部分和;后题对全部正目标和求方案数,每个有身份的非空牌子集恰好落入一个目标,标数相同也不能合并身份。
已记下,谢谢!