Binary Stirling Numbers
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 1761 | Accepted: 671 |
Description
The Stirling number of the second kind S(n, m) stands for the number of ways to partition a set of n things into m nonempty subsets. For example, there are seven ways to split a four-element set into two parts:
{1, 2, 3} U {4}, {1, 2, 4} U {3}, {1, 3, 4} U {2}, {2, 3, 4} U {1}
{1, 2} U {3, 4}, {1, 3} U {2, 4}, {1, 4} U {2, 3}.
There is a recurrence which allows to compute S(n, m) for all m and n.
S(0, 0) = 1; S(n, 0) = 0 for n > 0; S(0, m) = 0 for m > 0;
S(n, m) = m S(n - 1, m) + S(n - 1, m - 1), for n, m > 0.
Your task is much "easier". Given integers n and m satisfying 1 <= m <= n, compute the parity of S(n, m), i.e. S(n, m) mod 2.
Example
S(4, 2) mod 2 = 1.
Task
Write a program which for each data set:
reads two positive integers n and m,
computes S(n, m) mod 2,
writes the result.
Input
The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 200. The data sets follow.
Line i + 1 contains the i-th data set - exactly two integers ni and mi separated by a single space, 1 <= mi <= ni <= 10^9.
Output
The output should consist of exactly d lines, one line for each data set. Line i, 1 <= i <= d, should contain 0 or 1, the value of S(ni, mi) mod 2.
Sample Input
1
4 2
Sample Output
1
Source
可以转化成求C（N,M)来做。当然不是直接转化。
打出表看一下，发现是有规律的。
每一列都会重复一次。打表看一下吧。
思路：
s(n,m) 如果m是偶数 n=n-1; m=m-1;==>转化到它的上一个s(n-1,m-1);
k=(m+1)/2; n=n-k; m=m-k;求C（n,m)的奇偶性就可以了。（当然有很多书写方式，不一定要这样做。）
测试用的
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std; int dp[][];
int cnm[][];
void init()
{
int i,j;
dp[][]=;
for(i=;i<=;i++) dp[i][]=;
for(i=;i<=;i++)
for(j=;j<=i;j++)
dp[i][j]=dp[i-][j-]+dp[i-][j]*j;
for(i=;i<=;i++)
{
for(j=;j<=i;j++)
printf("%d ",(dp[i][j]&));
printf("\n");
} cnm[][]=;
for(i=;i<=;i++)
{
cnm[i][]=;
cnm[][i]=;
}
for(i=;i<=;i++)
{
for(j=;j<=i;j++)
{
if(j==) cnm[i][j]=i;
else if(i==j) cnm[i][j]=;
else cnm[i][j]=cnm[i-][j]+cnm[i-][j-];
}
}
for(i=;i<=;i++)
{
for(j=;j<=i;j++)
printf("%d ",cnm[i][j]&);
printf("\n");
}
}
int main()
{
init();
int n,m;
while(scanf("%d%d",&n,&m)>)
{
printf("%d\n",dp[n][m]);
}
return ;
}
ac代码
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
using namespace std; int a[],alen;
int b[],blen;
void solve(int n,int m)
{
int i;
bool flag=false;
alen=;
blen=;
memset(a,,sizeof(a));
memset(b,,sizeof(b));
while(n)
{
a[++alen]=(n&);
n=n>>;
}
while(m)
{
b[++blen]=(m&);
m=m>>;
}
for(i=; i<=alen; i++)
{
if(a[i]== && b[i]==) flag=true;
if(flag==true) break;
}
if(flag==true)printf("0\n");
else printf("1\n");
}
int main()
{
int T;
int n,m,k;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(m%==)
{
n=n-;
m=m-;
}
k=(m+)/;
solve(n-k,m-k);
}
return ;
}