[组合数][高精度] Jzoj P3431 网络

素颜马尾好姑娘i 2021-11-02 10:22 243阅读 0赞

#### Description ####

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

# 题解 #

*  从(0,0)到(n,m)随便走的方案数为C(n+m,m)
 *  然后题目要求不能穿过y=x这条直线，也就是不能碰到y=x+1的直线
 *  那么我们考虑将一条不合法的路线沿着y=x+1对称过去，那么(n,m)对称过去的点就是(m-1,n+1)
 *  考虑Catalan数的证明过程，发现从原点走到对称点(m-1,n+1)的一条路径都可以对称回来，并对应着一条从原点走到终点(n,m)穿过y=x的直线的路径
 *  所以穿过y=x的路径数就是从原点走向对称终点的路径是也就是C(n+1+m-1,m-1)=C(n+m,m-1)
 *  所有答案就是C(n+m,m)=C(n+m,m-1)
 *  可以把式子化简一下：
 *  ![1220613-20190811102120674-382268460.png][]
 *  通分后得：
 *  ![1220613-20190811102411854-1072005810.png][]
 *  最后打个高精度就ok了

# 代码 #

1 #include <cstdio>
     2 #include <cstring>
     3 #include <algorithm>
     4 using namespace std;
     5 const int N=10000,M=N*10;
     6 struct num
     7 {
     8     int shu[N];
     9     friend num operator-(num y,num z) 
    10     {
    11         num x;memset(x.shu,0,sizeof(x.shu)),x.shu[0]=y.shu[0];
    12         for (int i=1;i<=x.shu[0];i++) 
    13         {
    14             x.shu[i]+=y.shu[i]-z.shu[i];
    15             if (x.shu[i]<0) x.shu[i]+=M,x.shu[i+1]--;
    16         }
    17         while (!x.shu[x.shu[0]]) x.shu[0]--;
    18         return x;
    19     }
    20     friend num operator*(num y,int z) 
    21     {
    22         num x;memset(x.shu,0,sizeof(x.shu)),x.shu[0]=y.shu[0];
    23         for (int i=1;i<=x.shu[0];i++) x.shu[i]+=y.shu[i]*z,x.shu[i+1]+=x.shu[i]/M,x.shu[i]%=M;
    24         while (x.shu[x.shu[0]+1]) x.shu[0]++;
    25         return x;
    26     }
    27 }ans;
    28 int p[N+5],c[N+5],n,m;
    29 void recout(int x,int f) { for(;x!=1;x/=p[x]) c[p[x]]+=f; }
    30 num C(int m,int n) 
    31 {
    32     num x;memset(x.shu,0,sizeof(x.shu)),x.shu[0]=x.shu[1]=1,memset(c,0,sizeof(c));
    33     for (int i=n+1;i<=m;i++) recout(i,1);
    34     for (int i=1;i<=m-n;i++) recout(i,-1);
    35     for (int i=1;i<=N;i++) for (int j=1;j<=c[i];j++) x=x*i;
    36     return x;
    37 }
    38 int main() 
    39 {
    40     for (int i=2;i<=N;i++) if (!p[i]) for (int j=1;j<=N/i;j++) p[i*j]=i;
    41     scanf("%d%d",&n,&m),ans=C(m+n,m)-C(m+n,m-1),printf("%d",ans.shu[ans.shu[0]]);
    42     for (int i=ans.shu[0]-1;i>=1;i--) printf("%05d",ans.shu[i]);
    43 }

转载于:https://www.cnblogs.com/Comfortable/p/11334105.html

[Image 1]: 
[1220613-20190811102120674-382268460.png]: /images/20211101/047b355af2cc453ca5f6a2a778282d49.png
[1220613-20190811102411854-1072005810.png]: /images/20211101/d28c8a3be99643efa4d83153700eaf32.png