hdu2125(数学)

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

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

分析：数学公式

如果没有坏边的话，总放法数是C^N-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 10010
using 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
",c[n+m-2][m-1]-c[x1+y1][x1]*c[m+n-2-x2-y2][m-1-x2]);
    }
}