易混 2013 年安徽预赛 第 7 题 · P010540
两题都出现模三的分类,却在不同对象上取余。逐系数余数分布关心每个组合数的数值,需用指数的三进制数位;筛三倍下标的系数和关心项的位置,可用三次单位根消去不合下标。
不能把“下标属于某个余数类”和“系数数值属于某个余数类”混同;两种筛选作用在多项式的不同信息上。
组合数模3的余数分布
记组合数 ,数列 满足: 为 除以 的余数,,。 则数列 中数字为 的数目比为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
在模 下使用 Lucas 定理; 的三进制数位很稀疏,非零系数只需检查少量数位选择。
。由 Lucas 定理, 当且仅当 的每一位均不超过 的对应三进制数位,因此这样的 共有
个,故余数为 的项有 个。
对每个允许的三进制数位,模 的系数是各位小组合数之积。两个顶端数位为 ,每一位取 时相应因子为 ;另一个非零顶端数位为 ,下标数位取 或 时,相应因子均为 。因此两个“2”数位中恰有 奇数个取 时余数为 ,共有
项;其余 项余数为 。所以数目比为
直接由 展开,也得到非零项 个,其中余数 为 个,与 Lucas 逐位统计一致。
组合数模素数的零项和非零余数分布都可由 Lucas 定理逐位统计;化简比例前先核对三类数目之和应为 。
将2025写成三进制2210000以定非零位置,再统计两个最高2数位中取中间位的次数奇偶,区分余数1和2。
易混 2013 年安徽预赛 第 7 题 · P010540
两题都出现模三的分类,却在不同对象上取余。逐系数余数分布关心每个组合数的数值,需用指数的三进制数位;筛三倍下标的系数和关心项的位置,可用三次单位根消去不合下标。
不能把“下标属于某个余数类”和“系数数值属于某个余数类”混同;两种筛选作用在多项式的不同信息上。
已记下,谢谢!