{%hackmd @ioncamp/__style %}
# [平均變異次數](https://zerojudge.tw/ShowProblem?problemid=c893)

## 題目

- 給 $n,k,c[1]\sim c[k]$
- 代表 $a$ 出現 $c[1]$ 次，$b$ 出現 $c[2]$ 次...
- $\sum\limits_{i=1}^k c[i]=n$
- 這些 $1\sim k$ 組成了一個長度為 $n$ 的字串
- 問對於這些字元能組成的排列字串 $a$ ， $\sum\limits_{i=1}^{n-1}[a_i\neq a_{i+1}]$ 的總和除以方法數是多少
- 對於每種排列 $a$ 的 $\sum\limits_{i=1}^{n-1}[a_i\neq a_{i+1}]$ 加起來之後再去除以「排列方法數」是多少

## 想法

- $ans=\frac{1}{方法數}\sum\limits_{合法\text{a}}\sum\limits_{i=1}^{n-1}[a_i\neq a_{i+1}]$

- $ans=\sum\limits_{i=1}^{n-1}\frac{1}{方法數}\sum\limits_{合法\text{a}}[a_i\neq a_{i+1}]$

- 

- 我們先只討論 $i=1$
- 紅色的地方就是在算平均有幾次 $[a_1\neq a_2]$

- 平均次數 $=$ 期望次數

> 平均值跟期望值的關西 $\texttt{?}$
>
> 骰正常的 $6$ 面骰子，骰 $6$ 次，請問能骰到的平均點數
>
> $\begin{align} \texttt{avg}&= \frac{總和}{總方法數} \\ &= \frac{1+2+3+4+5+6}{6} \end{align}$
>
> $\begin{align}\texttt{E[X]} &=機率_1\times x_1+機率_2\times x_2+...+機率_n\times x_n \\ & =\frac{1}{6}\times 1+\frac{1}{6}\times 2+\frac{1}{6}\times 3+\frac{1}{6}\times 4+\frac{1}{6}\times 5+\frac{1}{6}\times 6 \\ & = \frac{1+2+3+4+5+6}{6}\end{align}$
>
> 骰子的 $6$ 面分別為 $\{1,1,2,2,3,3\}$，骰 $6$ 次，請問能骰到的平均點數
>
> $\begin{align} \texttt{avg}&= \frac{總和}{總方法數} \\ &= \frac{1+1+2+2+3+3}{6} \end{align}$
>
> $\begin{align}\texttt{E[X]} &=機率_1\times x_1+機率_2\times x_2+...+機率_n\times x_n \\ & =\frac{2}{6}\times 1+\frac{2}{6}\times 2+\frac{2}{6}\times 3 \\ & = \frac{1+1+2+2+3+3}{6} \end{align}$
>
> - 期望值就是把機率乘上 $\texttt{value}$ ， 平均值就是總方法數分之每次 $\texttt{value}$
>
> - 機率其實就是 $\begin{align}\frac{出現的次數}{總方法數}\end{align}$
>
> - 代表期望值可以寫成
>
> $$\begin{align}E[x] &= \sum \frac{出現的次數\times \texttt{value}}{總方法數} \\ &=\sum \frac{\underbrace{\texttt{value}+\texttt{value}+..\texttt{value}}_{出現的次數}}{總方法數} \end{align}$$
>
> - 就跟平均的一模一樣
>
> 所以**平均值$=$期望值**

- 回到剛剛的問題
- 平均次數 $=$ 期望次數 $=1\times P+0\times (1-P)=P$
- 代表在這個題目機率 $P=$ 期望次數
- 所以我們下面直接用機率來算
- 其中 $P$ 為 $[a_1\neq a_2]$ 的機率
- $P=1-P([a_1=a_2])$
- 因為期望值可以線性疊加
- $E[x_1+x_2]=E[x_1]+E[x_2]$
- 全部一起算 $=$ 單獨分開算
- 令總字數為 $m$
- $m=\sum\limits_{i=1}^k c[i]$
- $P([a_1=a_2])=\frac{c[a]}{m}\times \frac{c[a]-1}{(m-1)}+\frac{c[b]}{m}\times \frac{c[b]-1}{(m-1)}+..$

- $\texttt{ex:aabbbcc}$
- $P([a_1=a_2])=\frac{2}{7}\times \frac{1}{6}+\frac{3}{7}\times \frac{2}{6}+\frac{2}{7}\times \frac{1}{6}$
- $\texttt{a}$ 放在第一個的機率為 $\frac{2}{7}$ (因為總共 $7$ 個字母他站兩個)
- $\texttt{a}$ 放在第一個又放在第二個的機率為 $\frac{2}{7}\times \frac{1}{6}$ (因為總共 $7$ 個字母 $\texttt{a}$ 站兩個，$\texttt{a}$ 已經放一個下去了所以剩 $1$ 個全部剩 $6$ 個)

- 又類似抽籤跟順序無關
- 我們放的位置 $a_i,a_{i+1}$ 也跟順序無關
- 所以任意 $a_i,a_{i+1}$ 都是一樣的，直接 $P([a_1\neq a_2])\times (n-1)$ 就是答案了 ( $n-1$ 個縫)

## CODE

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 3e5 + 5;

int n, m, k;
int c[maxn];

void init () {
    cin >> n >> k;

    for (int i = 1; i <= k; i++) {
        cin >> c[i];
        m += c[i];
    }
}

void solve () {
    double ans = 0;
    for (int i = 1; i <= k; i++) {
        ans += (double) (c[i] * (c[i] - 1)) / ((m) * (m - 1));
    }

    ans = (double) (1 - ans) * (n - 1);
    cout << fixed << setprecision (3) << ans << "\n";
} 
 
signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        init();
        solve();
    }
} 

###### tags: `題解`