# Generating Function Modeling

Generating Function Modeling은 counting 문제나 DP 식을 계수열로 보고, 곱셈, 나눗셈, rational form으로 바꾸는 모델링 레슨입니다. Formal Power Series가 연산 도구를 다룬다면, 이 레슨은 문제 문장을 어떤 생성함수 식으로 번역할지에 집중합니다.

## 문제 신호

| 문제 표현 | 생성함수 관점 |
| --- | --- |
| 합이 정확히 `S`가 되게 고른다 | `x^S` 계수 |
| 각 물건을 0/1번 고른다 | `1 + x^w` |
| 같은 물건을 여러 번 고른다 | `1 + x^w + x^{2w} + ...` |
| 순서가 중요하다 | sequence construction |
| 길이 `n`의 구조 개수 | `x^n` 계수 추출 |
| 점화식이 낮은 차수로 보인다 | rational generating function 후보 |

가장 먼저 정할 것은 변수의 의미입니다. `x`가 "무게"인지, "길이"인지, "비용"인지 섞이면 식은 맞아 보여도 계수가 다른 값을 뜻합니다.

## 기본 번역 규칙

| 구조 | 식 |
| --- | --- |
| 둘 중 하나 선택 | `A(x) + B(x)` |
| 독립적으로 둘 다 선택 | `A(x) * B(x)` |
| 0/1 선택 | `1 + x^w` |
| 무한 반복 선택 | `1 / (1 - x^w)` |
| 적어도 1번 선택 | `x^w / (1 - x^w)` |
| 길이 제한 `<= N` | `N`차까지만 truncate |

대회 구현에서는 무한급수를 실제로 무한히 만들지 않습니다. 필요한 차수까지만 유지합니다.

## 작은 예시: Coin Change

동전 가치가 `2, 3`이고 순서를 무시해 합 `S`를 만드는 방법 수를 세어 봅시다.

```text
coin 2: 1 + x^2 + x^4 + x^6 + ...
coin 3: 1 + x^3 + x^6 + ...

F(x) = 1 / ((1 - x^2)(1 - x^3))
answer(S) = [x^S] F(x)
```

`S=6`이면 가능한 조합은 `2+2+2`, `3+3` 두 가지입니다. 실제로 `x^6` 계수는 2입니다.

## 순서가 있는 경우

같은 동전이라도 순서가 중요하면 식이 달라집니다.

```text
atomic choice A(x) = x^2 + x^3
sequence of choices = 1 + A + A^2 + A^3 + ...
                   = 1 / (1 - A(x))
```

S=6에서는 두 방식 모두 2입니다. 차이가 드러나는 S=5에서는 조합은 {2,3} 하나지만 수열은 (2,3), (3,2) 두 개입니다.

## DP와 생성함수의 연결

아래 DP는 coefficient update와 같습니다.

```text
dp[s] += dp[s - w]
```

이는 현재 다항식에 `1 + x^w + x^{2w} + ...`를 곱하는 과정입니다. 따라서 DP의 loop 순서가 생성함수 모델을 결정합니다.

| loop 순서 | 의미 |
| --- | --- |
| item 바깥, sum 증가 | 조합, 무한 반복 |
| sum 바깥, item 안쪽 | 순서 있는 sequence |
| item 바깥, sum 감소 | 0/1 선택 |

## 무제한 선택의 계수 생성

아래 코드는 무제한 선택의 계수를 필요한 차수까지만 생성합니다.

무한 반복의 weight는 양수여야 합니다. `maxDegree>=0`이며 1/(1-A)의 형식적 급수는 A(0)=0일 때 정의됩니다. 다항식 곱셈은 [Formal Power Series](https://h.readiz.com/learn/polynomial-recurrence-algorithms/formal-power-series)의 multiplyTruncated를 사용하되 그 함수의 limit은 최대 차수가 아닌 계수 개수이므로 maxDegree+1을 전달합니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <vector>
using namespace std;

vector<long long> unboundedChoicePolynomial(int weight, int maxDegree) {
    vector<long long> poly(maxDegree + 1, 0);
    for (int degree = 0; degree <= maxDegree; degree += weight) {
        poly[degree] = 1;
    }
    return poly;
}
```

`maxDegree`가 크고 다항식이 조밀하면 NTT가 필요합니다. 하지만 모델링 단계에서는 먼저 작은 truncate 구현으로 식이 맞는지 확인하는 편이 안전합니다.

## Rational Form으로 가는 신호

생성함수가 아래 꼴이면 `n`이 아주 클 때도 coefficient extraction을 할 수 있습니다.

```text
F(x) = P(x) / Q(x)
answer = [x^n] F(x)
```

`Q(x)`의 차수가 작으면 계수열은 선형 점화식을 가집니다. 이때 선택지는 세 가지입니다.

| 상황 | 방법 |
| --- | --- |
| `n`이 크고 `Q`가 직접 있음 | Bostan-Mori |
| 앞 항을 많이 만들 수 있음 | Berlekamp-Massey |
| 상태 전이가 작음 | Matrix Exponentiation |

생성함수 모델링은 이 세 도구의 입력을 만들어 주는 역할을 합니다.

## 손으로 따라가는 예시

문제: `1`과 `2`를 사용해 합 `n`을 만드는 순서 있는 방법 수.

```text
A(x) = x + x^2
F(x) = 1 / (1 - A(x))
     = 1 / (1 - x - x^2)
```

따라서 계수는 Fibonacci recurrence를 따릅니다.

```text
a_n = a_{n-1} + a_{n-2}
```

DP로 풀 수도 있고, `n`이 매우 크면 recurrence로 풀 수도 있습니다. 생성함수는 왜 같은 문제가 Fibonacci로 연결되는지 설명합니다.

## 시간 복잡도 선택

| 범위 | 접근 |
| --- | --- |
| `S <= 10^5`, item 수 중간 | 1차원 DP |
| 다항식 여러 개를 합친다 | divide-and-conquer convolution |
| `n`이 매우 크고 rational form | Bostan-Mori |
| 계수열 앞부분만 필요 | truncated polynomial |
| 조건이 여러 변수 | multivariate는 피하고 상태 DP로 압축 검토 |

변수가 두 개 이상이면 식은 예뻐져도 구현이 급격히 어려워집니다. 대회에서는 한 변수를 계수로 두고 나머지는 DP state로 남기는 혼합 모델이 자주 더 실용적입니다.