[RQNOJ29][stupid]愚蠢的组合数（计算n!中2因子个数）

[RQNOJ 29][stupid]愚蠢的组合数这题看一眼就知道是求C(n,k)的奇偶性，其实貌似这题只不过是PKU3219的包装版本……由C(n,k)=n!/(k!*(n-k)!)可以知道，只要能够算出n!, k!, (n-k)!中因子2的个数就能够得出答案。关键就在于如何计算n!中因子2的个数。

那天请教了下lzc，发现一个很快速的方法。计算n!中2因子的个数=[n/21]+[n/22]+[n/23]+…+[n/2[lg(n)]]其中lg(n)表示log2(n)，[x]表示下取整。原理也很简单：

[n/21]，统计了1~n中2的倍数的个数，也就是先统计了一部分的2因子。

[n/22]，又统计了4的倍数的个数，由于4=2*2，之前去掉一个2了，所以这一遍就加上剩下的这个2，不多不少。

……

直到[n/2[lg(n)]]。这样就把12…*n中所有的2因子都取出来了。

在写程序的时候，就是不断的x/=2;ans+=x;直到x=0。另外，由于计算机计算除法的时间是乘法的五六倍，而位运算则和加减乘速度相同，所以除以2可以直接看成是向右移动一位，这样效率就高多了（常数级的优化）。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

{
RQNOJ 29
abcdabcd987
@2011.08.02
}
var t,n,k:longint;
function b(x:longint):longint;
  begin
    b:=0;
    repeat
      x:=x shr 1;
      inc(b,x);
    until x=0;
  end;
begin
  readln(t);
  while t>0 do begin
    dec(t);
    readln(n,k);
    writeln(ord(b(n)-b(n-k)-b(k)<=0));
  end;
end.

Comments