Binary Stirling Numbers
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 1040 |
|
Accepted: 346 |
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
判斷第二類斯特靈數模 2 的余數。
在劉汝佳的黑書上有詳細解答，基本思路是枚舉數值較小的斯特靈數，從中尋找規律。
下面這幅圖是從維基百科截出來的，有一個二進制斯特靈數與組合數的轉化公式。而組合數模二的余數就很容易了。
我們知道，組合數C（N,M）=N ! / M ! /(N-M)!,因而只需求得階乘質因數分解式中二的重數即可解決問題。
而N ！質因數分解后2的重數可用下式來計算之。
K=N/2+N/2^2+N/2^3+....
上式的除法全是下取整。（可參見任何一本初等數論課本，如北大潘承洞編的那本《初等數論》）。
這樣，這個問題就迎刃而解。
另外，有一點說明的是上面那個圖形，就是分形幾何中一個很重要的例子——謝彬斯基墊片。楊輝三角也有類似的形狀。
這是我用MATLAB作的一個楊輝三角的二進制圖形。
#include <stdio.h>
int main(int argc, char *argv[])
{
int n,m;
int z,w1,w2;
int t;
int a,b,c;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
z=n-(m+2)/2;
w1=(m-1)/2;
w2=z-w1;
a=0;
while (z)
{
z>>=1;
a+=z;
}
b=0;
while (w1)
{
w1>>=1;
b+=w1;
}
c=0;
while (w2)
{
w2>>=1;
c+=w2;
}
printf("%d\n",(a-b-c)==0);
}
return 0;
}