1.糖果盒 nkoj 4052

问题:
何老板有很多颗相同的糖果，同时还有n个不同的糖果盒。何老板想把其中一些糖果放入这些盒子里，要求所有盒子里总的糖果数不超过m，问总共有多少种不同的方案？
每个盒子的容量无限大，可以选择装糖，也可以不装。
答案可能很大，mod p后在输出，p是一个素数。

解:
假设有k个糖果要装进n个糖果盒里面
增设空格子利用插板原理答案为\(c(n+m-1,{m-1})\)

所以不超过m的答案为\(\sum _{i=1}^{i=m} c(n+i-1,{i-1})\)
注意到\(c(n ,0) =1\) 所以可以换成\(c(n+1,0)\)就递推就行了,
我们有组合数公式 \(C(N,M)=C(N-1,M)+C(N-1,M-1)\)
于是就可以递推
最终答案为\(C(n+m,m)\)
code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,p;
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans%p;
}
ll C(ll x,ll y)
{
    ll A=1,B=1;
    for(int i=1;i<=y;i++)
    {
        A=(A*(x-y+i)%p)%p;
        B=(B*(i)%p)%p;
    }
    return (A*ksm(B,p-2))%p;

}
ll lucas(ll x,ll y)
{
    if(y==0) return 1;
    return (C(x%p,y%p)*lucas(x/p,y/p))%p;
}
int main()
{
    cin>>n>>m>>p;
    cout<<lucas(n+m,m)%p;
}

2.nkoj 4502 装糖果

NK小卖部有m种不同口味的糖果出售。
何老板委托你去买2*n颗糖装入两个盒子里，每个盒子里有一排n个方格，每个方格只能装1颗糖。何老板要求，两个盒子里不能有相同口味的糖果(同一个盒子里可以有口味相同的)。
那么问题来了，总共有多少种方案呢？
1≤n,m≤2000

此题有两种做法

1.
首先两个盒子就是两个变量
我们想到先确定一个变量
那么我们就枚举第一个箱子确定装的\(i\)种糖果那么第二个箱子就装的
\(m-i\)种糖果那么第二种箱子的方案数为 \((m-i)^n\)
讨论第一种箱子
你就会想到是将n个盒子划分成i个非空集合这不就是第二类斯特林数吗???
但是他有排列顺序没关系我们 times \({A_i^i}\) 就行了(这里没有搞懂准备明天再去问)
答案就是\(\sum _{i=1}^{i=m-1} (C(m,i)\times f[n][i]\times(A_i^i)\times (m-i)^n)\)

糖果

组合数例题

1.糖果盒 nkoj 4052

2.nkoj 4502 装糖果