易混 2008 年湖南预赛 第 11 题 · P010872
两题都可译为有序整数三元组,但固定总和的一层与总和落在区间内不是同一个计数对象。先明确层或区域,再选择坐标超界容斥或上下尾部补集。
指定系数题按某个坐标超过上界来平移;区间题可用补元对称配对两端。固定层的隔板式不能直接当作一段总和的累计数。
若整数 满足
则满足条件的有序数组 共有 组。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先数立方格点总数,再利用 的对称性扣除两端。
不计和的限制时共有 组。和不超过 的非负整数三元组个数为
此时各变量自动不超过 。变换
把和不超过 的数组双射到和不小于 的数组。因此所求为
两个被扣除区域互不相交,且变换保持每个坐标在 内,双射无边界遗漏。
有上下界且总和位于中间区间的格点计数,常可用立方体中心对称把上下尾部化为同一个星棒问题。
下尾和不超过9时上界自动满足,用隔板法计数,再以坐标关于5反射得到等大的上尾。
易混 2008 年湖南预赛 第 11 题 · P010872
两题都可译为有序整数三元组,但固定总和的一层与总和落在区间内不是同一个计数对象。先明确层或区域,再选择坐标超界容斥或上下尾部补集。
指定系数题按某个坐标超过上界来平移;区间题可用补元对称配对两端。固定层的隔板式不能直接当作一段总和的累计数。
已记下,谢谢!