欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ1430 Binary Stirling Numbers

程序员文章站 2022-07-15 10:44:44
...

@(POJ)[Stirling數, 排列組合, 數形結合]

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

Solution

題意:
求斯特林數\[ \left\{ \begin{array}{} n \\ k \end{array}{} \right\} \% 2\]\[n, m \in [1, 10^9]\]
這題直接求解肯定是會T的, 因此考慮優化.

轉載自sdchr博客
侵刪

POJ1430 Binary Stirling Numbers
POJ1430 Binary Stirling Numbers
代碼附上:

#include<cstdio>
#include<cctype>
using namespace std;

inline int read()
{
    int x = 0, flag = 1;
    char c;
    while(! isdigit(c = getchar()))
        if(c == '-')
            flag *= - 1;
    while(isdigit(c))
        x = x * 10 + c - '0', c = getchar();
    return x * flag;
}

void println(int x)
{
    if(x < 0)
        putchar('-'), x *= - 1;
    if(x == 0)
        putchar('0');
    int ans[1 << 5], top = 0;
    while(x)
        ans[top ++] = x % 10, x /= 10;
    for(; top; top --)
        putchar(ans[top - 1] + '0');
    putchar('\n');
}

long long getQuantity(int x)
{
    long long ret = 0;
    
    for(int i = 2; i <= x; i <<= 1)
        ret += x / i;
        
    return ret;
}

int calculate(int x, int y)
{
    return getQuantity(x) - getQuantity(y) - getQuantity(x - y) == 0;
}

int main()
{
    int T = read();
    
    while(T --)
    {
        int n = read(), m = read();
        int d = n - m, oddQua = (m + 1) / 2;
        println(calculate(d + oddQua - 1, oddQua - 1));
    }
}