数論——組合せ数(基礎)

最近、大爱洛谷の大系分駅で、そこでまたそこでランダムに问题を踊ります(⊙o⊙)...
それから奇妙な問題を踊った.
P 1869愚かな組み合わせの数のテーマの説明
最近先生は犬にどのように组み合わせの数を计算することを教えて、犬はまた1つの问题を思いつきました...
ワンちゃん定義C(N,K)は、N個の要素からK個の要素を繰り返し選択しないシナリオ数を表す.
犬が知りたいのはC(N,K)のパリティ.
もちろん、この日はいつも縦で123456789*987654321=?の人はあなたにそんなに自分をそんなに楽にさせないで、それは言います:“NとKはすべてかなり大きいかもしれません.”
しかし、犬も困っているので、あなたを見つけて、この問題を解決してもらいたいと思っています.
入力フォーマット:1行目:データのグループ数を表す正の整数t.2~2+t-1行目:2つの非負の整数NとK.(保証k<=n)
出力フォーマット:入力のセットごとに、C(N,K)が奇数の場合は1を出力し、そうでない場合は0を出力します.
入力サンプル#1:3 1 1 1 0 2 1出力サンプル#1:1 1 0データ範囲30%データ、n<=10^2 t<=10^4 50%データ、n<=10^3 t<=10^5 100%データ、n<=10^8 t<=10^5
テーマを見終わったら、oh、shit、組み合わせの数は何ですか.それから度娘を探します.
n個の異なる元素のうち、m(m≦n)個の元素を任意に取ってグループ化し、n個の異なる元素からm個の元素を取り出す組み合わせと呼ばれる.n個の異なる元素からm(m≦n)個の元素を取り出すすべての組合せの個数を、n個の異なる元素からm個の元素を取り出す組合せ数と呼ぶ.符号c(n,m)で表す.
ああ!この様子!あのグループの合数は計算しにくいのではないでしょうか.しかし、突然数字が大きいことに気づいたのは、高精度なのだろうか.
大切なことが来たのはパリティだけ....う~~~~ん
それから水の問題がほしいと思った!結果gg
次は問題解を研究する時だ!その結果不思議な知識が発見されました
数論Lucas定理:c(n,m)mod pの値を求めるために用いられ,pは素数(nからmの組合せを取り,モジュール上のp)である.C(n,k)≡C(n/p,k/p)*C(n%p,k%p)(mod p)パリティを求めるとp=2
それでは、関数で2を触って、最後に原式=c[i][j](i,j=0||1)を出すことができます.残りはc[i][j]に初期値を与えればいいのです
そしてすべてが简単になる

#include
int c[2][2], n, t, k;
int ans(int a, int b) 
{
    if (a < 2 && b < 2) return c[a][b];
    //       
    if (!ans(a%2, b%2)) return 0;
    //     ，      
    return ans(a/2, b/2);
    //               
}

int main() {
    //   c(0, 0)~c(1, 1) 
    c[0][0] = 1;
    c[0][1] = 0;
    c[1][0] = 1;
    c[1][1] = 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        printf("%d
", ans(n, k));
    }
    return 0;
}

ああ