一般型母関数の詳細とそのテンプレートタイプ


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:
<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>