I - Saving Beans HDU - 3037

题意

n个树中取小于等于m个豆子，有多少种取法？

题解

假设n个树中取m个豆子。用隔板法，可以转化为在m个人中插入n-1个人有多少种方法。第一个人可以插入的位置有m+1个，第二个人可以插入的位置有m+2个。那么一共有(m+1)(m+2)...(m+n-1) = C(m+n-1,n-1)(n-1)!。而计算收取豆子时是不考虑树的位置的，计算结果还要除以(n-1)!，因此共有C(n + m - 1,m)种方法。再计算m从0到m，C(n-1,0) + C(n,1) + ...+C(n+m-1,m) = C(n+m,m)。再用lucas定理计算

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll n,m,p;
ll f[maxn];
void init()
{
    f[0] = 1;
    for(int i = 1;i <= p;i++)
    {
        f[i] = f[i - 1] * i % p;
    }
}
ll pow_mod(ll a,ll n,ll p)
{
    ll res = 1;
    while(n)
    {
        if(n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}
ll comb(ll n,ll m)
{
    if(n < m) return 0;
    return f[n] * pow_mod(f[m] * f[n - m] % p,p - 2,p) % p;
}
ll lucas(ll n,ll m)
{
    if(n < m) return 0;
    if(m == 0) return 1;
    return comb(n % p,m % p) * lucas(n / p,m / p) % p;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld %lld %lld",&n,&m,&p);
        init();
        printf("%lld\n",lucas(n + m,m));
    }
    return 0;
}

J - 小兔的棋盘 HDU - 2067

题解

求不经过对角线的网格路径数，是卡特兰数的模型。既可以在下半部分走，也可以在上半部分走，所以结果要乘2。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll kart[36];
void init()
{
    kart[0] = kart[1] = 1;
    for(int i = 2;i < 36;i++)
    {
        for(int j = 0;j < i;j++)
        {
            kart[i] += kart[j] * kart[i - j - 1];
        }
    }
}
int main()
{
    init();
    ll n,cas = 0;
    while(scanf("%lld",&n) && n != -1)
    {
        printf("%lld %lld %lld\n",++cas,n,kart[n] * 2);
    }
    return 0;
}