UPC8428 网格VI

问题 s: 网格VI

时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 4
[提交] [状态] [命题人:admin]

题目描述

某城市的街道呈网格状，左下角坐标为A(0, 0)，右上角坐标为B(n, m)，其中n >= m。现在从A(0, 0)点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点(x, y)都要满足x >= y，请问在这些前提下，到达B(n, m)有多少种走法。

输入

仅有一行，包含两个整数n和m，表示城市街区的规模。

输出

仅有一个整数和一个换行/回车符，表示不同的方案总数。

样例输入

6 6

样例输出

提示

100%的数据中，1 <= m <= n <= 5 000

一道组合数学的题目，公式推导如下。

但是这道题目很显然需要高精度乘法和高精度除法，但是由于我很懒，不想写高精度除法，于是想到了用质因数分解的方法，将高精度除法转换成了质因数指数的减法来做。

这样只需要在最后处理答案的时候使用高精度乘法将答案处理出来即可，实测跑的飞快，比一般的高精度除法处理要快的多。

AC代码如下

#include <bits/stdc++.h>
#define rint register int
typedef long long ll;
using namespace std;
const int N=5e3;
const int mod=1e8;
struct bign
{
    ll val[1000];
    int len;
    bign()
    {
        memset(val,0,sizeof val);
    }
    bign operator *(const bign &t)const
    {
        bign res;
        for(rint i=0; i<len; i++)
            for(rint j=0; j<t.len; j++)
            {
                res.val[i+j]+=val[i]*t.val[j];
                res.val[i+j+1]+=res.val[i+j]/mod;
                res.val[i+j]%=mod;
            }
        res.len=len+t.len;
        if(res.val[res.len-1]==0)res.len--;
        return res;
    }
};
bign transbign(ll x)
{
    int j=0;
    bign res;
    while(x)
    {
        res.val[j++]=x;
        x/=mod;
    }
    res.len=j;
    return res;
}
void write(bign x)
{
    int i=x.len;
    printf("%lld",x.val[--i]);
    while(i)printf("%08lld",x.val[--i]);
    puts("");
}
int prime[2*N+5],cnt;
bool vis[2*N+5];
void erla()
{
    for(int i=2; i<=2*N; i++)
    {
        if(!vis[i])prime[++cnt]=i;
        for(int j=1; j<=cnt&&prime[j]*i<=2*N; j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
bign qpow(bign a,ll b)
{
    bign ans;
    ans.val[0]=1;ans.len=1;
    while(b)
    {
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int up[N*2],down[N*2];
bign ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    erla();
    int n,m;
    cin>>n>>m;
    for(int i=n+2; i<=n+m; i++)
    {
        int k=i;
        for(int j=1; j<=cnt&&prime[j]<=k; j++)
        {
            int p=prime[j];
            while(k%p==0)
            {
                up[p]++;
                k/=p;
            }
        }
    }
    int k=n-m+1;
    for(int j=1; j<=cnt&&prime[j]<=k; j++)
    {
        int p=prime[j];
        while(k%p==0)
        {
            up[p]++;
            k/=p;
        }
    }
    for(int i=2; i<=m; i++)
    {
        int k=i;
        for(int j=1; j<=cnt&&prime[j]<=k; j++)
        {
            int p=prime[j];
            while(k%p==0)
            {
                down[p]++;
                k/=p;
            }
        }
    }
    bign t;
    ans.val[0]=1;ans.len=1;
    for(int i=1;i<=cnt;i++)
    {
        int p=prime[i];
        int c=up[p]-down[p];
        if(c==0)continue;
        //cout<<p<<" "<<up[p]<<" "<<down[p]<<endl;
        t=transbign(p);
        t=qpow(t,c);
        ans=ans*t;
    }//cout<<ans.len<<endl;
    write(ans);
    return 0;
}