梅爾變換 CNN 詳情 - 梅爾變換 CNN,母函數,生成函數,斐波那契數列,機器學習,人工智能 mob64ca14038b36 博客

生成函數(母函數)

什麼是生成函數：wiki上的介紹

在數學中，某個序列梅爾變換 CNN_生成函數的母函數（又稱生成函數，英語：Generating function）是一種形式冪級數，其每一項的係數可以提供關於這個序列的信息。使用母函數解決問題的方法稱為母函數方法。

母函數可分為很多種，包括普通母函數、指數母函數、L級數、貝爾級數和狄利克雷級數。對每個序列都可以寫出以上每個類型的一個母函數。構造母函數的目的一般是為了解決某個特定的問題，因此選用何種母函數視乎序列本身的特性和問題的類型。

母函數，又稱生成函數，是ACM競賽中經常使用的一種解題算法，常用來解決組合方面的題目。

生成函數的定義：梅爾變換 CNN_斐波那契數列_02 稱梅爾變換 CNN_斐波那契數列_03 是序列梅爾變換 CNN_母函數_04 的生成函數。

小題

一、

有1克、2克、3克、4克的砝碼各一枚，能稱出哪幾種重量？每種重量各有幾種可能方案？

我們用母函數來解決這個問題

1個1克砝碼可以看成1+x^1,1表示不取，x^1表示取一個，以下同理
1個2克砝碼可以看成1+x^2
1個3克砝碼可以看成1+x^3
1個4克砝碼可以看成1+x^4

那麼生成函數就是

梅爾變換 CNN_梅爾變換 CNN_05

這個函數中可以看出重量為3克的方案有兩種，重量為7的方案有兩種，重量為10的有1種。

不難發現指數表示重量，係數表示方案數。

二、

求用1分、2分、3分的郵票貼出不同數值的方案數：
大家把這種情況和第一種比較有何區別？第一種每種是一個，而這裏每種是無限的。

那麼生成函數就是梅爾變換 CNN_生成函數_06

以展開後的x^4為例，其係數為4，即4拆分成1、2、3之和的拆分方案數為4；

即：4=1+1+1+1=1+1+2=1+3=2+2

三、

設有n個標誌為1,2,…,n的網袋，第i個(i=1,2,…n)網袋裏放有ni個球。不同網袋裏的球是不同的，而同一網袋裏的球則是沒有差別的，認為是相同的。詢問從中取r個球的方案數。

設生成函數梅爾變換 CNN_生成函數_07

最後指數為r的那一項的係數就是方案數。

總結一下，生成函數大多用來解決有限或無限物體的組合方案。

給出通用模板，其實就是暴力拆這個函數罷了。

#include<cstdio>
using namespace std;
int N,g[2][125];
int main(){
	while(~scanf("%d",&N)){
		for(int i=0;i<=N;++i) g[1][i]=1,g[0][i]=0;
		for(int i=2;i<=N;++i){
			for(int j=0;j<=N;++j)
			for(int k=0;k<=N-j;k+=i) g[i&1][j+k]+=g[1-(i&1)][j];
			for(int j=0;j<=N;++j) g[1-(i&1)][j]=0;
		}
		printf("%d\n",g[N&1][N]);
	}
	return 0;
}

以上是一些基礎，接下來給一道難題（反正我一點也不會，逃）：BZOJ4001

不會也沒有關係，我們慢慢來。