【题解】洛谷P1869愚蠢的组合数

前往：我自己搭建的博客

题目

洛谷P1869愚蠢的组合数

题解

由于n较大，考虑使用卢卡斯定理，C(n,m) mod 2=0/1，即可判断奇偶性。C(0,0)=1,C(1,1)=1,C(0,1)=0,C(1,0)=1。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m; int C[2][2]; int lucas(int n,int m) {return n<2&&m<2 ? C[n][m] : lucas(n/2,m/2)*lucas(n%2,m%2)%2;} int main() { C[0][0]=C[1][1]=C[1][0]=1,C[0][1]=0; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); if(lucas(n,m)) printf("1\n"); else printf("0\n"); } return 0; }

 优化：考虑lucas定理中的两个操作（n/p和n mod p），如果反复执行这样的操作，直至n<p，那么这个过程相当于将n,m进行p进制分解，然后将p进制下的每一位分别计算组合数，并相乘。此题p=2，就是二进制分解。如果出现某一位，m为1，n为0，则结果为0，否则为1。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); if((n&m)==m) printf("1\n"); else printf("0\n"); } return 0; }