题解 P1869 【愚蠢的组合数】
LuckyCloud
2018-08-20 16:53:15
**对于C(N,K)**
**首先是不重复取K个，那么第一次有N种选择，第二次有（N-1）种选择，以此类推就有
【N（N-1）（N-2）（N-3）……（N-K+1）】种选择**
**但是这样会有一个问题**
**比如**
**在3个里取两个**。
1 3
1 2
**2 1**
2 3
**3 1**
**3 2**
**(加粗为重复计算的)**
**会发现这些重复的只是同一数字的位置不同而已。**
**给定K种物品，对于第一个位置，我们可以放K种，第二个位置，可以放(K-1)种，以此类推，会有【K（K-1）（K-2）……1】 种摆放方式**
### 那么
#### C(N,K)=【N（N-1）（N-2）（N-3）……（N-K+1）】÷【K（K-1）（K-2）……1】
**好了，现在我们想知道C（N,K）是奇数还是偶数，我们只要关心是分母所拥有2这个因子多，还是分子所拥有2这个因子多。如果分子多的话，两者相除，结果肯定没有2这个因子，所以肯定是奇数。反之，那就是偶数咯**
**我们可以直接预处理出 1——i（1<=i<=10万)这个范围内2这个因子的总个数。其实就是类似前缀和，详细看代码。**
**分母是一段连续数的乘法，分子同样也是。我们以tot[i]表示1——i内2这个因子的总个数。**
**【N（N-1）（N-2）（N-3）……（N-K+1）】=tot[n]-tot[n-k]**
**【K（K-1）（K-2）……1】=tot[k]**
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int x,T,y,n,k,tot[101000],a,b;
inline int read()
{
int cnt=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){cnt=cnt*10+ch-48;ch=getchar();}
return cnt*f;
}
int main()
{
T=read();
for (int i=1;i<=100010;i++)
{
x=0;y=i;
while (!(y&1)&&y) {y>>=1;x++;}
tot[i]=tot[i-1]+x;
}
while (T--)
{
n=read();k=read();
a=tot[n]-tot[n-k];
b=tot[k];
if (a>b) puts("0");
else puts("1");
}
return 0;
}
```