一般型母関数の詳細とそのテンプレートタイプ
PS:一般型母関数(つまり生成関数)に初めて触れたのか、離散数学の教科書でコードを叩くこともあまりできず、手動で計算できるだけだったのか、母関数について詳しく紹介します.
一般型の母関数は生成関数とも呼ばれ、
1.定義:G(x)=a 0+a 1*x+a 2*x^2+...+an*x^n + ...,G(x)はシーケンス{an}の生成関数である.
Eg:{C(n,m)}の生成関数は(1+x)^m,{k^n}の生成関数はG(x)=1+k*x+k^2*x^2+.==1/(1-k*x)
2.基本モデル:
1.分銅の問題:
今分銅が1グラム2個、分銅が2グラム1個、分銅が4グラム2個あるとしたら、どのような重量を量ることができますか.案数はいくらですか.
解:
不定方程式をリストできます.
1*x1 + 2*x2 + 4*x3 == r;(0<=x1<=2, 0<=x2<=1, 0<=x3<=2)
したがって、対応する親関数は次のとおりです.
G(x) = (1+x+x^2) * (1+x^2) * (1+x^4+x^8) = 1+x+2*x^2+x^3+2*x^4+x^5+2*x^6+x^7+2*x^8+x^9+2*x^10+x^11+x^12
ここで、xの指数は秤量可能な重量であり、xの前の係数は重量が指数であることができる案数である.
2.正の整数分割の問題:
G(x) = (1+x+x^2+x^3+x^4+...)* (1+x+x^2+x^3+x^4+...)* (1+x+x^2+x^3+x^4+...)*...*(n回乗算)
3.ボールを取る問題:
ポケットの中は白いボールの2つがあって、赤いボールの3つ、黄色のボールの1つ、袋の中から3つのボールを探し出して何种类の取り方がありますか?
G(x)= (1+x+x^2) * (1+x+x^2+x^3) * (1+x)
1はボールを取らないことを表して、xは1つのボールを取って、x^2は2つのボールを取って、x^3は3つのボールを取って
だから私たちはx^3の前の係数を要求するだけでいいです.X^mの前の係数はm個のボールを触るのに必要な方法数を表しているからです.
4.ボールを放つ問題:
n個のボールがm個の箱の中に置いて、何種類の異なる置き方がありますか?
G(x) = (1+x+x^2+x^3+...x^k+...)*(1+x+x^2+x^3+...x^k+...)*...(全部でn項あり)我々が要求するのはx^mの前の係数,すなわち方法数である.
5.求めたR-コンビネーション数
Eg:S=(3*a,4*b,5*c)の10-組合せ数Nを求める;
解:生成関数G(x)=(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4)*(1+x+x^2+x^3+x^4+x^5)
= ( 1 + ... + 3*x^10+2*x^10+x^10+...)
だからx^10の係数は6なので、N=6です.
*******************************************************************************************************************************************
これらの基本例を紹介した後、基本的なテンプレートについて話します.つまり、プログラムを書きます.
整数分割で言えば、実はプログラムの多くは同じで、あまり大きな違いはありません:大体2つの配列c 1[]を利用して、c 2[]を利用して、c 1の配列は多項式の各係数の最後の結果を保存するために使用して、c 2の配列は中間変換のために使用して、計算が終わるたびに、それをc 1に割り当てて、それからc 2はゼロにします.次に3サイクル:最外層、それといくつかの多項式の乗算を記録します;第2層は、c 1の各項目を表す.第3層は、後に多項式に乗算される各項目を表す.PS:まず手作業で作って、シミュレーションしておけばいいと思います.
My Code:
一般型の母関数は生成関数とも呼ばれ、
1.定義:G(x)=a 0+a 1*x+a 2*x^2+...+an*x^n + ...,G(x)はシーケンス{an}の生成関数である.
Eg:{C(n,m)}の生成関数は(1+x)^m,{k^n}の生成関数はG(x)=1+k*x+k^2*x^2+.==1/(1-k*x)
2.基本モデル:
1.分銅の問題:
今分銅が1グラム2個、分銅が2グラム1個、分銅が4グラム2個あるとしたら、どのような重量を量ることができますか.案数はいくらですか.
解:
不定方程式をリストできます.
1*x1 + 2*x2 + 4*x3 == r;(0<=x1<=2, 0<=x2<=1, 0<=x3<=2)
したがって、対応する親関数は次のとおりです.
G(x) = (1+x+x^2) * (1+x^2) * (1+x^4+x^8) = 1+x+2*x^2+x^3+2*x^4+x^5+2*x^6+x^7+2*x^8+x^9+2*x^10+x^11+x^12
ここで、xの指数は秤量可能な重量であり、xの前の係数は重量が指数であることができる案数である.
2.正の整数分割の問題:
G(x) = (1+x+x^2+x^3+x^4+...)* (1+x+x^2+x^3+x^4+...)* (1+x+x^2+x^3+x^4+...)*...*(n回乗算)
3.ボールを取る問題:
ポケットの中は白いボールの2つがあって、赤いボールの3つ、黄色のボールの1つ、袋の中から3つのボールを探し出して何种类の取り方がありますか?
G(x)= (1+x+x^2) * (1+x+x^2+x^3) * (1+x)
1はボールを取らないことを表して、xは1つのボールを取って、x^2は2つのボールを取って、x^3は3つのボールを取って
だから私たちはx^3の前の係数を要求するだけでいいです.X^mの前の係数はm個のボールを触るのに必要な方法数を表しているからです.
4.ボールを放つ問題:
n個のボールがm個の箱の中に置いて、何種類の異なる置き方がありますか?
G(x) = (1+x+x^2+x^3+...x^k+...)*(1+x+x^2+x^3+...x^k+...)*...(全部でn項あり)我々が要求するのはx^mの前の係数,すなわち方法数である.
5.求めたR-コンビネーション数
Eg:S=(3*a,4*b,5*c)の10-組合せ数Nを求める;
解:生成関数G(x)=(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4)*(1+x+x^2+x^3+x^4+x^5)
= ( 1 + ... + 3*x^10+2*x^10+x^10+...)
だからx^10の係数は6なので、N=6です.
*******************************************************************************************************************************************
これらの基本例を紹介した後、基本的なテンプレートについて話します.つまり、プログラムを書きます.
整数分割で言えば、実はプログラムの多くは同じで、あまり大きな違いはありません:大体2つの配列c 1[]を利用して、c 2[]を利用して、c 1の配列は多項式の各係数の最後の結果を保存するために使用して、c 2の配列は中間変換のために使用して、計算が終わるたびに、それをc 1に割り当てて、それからc 2はゼロにします.次に3サイクル:最外層、それといくつかの多項式の乗算を記録します;第2層は、c 1の各項目を表す.第3層は、後に多項式に乗算される各項目を表す.PS:まず手作業で作って、シミュレーションしておけばいいと思います.
My Code:
<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
if(b == 0)
return a;
return gcd(b, a%b);
}
int c1[maxn];///
int c2[maxn];///
int n;///
/**
c1 ,
(1+x+x^2+..x^n) ,
0 n x 1.
**/
void Init()
{
for(int i=0; i<=n; i++)
{
c1[i] = 1;
c2[i] = 0;
}
}
int main()
{
while(cin>>n)
{
Init();
for(int i=2; i<=n; i++)/// ,
{
for(int j=0; j<=n; j++)///
{
for(int k=0; k+j<=n; k+=i)/// n
{
c2[k+j] += c1[j];/// ,
}
}
for(int j=0; j<=n; j++)/// c1[]
{
c1[j] = c2[j];
c2[j] = 0;///c2
}
}
cout<<c1[n]<<endl;
}
return 0;
}
</span>