hdu2125(数学)

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

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

分析：数学公式

如果没有坏边的话，总放法数是C

因为每种方法都要走(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[][];

void init()

{

    for(int i=;i<=;i++)c[i][]=c[i][i]=;

    for(int i=;i<=;i++)

        for(int j=;j<i;j++)c[i][j]=c[i-][j]+c[i-][j-];

}

int main()

{

    int n,m,x1,y1,x2,y2;

    init();

    while(scanf("%d%d",&n,&m)>)

    {

        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-][m-]-c[x1+y1][x1]*c[m+n--x2-y2][m--x2]);

    }

}