奇数三元组
|
取集合$\{1,2,…,n\}$的所有k元子集，并记其中元素和为奇数的子集数目为$f(n,k)$。
例如集合$\{1,2,3,4,5\}$的所有三元子集中有三个子集的和为奇数，它们分别是$\{1,2,4\}$、$\{1,3,5\}$、$\{2,3,4\}$和$\{2,4,5\}$，因此$f(5,3)=4$。
当n、k和$f(n,k)$均为奇数时，就称之为奇数三元组$[n,k,f(n,k)]$。
当$n\le10$时，恰有五个奇数三元组，分别是：$[1,1,f(1,1)=1]$、$[5,1,f(5,1)=3]$、$[5,5,f(5,5)=1]$、$[9,1,f(9,1)=5]$和$[9,9,f(9,9)=1]$。
求$n\le10^{12}$时奇数三元组的总数。
|
本题难度:
|
解答
|
为方便起见，以下规定若$y>x$，则$\binom{x}{y}=0$。
设$[n,k,f(n,k)]$是一奇数三元组，并设$n=2a+1$，$k=2b+1$。\\
此时$\{1,2,…,n\}$中有a个偶数，$a+1$个奇数，预使子集和为奇数，子集中必定有偶数个偶数，因此
$$f(n,k)=\sum_j\binom{a}{2j}\binom{a+1}{k-2j}.$$
注意到$k-2j$是奇数，因此$a+1$也需要是奇数。这是因为：
引理： 若$x$是偶数，$y$是奇数，则$\binom{x}{y}$是偶数。
证明很简单，考虑从x个物体中取出y个，并用一个x位的二进制数$d_y$来表示该选择，$d_y$的第i位是1就表示选择第i个的物体，否则表示不选。x是偶数，因此$d_y$不可能是回文数，否则$d_y$将有偶数个1，因此将$d_y$反转就可以得到另一个符合要求的取法，因此$\binom{x}{y}$是偶数。
由以上推断可知a是偶数，将其写成$a=2c$的形式，从而有
$$f(n,k)=\sum_j\binom{2c}{2j}\binom{2c+1}{2b-2j+1}=\sum_j\binom{c}{j}\binom{c}{b-j} \pmod 2.$$
其中最后一个等号可由第148题中提及的Lucas定理推得。
由上式的对称性可知b必须是偶数（考虑关于$b/2$对称的j），并设$b=2d$，则上式可以进一步简化为
$$f(n,k)=\sum_j\binom{c}{j}\binom{c}{b-j}=(\binom{c}{d})^2=\binom{c}{d} \pmod 2.$$
因此原问题转化为杨辉三角从第0行到第249999999999行中有多少个奇数。
由第148题的方法可知，第n行共有$2^{d_n}$个奇数，其中$d_n$是$n$的二进制表达中1的数量，以及前$2^k$行（即第0到$2^k-1$行）中共有$3^k$个奇数。
简单计算即得结果是$997104142249036713$。
s=format(250000000000,"b")
n=len(s)
r,m=0,1
for k,d in enumerate(s):
if d=="1":
r+=m*(3**(n-1-k))
m<<=1
print r
|
| |
