首页 > 代码库 > hdu2125(数学)

hdu2125(数学)

2024-08-06 22:27:37   218人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2125

题意：N×M的网格其中有一条边坏掉了，问从起点到终点的放法数。

分析：数学公式

如果没有坏边的话，总放法数是CN-1(M+N-2) 

因为每种方法都要走(M+N-2)步，向上走N-1步，向下走M-1步

现在考虑一条坏边，那么就计算经过这条坏边的方案数然后从总数里面减去即可

经过坏边的放法数就是从起点到(x1, y1)的放法数×从(x2, y2)到终点的放法数

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;LL c[50][50];void init(){    for(int i=0;i<=40;i++)c[i][0]=c[i][i]=1;    for(int i=1;i<=40;i++)        for(int j=1;j<i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];}int main(){    int n,m,x1,y1,x2,y2;    init();    while(scanf("%d%d",&n,&m)>0)    {        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);        if(x1+y1>x2+y2)        {            swap(x1,x2);            swap(y1,y2);        }        printf("%I64d\n",c[n+m-2][m-1]-c[x1+y1][x1]*c[m+n-2-x2-y2][m-1-x2]);    }}
View Code

 

hdu2125(数学)


联系
我们