我就不吐槽这题面确实不怎么和谐了、、

直接求组合数大致是一个nlogn级别的工程、在这里显然是不可接受的、

于是我们用到了lucas定理、

这个定理的内容大致可以被表述为：

C(A,B)与A和B分解为P进制后各对应位数的组合数的乘积对P同余、

我也不会严格证明、、大致可以自己想想、、

 

Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int p=10007;int a[11],b[11];int n,m,t,ans;int pow(int x,int k){	if 	(k==0)   return 0;	if  (k==1)   return x;	int now=pow(x,k/2);	now=(now*now)%p;	if  (k&1)   now=now*x%p;	return now;}int c(int aa,int bb){	if	(bb==0)  return 1;	if  (aa
          
           aa-bb;i--) cur=cur*i%p; for (int i=1;i<=bb;i++) cur=cur*pow(i,p-2)%p; return cur;}int main(){ scanf("%d",&t); while (t--){ scanf("%d%d",&m,&n); int len1=0,len2=0,ans=1; while (m){ a[len1++]=m%p; m/=p; } while (n){ b[len2++]=n%p; n/=p; } for (int i=0;i