平均變異次數

題目

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

想法

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

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

• • 我們先只討論

    $i=1$

  • 紅色的地方就是在算平均有幾次

    $[a_1\ne a_2]$

  • 平均次數

    $=$ 期望次數

平均值跟期望值的關西

$\mathtt{\text{?}}$

骰正常的

$6$ 面骰子，骰

$6$ 次，請問能骰到的平均點數

$\begin{array}{rl}\mathtt{\text{avg}}& =\frac{\mathrm{總}\mathrm{和}}{\mathrm{總}\mathrm{方}\mathrm{法}\mathrm{數}}\\ & =\frac{1+2+3+4+5+6}{6}\end{array}$

$\begin{array}{rl}\mathtt{\text{E[X]}}& =\mathrm{機}{\mathrm{率}}_1\times x_1+\mathrm{機}{\mathrm{率}}_2\times x_2+...+\mathrm{機}{\mathrm{率}}_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{array}$

骰子的

$6$ 面分別為

$\{1,1,2,2,3,3\}$，骰

$6$ 次，請問能骰到的平均點數

$\begin{array}{rl}\mathtt{\text{avg}}& =\frac{\mathrm{總}\mathrm{和}}{\mathrm{總}\mathrm{方}\mathrm{法}\mathrm{數}}\\ & =\frac{1+1+2+2+3+3}{6}\end{array}$

$\begin{array}{rl}\mathtt{\text{E[X]}}& =\mathrm{機}{\mathrm{率}}_1\times x_1+\mathrm{機}{\mathrm{率}}_2\times x_2+...+\mathrm{機}{\mathrm{率}}_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{array}$

• 期望值就是把機率乘上

  $\mathtt{\text{value}}$ ， 平均值就是總方法數分之每次
  $\mathtt{\text{value}}$

• 機率其實就是

  $\begin{array}{r}\frac{\mathrm{出}\mathrm{現}\mathrm{的}\mathrm{次}\mathrm{數}}{\mathrm{總}\mathrm{方}\mathrm{法}\mathrm{數}}\end{array}$

• 代表期望值可以寫成

$$\begin{array}{rl}E[x]& =\sum \frac{\mathrm{出}\mathrm{現}\mathrm{的}\mathrm{次}\mathrm{數}\times \mathtt{\text{value}}}{\mathrm{總}\mathrm{方}\mathrm{法}\mathrm{數}}\\ & =\sum \frac{\underset{\mathrm{出}\mathrm{現}\mathrm{的}\mathrm{次}\mathrm{數}}{\underbrace{\mathtt{\text{value}}+\mathtt{\text{value}}+..\mathtt{\text{value}}}}}{\mathrm{總}\mathrm{方}\mathrm{法}\mathrm{數}}\end{array}$$

• 就跟平均的一模一樣

所以平均值

$=$期望值

• 回到剛剛的問題

• 平均次數

  $=$ 期望次數
  $=1\times P+0\times (1-P)=P$
  • 代表在這個題目機率
    $P=$ 期望次數
  • 所以我們下面直接用機率來算
  • 其中
    $P$ 為
    $[a_1\ne a_2]$ 的機率
  • $P=1-P([a_1=a_2])$

• 因為期望值可以線性疊加

  • $E[x_1+x_2]=E[x_1]+E[x_2]$
  • 全部一起算
    $=$ 單獨分開算

• 令總字數為

  $m$
  • $m=\sum _{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)}+..$

• $\mathtt{\text{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}$
  • $\mathtt{\text{a}}$ 放在第一個的機率為
    $\frac{2}{7}$ (因為總共
    $7$ 個字母他站兩個)
  • $\mathtt{\text{a}}$ 放在第一個又放在第二個的機率為
    $\frac{2}{7}\times \frac{1}{6}$ (因為總共
    $7$ 個字母
    $\mathtt{\text{a}}$ 站兩個，
    $\mathtt{\text{a}}$ 已經放一個下去了所以剩
    $1$ 個全部剩
    $6$ 個)

• 又類似抽籤跟順序無關

  • 我們放的位置
    $a_i,a_{i+1}$ 也跟順序無關
  • 所以任意
    $a_i,a_{i+1}$ 都是一樣的，直接
    $P([a_1\ne 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: 題解