首页 > ACM题库 > HDU-杭电 > HDU 3398-String-数论-[解题报告]HOJ
2014
03-23

HDU 3398-String-数论-[解题报告]HOJ

String

问题描述 :

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?

输入:

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

输出:

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

样例输入:

1
2 2

样例输出:

2

好难的题目啊,是cantalon数的一般情况啊,公式为c(a+b,b)-c(a+b,b-1),一开始想从cantalon推这一题,白浪费了一个小时,又是打了m,n的表和组合数的表,才推了这公式

写完提交后无限WA,直到练习赛时间过了才想起来StringString是我求的com(a+b, b)-com(a+b,b-1)可能为负值,因为a>b不代表a%p>b%p,即(a-b)%p
= ((a%p-b%p)+p)%p而不是a%p-b%p,贴个临时的代码,好像代码有点冗长,再修改修改。(已修改)

time:1718ms

//calc(n,k)=n!/(k!*(n-k)!)
//n!    =2^a1*3^a2*5^a3……
//k!    =2^b1*3^b2*5^b3……
//(n-k)!=2^c1*3^c2*5^c3……
#include<iostream>
#include<string>
using namespace std;
const long long maxn=2000000+1000;
const long long p=20100501;
int cnt=0;
bool not_prime[maxn];
int prime[maxn/10],a[maxn/10],b[maxn/10],c[maxn/10];
void init()//求素数表
{
    memset(prime,0,sizeof(prime));
    memset(not_prime,0,sizeof(prime));
    for(int i=2;i<maxn;i++)
    {
        if(!not_prime[i])   prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            not_prime[i*prime[j]]=1;
            if(!(i%prime[j]))   break;
        }
    } 
    //cout<<cnt<<endl;
}
inline long long fin_fac(long long n,long long q)    //n!中q因子个数
{
    long long ans=0;
    while(n)
    {
        ans+=n/q;
        n/=q;
    }
    return ans;
}
inline long long fast_pow(long long a,long long k)       //a^k%p
{
    long long ans=1,t=a;
    while(k)
    {
        if(k&1) ans=ans*t%p;
        t=t*t%p;
        k>>=1;
    }
    return ans;
}
 long long com(int n,int k)  //calc C(n,k)%p=(n!/(k!*(n-k)!))%p = (2^(a1-b1-c1)*3^(a2-b2-c2)*……)%p
{
    long long ans=1;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(int i=0;prime[i]<=n;i++)
        a[i]=fin_fac(n, prime[i]);
    for(int i=0;prime[i]<=k;i++)
        b[i]=fin_fac(k,prime[i]);
    for(int i=0;prime[i]<=n-k;i++)
        c[i]=fin_fac(n-k,prime[i]);
    for(int i=0;prime[i]<=n;i++)
        ans=ans*fast_pow(prime[i],a[i]-b[i]-c[i])%p;
    return ans;
}
int main()
{
    init();
    long long t;
    cin>>t;
    while(t--)
    {
        long long a,b;
        cin>>a>>b;
        if(a<b)cout<<0<<endl;
        else    if(b==0)    cout<<1<<endl;
        else
        cout<<((com(a+b, b)-com(a+b,b-1))%p+p)%p<<endl;
    }
    return 0;
}

删了a,b,c三个数组,其它也有调整了一下,快了一倍

time:812ms

#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=2000000+1;
const int p=20100501;
bool not_prime[maxn];
int prime[maxn/10];

