hdu5698 百度之星2016round2b第3题

这题首先是找规律推公式，然后就是组合数学的知识了。

题目是问到第n行第m列的格式有几种方案，我们可以用手算的方法列出当n和m比较小时的所有答案

比如我列出以下8*8的矩阵

矩阵上的数表示从那个位置到最右下角一共有多少种方案。

求每个位置的值也简单，就是把它右下角的所有数加起来即可。

那么，把这个矩阵倒过来看，就是想要的结果矩阵了。

规律也很容易发现，首先，矩阵是对称的，所以我是只考虑m>=n的情况。

然后，可以发现每个位置的数就是一个组合数C(m + n - 4, n - 2)

最后就是求组合数取模了，C(m + n - 4, n - 2) %

然而，多年没做题的我，并不会组合数取模。找了以前的模板，是竹教主写的，看了好半天才明白，等我打完的时候，比赛刚结束。

比赛结束后交了一次，果然a了T_T

以下是代码

/*

 * baidu/win.cpp

 * Created on: 2016-5-22

 * Author    : ben

 */

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#include <stack>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <functional>

#include <numeric>

#include <cctype>

using namespace std;

typedef long long LL;

LL Ext_gcd(LL a, LL b, LL &x, LL &y) {

    if (b == ) {

        x = , y = ;

        return a;

    }

    LL ret = Ext_gcd(b, a % b, y, x);

    y -= a / b * x;

    return ret;

}

LL Inv(LL a, int m) { ///求除数a对m的逆元；

    LL d, x, y, t = (LL) m;

    d = Ext_gcd(a, t, x, y);

    if (d == )

        return (x % t + t) % t;

    return -;

}

void work(int n, int m) {

    int i;

    const int mod = ;

    LL sum = ;

    for (i = n - m + ; i <= n; i++) {

        sum *= (LL) i;

        sum %= mod;

    }

    LL tmp = ;

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

        tmp *= i, tmp %= mod;

    sum *= Inv(tmp, mod);

    sum %= mod;

    printf("%I64d\n", sum);

}

int main() {

    int n, m;

    while (scanf("%d%d", &n, &m) == ) {

        if (m < n) {

            int tmp = m;

            m = n;

            n = tmp;

        }

        work(m + n - , n - );

    }

    return ;

}

巴特西

hdu5698 百度之星2016round2b第3题

最新文章

热门文章