POJ1430_UVA1118

蔚落 2023-02-25 10:25 15阅读 0赞

![博客图片][format_png]

## 题目连接 ##

[POJ1430][]

## 题目概述 ##

判断第二类 s t i r l i n g stirling stirling数 S ( n , m ) S(n,m) S(n,m)的奇偶性.数据规模 n n n很大, ( 1 ≤ n ≤ 1 0 9 ) (1 \\leq n \\leq 10^9) (1≤n≤109).

## 不算方法的做法 ##

因为 S ( n , m ) = m ∗ S ( n − 1 , m ) + S ( n − 1 , m − 1 ) S(n,m)=m\*S(n-1,m)+S(n-1,m-1) S(n,m)=m∗S(n−1,m)\+S(n−1,m−1),当 m m m为偶数的时候, S ( n , m ) S(n,m) S(n,m)的奇偶性与 S ( n − 1 , m − 1 ) S(n-1,m-1) S(n−1,m−1)一样;当 m m m为奇数的时候, S ( n , m ) S(n,m) S(n,m)的奇偶性和 S ( n − 1 , m ) + S ( n − 1 , m − 1 ) S(n-1,m)+S(n-1,m-1) S(n−1,m)\+S(n−1,m−1)一样(为奇数的话, m m m可以替换为1,不改变奇偶性.然后得到一个式子:  
 S ∗ ( n , m ) = \{ S ∗ ( n − 1 , m − 1 ) , i f   m % 2 = 0 S ∗ ( n − 1 , m ) + S ∗ ( n − 1 , m − 1 ) , i f   m % 2 = 1 S^\*(n,m)= \\begin\{cases\} S^\*(n-1,m-1), \\quad if\\, m\\%2 = 0\\\\ S^\*(n-1,m)+S^\*(n-1,m-1),\\quad if\\, m\\%2 =1 \\end\{cases\} S∗(n,m)=\{ S∗(n−1,m−1),ifm%2=0S∗(n−1,m)\+S∗(n−1,m−1),ifm%2=1

这样得到的 S ∗ ( n , m ) S^\*(n,m) S∗(n,m)与 S ( n , m ) S(n,m) S(n,m)的奇偶性是一样的.对于 S ∗ ( n , m ) S^\*(n,m) S∗(n,m)当 m m m为奇数时和组合数的递推式一样,因为 S ∗ ( n − 1 , m − 1 ) = S ∗ ( n − 2 , m − 2 ) , ( ( m − 1 ) % 2 = 0 ) S^\*(n-1,m-1)=S\*(n-2,m-2),((m-1)\\%2=0) S∗(n−1,m−1)=S∗(n−2,m−2),((m−1)%2=0),所以 S ∗ ( n , m ) S^\*(n,m) S∗(n,m)的结果与 m m m列和 m − 2 m-2 m−2列有关,如果把奇数列单独拎出来的话,和组合数那个系数表很像:

![奇数列][format_png 1]

第一列是 C n ′ 0 C\_\{n'\}^0 Cn′0,第二列是 C n ′ 1 C\_\{n'\}^1 Cn′1, ⋯ \\cdots ⋯.第 m m m列对应的应该是 C n ′ m / 2 C\_\{n'\}^\{m/2\} Cn′m/2.行的关系算出来是 n ′ = n − 1 − m / 2 n'=n-1-m/2 n′=n−1−m/2.这 m m m是奇数时的情况,用同样的方法可以推出偶数时的关系,最后可以同一成这个:  
 S ∗ ( n , m ) = C n − 1 − m / 2 m + 1 2 − 1 S^\*(n,m)=C\_\{n-1-m/2\}^\{\\frac\{m+1\}\{2\}-1\} S∗(n,m)=Cn−1−m/22m\+1−1

对于组合数 C n m C\_n^m Cnm奇偶性的判断有这样一个快速的方法,如果 n & m = m n\\&m=m n&m=m,那么是奇数,否则是偶数.

## 代码实现 ##

#include <iostream>
    using namespace std;
    const int N = 100;
    
    void solve(int n, int m) {
        
        if( m > n){
        
            cout<< "0"<<endl;
            return;
        }else if( m == n){
        
            cout<< "1"<<endl;
            return;
        }else if( n * m == 0 ){
        
            cout << "0" << endl;
            return;
        }
        int x = n - 1 - m/2;
        int y = (m+1)/2 - 1;
        if( (x & y) == y){
        
            cout<<"1"<<endl;
        }else{
        
            cout<<"0"<<endl;
        }
    }
    
    int main(int argc, const char** argv) {
        
        int t;
        scanf("%d", &t);
        while(t--){
        
            int n, m;
            scanf("%d%d", &n, &m);
            solve(n, m);
        }
        return 0;
    }

## 补充 ##

[format_png]: /images/20230209/f6851a4246134ec597a7ecf28b645f8c.png
[POJ1430]: http://poj.org/problem?id=1430
[format_png 1]: /images/20230209/bd1dcef9045a4caa8fdaf4f64a33e13b.png