首页 > 代码库 > [ACM] HDU 3398 String (从坐标0,0走到m,n且不能与y=x-1相交的方法数,整数唯一分解定理)

[ACM] HDU 3398 String (从坐标0,0走到m,n且不能与y=x-1相交的方法数,整数唯一分解定理)

String



Problem Description
Recently, lxhgww received a task : to generate strings contain ‘0‘s and ‘1‘s only, in which ‘0‘ appears exactly m times, ‘1‘ appears exactly n times. Also, any prefix string of it must satisfy the situation that the number of 1‘s can not be smaller than the number of 0‘s . But he can‘t calculate the number of satisfied strings. Can you help him?
 

Input
T(T<=100) in the first line is the case number.
Each case contains two numbers n and m( 1 <= m <= n <= 1000000 ).
 

Output
Output the number of satisfied strings % 20100501.
 

Sample Input
1 2 2
 

Sample Output
2
 

Author
lxhgww
 

Source
HDOJ Monthly Contest – 2010.05.01 


解题思路:

题意为一个字符串只由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<x,也就是路线不能与y=x-1相交,因为只要一相交,就不满足1的个数不能小于0的个数。

所以不合法的路径一定与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 <iostream>
#include <algorithm>
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<len&&prime[i]<=(n+m);i++)//prime[i]<=(n+m)是因为拆成素数幂相乘的形式该素数不会大于n+m,最大(n+m)!   (n+m)*(n+m-1)*(n+m-2).....
        {
            int cnt=0;//分解为素数prime[i]的指数是多少
            while(nm%prime[i]==0)//nm中有多少个prime[i],也就是把nm分解后prime[i]的指数
            {
                nm/=prime[i];
                cnt++;
            }
            cnt=cnt+cal(prime[i],n+m)-cal(prime[i],m)-cal(prime[i],n+1);//加上分子的指数再减去分母的指数
            for(int j=1;j<=cnt;j++)
            {
                ans=ans*prime[i];
                if(ans>=mod)
                    ans%=mod;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}



[ACM] HDU 3398 String (从坐标0,0走到m,n且不能与y=x-1相交的方法数,整数唯一分解定理)