# 확률과 기대값

확률과 기대값 문제는 경우의 수를 직접 세는 대신, 상태별로 "앞으로 얼마나 걸리는가" 또는 "성공할 가능성이 얼마인가"를 식으로 세웁니다. 대회에서는 주사위, 랜덤 이동, 흡수 상태, 기댓값 DP 형태로 자주 등장합니다.

## 확률 DP와 기대값 DP

확률은 특정 사건이 일어날 가능성을 구합니다. 기대값은 어떤 값의 평균적인 결과를 구합니다.

| 질문 | 식의 형태 |
| --- | --- |
| 성공할 확률은? | `prob[state] = sum p * prob[next]` |
| 끝날 때까지 평균 몇 번? | `E[state] = 1 + sum p * E[next]` |
| 얻는 점수의 평균은? | `E[state] = reward + sum p * E[next]` |
| 여러 선택 중 최적인 기대값은? | `min` 또는 `max`와 기대값 결합 |

확률의 합은 1이어야 합니다. 기대값은 단위가 "횟수", "점수", "비용" 중 무엇인지 먼저 고정해야 합니다.

## DAG 기대값

상태가 항상 더 큰 번호로만 이동한다면 뒤에서부터 계산할 수 있습니다. 예를 들어 칸 `pos`에서 주사위를 던져 `target` 이상이 되면 끝난다고 합시다.

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

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

vector<double> expectedDiceThrows(int target) {
    vector<double> expected(target + 1, 0.0);
    expected[target] = 0.0;

    for (int pos = target - 1; pos >= 0; --pos) {
        double sum = 0.0;
        for (int dice = 1; dice <= 6; ++dice) {
            int next = pos + dice;
            if (next > target) {
                next = target;
            }
            sum += expected[next];
        }
        expected[pos] = 1.0 + sum / 6.0;
    }

    return expected;
}
```

`expected[pos]`는 현재 위치에서 끝까지 필요한 평균 던짐 수입니다. 한 번 던지는 행동이 있으므로 항상 `1.0`이 더해집니다.

## 확률 분포 DP

주사위를 `n`번 던졌을 때 합의 분포는 DP로 계산할 수 있습니다.

코드는 target·던짐 수가 비음수이고 배열 크기 계산이 int 범위인 입력을 받습니다.

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

vector<double> diceSumDistribution(int throws) {
    vector<double> dp(6 * throws + 1, 0.0);
    dp[0] = 1.0;

    for (int t = 0; t < throws; ++t) {
        vector<double> next(6 * throws + 1, 0.0);
        for (int sum = 0; sum <= 6 * t; ++sum) {
            for (int dice = 1; dice <= 6; ++dice) {
                next[sum + dice] += dp[sum] / 6.0;
            }
        }
        dp.swap(next);
    }

    return dp;
}
```

확률 분포 DP에서는 전체 확률 합이 1에 가까운지 확인하면 디버깅에 도움이 됩니다. 실수 오차가 있으므로 `1e-9` 정도의 오차는 허용합니다.

## 기대값의 선형성

기대값은 사건들이 독립이 아니어도 합을 분리할 수 있습니다.

```text
E[X + Y] = E[X] + E[Y]
```

예를 들어 여러 indicator 변수를 세는 문제에서는 각 사건이 일어날 확률을 더하면 전체 기대 개수가 됩니다.

```text
기대 개수 = sum P(각 항목이 선택됨)
```

이 성질은 복잡한 상관관계를 직접 세지 않아도 되는 강력한 도구입니다.

## 순환이 있는 기대값

상태가 자기 자신이나 이전 상태로 돌아올 수 있으면 단순한 역순 DP가 안 됩니다.

예를 들어 어떤 상태에서 확률 `p`로 성공하고, 확률 `1-p`로 같은 상태에 남는다면:

```text
E = 1 + (1 - p) * E
p * E = 1
E = 1 / p
```

상태가 여러 개면 이런 식들이 연립방정식이 됩니다. 작은 상태 수에서는 Gaussian elimination을 쓰고, 특수 구조가 있으면 식을 변형해 닫힌 형태로 풉니다.

자기 반복 예시는 p>0일 때만 E=1/p이며, p=0이면 종료까지의 기대 횟수는 무한대입니다. 일반 순환계는 목표 도달과 유한 기대값 조건을 먼저 확인합니다.

## 모듈러 확률

정답을 `MOD`로 출력하라는 문제에서는 확률 `a / b`를 `a * inv(b) mod MOD`로 표현합니다. `MOD`가 소수이고 `b`가 `MOD`의 배수가 아니어야 Fermat 역원을 사용할 수 있습니다.

모듈러 나눗셈은 [모듈러 연산과 빠른 거듭제곱](https://h.readiz.com/learn/modular-arithmetic)의 역원 함수를 사용합니다. 확률의 분모가 modulus의 배수이면 이 표현을 사용할 수 없습니다.

실수 출력 문제인지 모듈러 출력 문제인지에 따라 구현이 완전히 달라집니다. 문제의 출력 형식을 먼저 확인합니다.

## 최적 선택과 기대값

랜덤 전이가 있지만 중간에 선택도 할 수 있다면 DP에 `min` 또는 `max`가 섞입니다.

```text
E[state] = min_action( cost(action) + sum p(next) * E[next] )
```

이 경우에도 각 action을 고정하면 기대값 식이고, 그중 최적 action을 선택합니다. 단, 순환이 있으면 최적성 방정식이 되어 더 어려워질 수 있습니다.

## 시간 복잡도

| 형태 | 시간 |
| --- | ---: |
| DAG 기대값 DP | `O(states * transitions)` |
| 확률 분포 DP | `O(steps * states * outcomes)` |
| Gaussian elimination | `O(states^3)` |
| Monte Carlo simulation | 정확도에 따라 다름 |

대회 문제는 보통 정확한 값을 요구합니다. "랜덤으로 많이 돌려 평균"은 검증용으로는 쓸 수 있지만 정답 제출용으로는 거의 맞지 않습니다.