自己寫一遍插板法的東西，順便補(bǔ)上 oiwiki 上沒有的一個證明。

偏向整理，別人估計不知道我在干什么。

基本模型：\(x_0+x_1+...+x_k=n\) 的正整數(shù)或非負(fù)整數(shù)解數(shù)量，可以抽象為元素組的劃分。

正整數(shù)解的數(shù)量

也是插板法最基本的模型。

有 \(n\) 個相同的元素，將它們分成 \(k\) 組，并且要求每組不是空的，求統(tǒng)共有多少種分配方法。

注意是元素相同組別不同。

為什么標(biāo)粗相同的元素？不相同就不能用插班法了，插班法依賴于元素的不可區(qū)分性。

我們將這個問題視作把 \(k-1\) 個隔板放入 \(n-1\) 個空隙之間。

也就是 \(\binom{n-1}{k-1}\)。

問題等同于求解 \(x_0+x_1+...+x_k=n\) 的正整數(shù)解數(shù)量。

這里的 \(x_i\) 表示 \(i\) 組的個數(shù)。

非負(fù)整數(shù)解的數(shù)量

現(xiàn)在去掉限制每組不是空，也就是允許每組是空的。

由于元素的等同的，我們可以先添加 \(k\) 個元素，再進(jìn)行上述插班法，最后再抽去我們添加的元素。

得到答案 \(\binom{n+k-1}{k-1}\)=\(\binom{n+k-1}{n}\)。

問題等同于求解 \(x_0+x_1+...+x_k=n\) 的非負(fù)整數(shù)解數(shù)量。

以上便是基本的兩大模型，我們遇到問題可以試著轉(zhuǎn)化模型。

下界不同的整數(shù)解的數(shù)量

我們規(guī)定對于第 \(i\) 組必須至少要分配到 \(a_i\) 個元素。

這個時候我們選擇轉(zhuǎn)化成數(shù)學(xué)模型，問題變復(fù)雜時我們不能總是依賴直觀。

我們設(shè) \(x_i\) 為每組的個數(shù)，嘗試轉(zhuǎn)化成我們熟悉的數(shù)學(xué)模型。

\(x_0+x_1+...+x_k=n\)

設(shè) \(x_i'=x_i-a_i\)，這個樣子我們就可以轉(zhuǎn)化成以下東西。

\(x_0'+x_1'+...+x_k'=n - \sum a_i\)

其中 \(x_i\) 必須是非負(fù)整數(shù)。

這不就轉(zhuǎn)化成之前的問題了。

答案自然是 \(\binom{n-\sum a_i +k-1}{n-\sum a_i}\)。

不相鄰的排列數(shù)量

有 \(1到n\) 的自然數(shù)可以選(一個排列)，我們需要選擇 \(k\) 個數(shù)，使得這些數(shù)在大小上互相不相鄰，請問有多少種選法。

這個看似不太可以使用插板法分析，明明元素之間并不是相同的。

但是我們發(fā)現(xiàn)兩個離得最近的被選擇的數(shù)之間的大小差異是相同的。

我們考慮如下轉(zhuǎn)化。

設(shè) \(x_i\) 為比 \(x\) 小的最大數(shù)與 \(x\) 中間的沒有被選的數(shù)量，\(miao\) 表示比 \(k\) 大的沒有被選的數(shù)量。

這個樣子我們可以列出來式子 \(x_1+x_2+...+x_k+miao=n-k\)。

其中 \(x_1 \ge 0\)，其他 \(x_i \ge 1\)，\(miao\ge 0\)。

這個樣子就成了之前的老問題。

我們轉(zhuǎn)化一下，仿照上邊的思路。

\(x_1'=x_1+1\)，\(miao'=miao+1\)。

這樣就成了第二個問題。

\(x_1'+x_2+...+x_k+miao'=n-k+2\)

\(x_i,miao\) 都是非負(fù)整數(shù)。

直接套剛才式子得出答案是 \(\binom{n-k+1}{k}\)

為什么不是 \(k-1\)？\(miao\) 也是元素啊。

簡單的例題 P2638

復(fù)習(xí)玩排列組合正好寫到一道，遂補(bǔ)上去。

一共有 \(n\) 個儲存區(qū)，儲存區(qū)里邊可以放任意多 0 和 1，當(dāng)然，也可以什么都不放。

我們的 0 和 1 的總數(shù)量是有限的，放的時候并不一定要放完才行。

0 一共有 \(a\) 個，1 一共有 \(b\) 個。

詢問一共有多少種方法。

我一開始并沒有思路，于是嘗試將問題轉(zhuǎn)化為數(shù)學(xué)模型來分析。

一轉(zhuǎn)化出來就知道怎么做了。

設(shè) \(x_i\) 表示 \(i\) 格子中的 0 個數(shù)

設(shè) \(y_i\) 表示 \(i\) 格子中的 1 個數(shù)。

枚舉使用了 \(i\) 個 0，\(j\) 個 1。

我們得到數(shù)學(xué)問題，分別求以下的非負(fù)整數(shù)解個數(shù)。

\(x_1+...+x_n=i\)

\(y_1+...+y_n=j\)

因為兩個互不影響，所以把答案乘起來就行了，怎么算我就不多說了，和上邊顯然是一樣的。

形式化就是求解 \(\sum_{i=0}^{a}\sum_{j=0}^\binom{i+n-1}{i}\times\binom{j+n-1}{j}\)

有個神經(jīng)病的 hack 需要 __int128 才可以通過。

代碼↓

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int MN=51;
int C[MN][MN], ans=0;
void Pre(){
	for(int i=0; i<MN; ++i){
		for(int j=0; j<=i; ++j){
			if(!j) C[i][j]=1;
			else C[i][j]=C[i-1][j]+C[i-1][j-1];
		}
	}
}
int n, a, b;
inline void Read(int &n){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    n=x*f;
}
inline void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	Pre(); Read(n), Read(a), Read(b);
	for(int i=0; i<=a; ++i){
		for(int j=0; j<=b; ++j){
			ans+=C[i+n-1][i]*C[j+n-1][j];
		}
	}
	print(ans);
	return 0;
}