a679. CPE：Binary Stirling Numbers (UVa 1118)

題目描述

第二類 Stirling 數 S(n,m) 表示將 n 個不同物件分成 m 個非空、無順序子集合的方法數。例如 S(4,2)=7。請計算 S(n,m) mod 2，也就是判斷其奇偶性。其遞迴關係為 S(n,m)=mS(n−1,m)+S(n−1,m−1)，邊界 S(n,1)=S(n,n)=1。

輸入格式

第一行為測試筆數，其後每筆給 n、m，1 ≤ m ≤ n ≤ 1,000,000,000。各筆資料間有空白行。

輸出格式

每筆輸出 0 或 1，兩筆輸出之間留一空白行。

題目來源：UVa 1118 — Binary Stirling Numbers，CPE 歷屆試題。 原題：https://onlinejudge.org/external/11/1118.pdf