求通式f(n)

hujunhua

A对应于一个 n 位 2 进数 a（可含前导 0），c= a的奇数位之和-a的偶数位之和。
由初等数论中的同余理论知`c\equiv a\pmod 3`. 因此问题等价于求0~11...1（n个1，2进数）中3的倍数有多少个。
显然结果就是`\lfloor\frac{2^{n-1}}3\rfloor+1`。

aimisiyou

你说的等价我怎么百思不得其姐？

aimisiyou

还真是那么回事！
原来，一个2进整数对模3的余数等于其奇数位之和减去偶数位之和所得差对模3的余数。
正如，一个十进整数对模11的余数等于其奇数位之和减去偶数位之和所得差对模11的余数。
一般而言，一个n 进整数对模(n+1)的余数等于其奇数位之和减去偶数位之和所得差对模(n+1)的余数。

aimisiyou

接9楼，若将该区域平移，如将（0，0）移动至另一整数点对上，其符合要求的点对个数是否保持不变？感觉是的，到说不清理由。谁能解释下？

aimisiyou

算了下，原来是坐标平移变换保持结果不变。