当前位置:编程学习 > C/C++ >>

poj 1430 Binary Stirling Numbers

第二类Stirling数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。
递推公式为:
S(n,k) = 0(n<k||k=0),
S(n,n) = S(n,1) = 1,
S(n,k) = S(n-1,k-1) + kS(n-1,k).

下面这幅图是从维基百科截出来的,有一个二进制斯特灵数与组合数的转化公式。而组合数模二的余数就很容易了。

 

我们知道,组合数C(N,M)=N ! / M ! /(N-M)!,因而只需求得阶乘质因数分解式中二的重数即可解决问题。
而N !质因数分解后2的重数可用下式来计算之。
K=N/2+N/2^2+N/2^3+....

 

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
 

代码:

[cpp] 
#include<iostream> 
using namespace std; 
int f(int k) 

    int a=0; 
    while(k) 
    { 
      k=k/2; 
      a+=k; 
    } 
    return a; 

int main() 

    int t,n,m,z,w1,w2; 
    scanf("%d",&t); 
    while(t--) 
    { 
      scanf("%d%d",&n,&m); 
      z=n-(m+2)/2; 
      w1=(m-1)/2; 
      w2=z-w1; 
      if(f(z)==f(w1)+f(w2)) 
        printf("1%\n"); 
      else printf("0%\n"); 
    } 
    return 0; 

     
     

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,