int fin_fac(int n,int q)
{
    if(q==0||n<q)    return 0;
    int ans=0;
    while(n)
    {
        n/=q;
        ans+=n;
    }
    return ans;
}
ll fast_pow(ll a,ll k)
{
    if(k==1)    return a;
    ll ans=1,t=a;
    while(k)
    {
        if(k&1) ans=ans*t%p;
        t=t*t%p;
        k>>=1;
    }
    return ans;
}
ll com(int n,int k)
{
    ll ans=1,tmp;
    for(int i=0;prime[i]<=n;i++)
        ans=ans*fast_pow(prime[i],fin_fac(n, prime[i])-fin_fac(k,prime[i])-fin_fac(n-k,prime[i]))%p;
    return ans;
}
int main()
{
    int t,a,b,cnt=0;
    for(int i=2;i<maxn;i++)
    {
        if(!not_prime[i])   prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            not_prime[i*prime[j]]=1;
            if(!(i%prime[j]))   break;
        }
    } 
    cin.sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<(com(a+b, b)-com(a+b,b-1)+p)%p<<endl;
    }
    return 0;
}

刚刚发现计算com(a+b,b)与com(a+b,b-1)几乎是重复计算了一次,果断改之(也避免了(a-b)%c小于0的问题!)

直接计算com(a+b,b)-com(a+b,b-1)=(a+b)!(n+1-m)/(m!(n+1)!) 注意!不要计算ans=(a+b)!/(m!(n+1)!),再计算ans*(n+1-m),因为不能保证(a+b)!/(m!(n+1)!)可以整除!

time:421MS

#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=2000000+1;
const int p=20100501;
bool not_prime[maxn];
int prime[maxn/10];

int fin_fac(int n,int q)
{
    if(q==0||n<q)    return 0;
    int ans=0;
    while(n)
    {
        n/=q;
        ans+=n;
    }
    return ans;
}
ll fast_pow(ll a,ll k)
{
    if(k==1)    return a;
    ll ans=1,t=a;
    while(k)
    {
        if(k&1) ans=ans*t%p;
        t=t*t%p;
        k>>=1;
    }
    return ans;
}
int fac(int n,int k)
{
    if(k==0)    return 0;
    int t=0;
    while(n%k==0)
    {
        n/=k;t++;
    }
    return t;
}
ll calc(int n,int m)
{
    ll ans=1;
    for(int i=0;prime[i]<=n+m;i++)
        ans=ans*fast_pow(prime[i], fac(n+1-m,prime[i])+fin_fac(n+m, prime[i])-fin_fac(m, prime[i])-fin_fac(n+1, prime[i]))%p;
    return ans;
}
int main()
{
    int t,a,b,cnt=0;
    for(int i=2;i<maxn;i++)
    {
        if(!not_prime[i])   prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
        {
            not_prime[i*prime[j]]=1;
            if(!(i%prime[j]))   break;
        }
    } 
    cin.sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<calc(a, b)<<endl;
    }
    return 0;
}

发现有15 ms,32ms过的,若哪位大仙知道,求赐教啊!

刚刚找到的公式的推导:

参考自:http://apps.hi.baidu.com/share/detail/17473477

①:我们设初始在坐标系的原点(0,0),从字符串第一位开始,碰到一个1就向上走,碰到一个0就向右走,那么由n个1、m个0组成的字符串最后必定走到(n,m)点,即满足由n个1、m个0组成的字符串的个数为C(n+m,n) = C(n+m,m) (满足n+m长度内n个长度走1或者m个长度走0)。

②:对于任意前缀中1的个数不少于0的个数的字符串的个数这个条件,可以看成是坐标系中,从(0,0)点走到(m, n)点,并且跟y=x-1这条直线不相交的方案数。又因为(0,0)点关于直线y=x-1的对称点是(1,-1),而从(1,-1)点走到(m, n)点的所有方案一定都会与直线y=x-1相交,对于这些方案,将从(1,-1)点到与y=x-1的第一个交点之间的路径关于y=x-1对称翻转过去,就可以得到所有不满足题意的从(0,0)点走到(m, n)点的方案,于是最终答案就是C(n+m, n)-C(n+m,n+1)。

第一点一开始就看出来了,第二点的转化才是关键的啊

参考:http://blog.csdn.net/wxfwxf328/article/details/7213498


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.