平均變異次數

題目

• 給 \(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: 題解