poj 1430 Binary Stirling Numbers

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

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)的奇偶性就可以了。（当然有很多书写方式，不一定要这样做。）

测试用的

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 int dp[21][21];
 8 int cnm[21][21];
 9 void init()
10 {
11     int i,j;
12     dp[0][0]=1;
13     for(i=1;i<=20;i++) dp[i][0]=0;
14     for(i=1;i<=20;i++)
15         for(j=1;j<=i;j++)
16             dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
17     for(i=0;i<=15;i++)
18     {
19         for(j=0;j<=i;j++)
20             printf("%d ",(dp[i][j]&1));
21         printf("
");
22     }
23 
24     cnm[0][0]=1;
25     for(i=1;i<=20;i++)
26     {
27         cnm[i][0]=1;
28         cnm[0][i]=1;
29     }
30     for(i=1;i<=20;i++)
31     {
32         for(j=1;j<=i;j++)
33         {
34             if(j==1) cnm[i][j]=i;
35             else if(i==j) cnm[i][j]=1;
36             else cnm[i][j]=cnm[i-1][j]+cnm[i-1][j-1];
37         }
38     }
39     for(i=0;i<=15;i++)
40     {
41         for(j=0;j<=i;j++)
42             printf("%d ",cnm[i][j]&1);
43         printf("
");
44     }
45 }
46 int main()
47 {
48     init();
49     int n,m;
50     while(scanf("%d%d",&n,&m)>0)
51     {
52         printf("%d
",dp[n][m]);
53     }
54     return 0;
55 }

View Code

ac代码

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 int a[64],alen;
 8 int b[64],blen;
 9 void solve(int n,int m)
10 {
11     int i;
12     bool flag=false;
13     alen=0;
14     blen=0;
15     memset(a,0,sizeof(a));
16     memset(b,0,sizeof(b));
17     while(n)
18     {
19         a[++alen]=(n&1);
20         n=n>>1;
21     }
22     while(m)
23     {
24         b[++blen]=(m&1);
25         m=m>>1;
26     }
27     for(i=1; i<=alen; i++)
28     {
29         if(a[i]==0 && b[i]==1) flag=true;
30         if(flag==true) break;
31     }
32     if(flag==true)printf("0
");
33     else printf("1
");
34 }
35 int main()
36 {
37     int T;
38     int n,m,k;
39     scanf("%d",&T);
40     while(T--)
41     {
42         scanf("%d%d",&n,&m);
43         if(m%2==0)
44         {
45             n=n-1;
46             m=m-1;
47         }
48         k=(m+1)/2;
49         solve(n-k,m-k);
50     }
51     return 0;
52 }

View Code