返回首页 返回专题

【POJ1430】Binary Stirling Numbers 题解

第二类斯特林数有一个奇特的公式：

若 ，则有

于是斯特林数的奇偶性计算就变成了组合数的奇偶性计算，然后就可以做了

#include<bits/stdc++.h>
using namespace std;

int div(int n)
{
	int cnt=0,b=2;
	while(n/b) cnt+=n/b,b*=2;
	return cnt;
}

int main()
{
	int T,n,k;
	for(cin>>T;T;T--)
	{
		scanf("%d%d",&n,&k);
		int z=n-(k+2)/2,w=(k-1)/2;
		puts((div(z)-div(w)-div(z-w)>0)?"0":"1");
	}
	return 0;
}