三进制无进位有序数对计数
记
则集合 中的元素个数为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
,因此 到 恰好对应全部四位三进制串。
无进位条件在四个数位上彼此独立,可以先允许 计数,再用容斥删去两个数中至少一个为 的情形。
单个三进制数位上的有序数字对 必须满足 且 ,共有
这 种。四个数位独立,故在 时共有 个无进位有序数对。
若 ,则 可为 中任意一个,共 种; 同理,而 被重复扣除一次。因此
,所以没有遗漏任何四位三进制串;题目中的 有顺序,单个数位的 种也按有序对计数。
“某进制加法不进位”应拆成逐位限制,再用乘法原理。若题目变量从 开始而完整数位模型从 开始,最后需用容斥处理零值边界。
80恰是四位三进制全2,数位间独立有6种有序对,再容斥去除任一数为0的情况。
已记下,谢谢!