String

1
2 2

2

题意为一个字符串只由0，1组成，且0有m个，1有n个，要求该字符串中任意的前缀中1的个数不能小于0的个数，问这样的字符串一共有多少个。结果对20100501取模。

将构造字符串的过程转化到二维坐标上去，1用y表示，0用x表示，从坐标(0,0)出发，0代表向右走(x增加)，1代表向上走(y增加)，因为0有m个，1有n个，所以最后到达的坐标为

（m,n) ，单纯考虑从0,0走到m,n一共有C(n+m,m)种方法，又因为任意前缀中1的个数不能小于0，所以y>=x,也就是合法走的路线经过的坐标要么在y=x上，要么在其上边，那么

不合法的路线经过的坐标则满足y

所以不合法的路径一定与y=x-1相交，找到(0,0)关于y=x-1的对称点(1,-1)，从(1,-1)走到（m,n）一定与直线y=x-1相交，因为m,n在该直线的上边，1,-1在该直线的下

边。在这里设交点为P，那么路线就以P为分割点可以分为两部分，上面一部分取个名字叫不合法路线，下面一部分取个名字叫合法路线。那么从1,-1走到m,n有多少种方法也就

是从0,0走到m,n的不合法的方法数。仔细想一想为什么呢？为什么要找对称点，在对称直线一侧走的路线总可以在另一侧找到路线与之对称，刚才我们从1,-1走到m,n的那一段

合法路线沿着y=x-1再对称过去，不合法路线就不用对称了，因为不合法路线已经与y=x-1相交了（其实那一段合法路线的最后一个点也与y=x-1相交），这样就有了从0,0到m,n

的一种方案，总的来说就是对于从1,-1到m,n的每一条路线，都有从0,0到m,n关于y=x-1对称的一条路线与之对应。从1,-1走到m,n方法数为C (m+n,m-1)。

所以本题的答案就是C(n+m,m) - C (m+n,m-1)。

那么接下来的问题就是求上面的式子了。

上面式子最终可以化为 (n+1-m)*(n+m)! / (m! *(n+1)!)

直接求肯定不行，因为涉及到了除法的取模运算。

考虑整数唯一分解定理：

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数

那么可以把每个数都化成这样的形式，然后上下对于相同的素因子进行约分，也就是指数相减，对于一个素数pi,我们只要知道最终pi的指数是多少就可以了（上下都约分后的指数）

还有把阶层看作一个数,比m! 怎样求m!里面素数2的指数呢？

cnt=0; while(m) { m/=2; cnt+=m; } 就可以了，为什么呢？考虑m=4，则m!= 4*3*2*1, 第一次m/=2，是计算m!里面有多少个数能整除2的（有4，2）,所以cnt+=2，有两个数贡献了两个素数2，接下来第二次m/=2，是计算m!里面有多少个数能整除4的，有1个数又贡献了一个素数2.

代码：

#include 
  
   
#include 
   
     using namespace std; const int maxn=1000000; const int mod=20100501; bool isprime[maxn*2+10]; int prime[maxn*2+10]; int len=0;//素数的个数 int n,m; int t; void sieve(int n)//筛n以内的素数 { for(int i=0;i<=n;i++) isprime[i]=1; isprime[0]=isprime[1]=0; for(int i=2;i<=n;i++) if(isprime[i]) { prime[len++]=i; for(int j=2*i;j<=n;j+=i) isprime[j]=0; } } int cal(int p,int n)//计算n!里面有多少个p相乘 { int ans=0; while(n) { n/=p; ans+=n; } return ans; } int main() { sieve(maxn*2); cin>>t; while(t--) { long long ans=1;//记得要用long long cin>>n>>m; int nm=n+1-m; for(int i=0;i
    
     =mod) ans%=mod; } } cout<