Gym100187B

---

\(n\)：表示字符的種類(lèi)；
\(a_i\)：表示單詞i的個(gè)數(shù)；
\(Len\)：表示串的長(zhǎng)度；
先考慮一種單詞\(a_i\)放在一個(gè)固定位置p對(duì)答案的貢獻(xiàn):
整一個(gè)串的全排類(lèi)為：\[P = \frac{Len!}{a_1!a_2!...a_n!}\]
固定\(a_i\)的排列為：\[P_i = \frac{(Len-1)!}{a_1!a_2!...(a_i-1)!..a_n!}\]
對(duì)于最終答案貢獻(xiàn)就是：\[ans_{i,p} = \frac{P_i^2}{P^2}\]
則有：\[ans_i = \sum_{p=1}^{Len} ans_{i,p} = \frac{Len P_i^2}{P^2} = \frac{a_i^2}{Len}\]
下面只需枚舉字符求和即可：\[ans = \sum_{i=1}^{n}ans_i = \sum_{i=1}^{n} \frac{a_i^2}{Len}\]

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back #define PII pair<int,int> typedef long long ll; const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; using namespace std; int n,k,M[666],num; char s[200007]; double ans = 0; int main() {scanf(" %s",s+1);n=strlen(s+1);rep(i,1,n) ++M[s[i]-'a'];rep(i,0,25) {ans += (1.0*M[i]*M[i])/n;}printf("%.10f\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9460637.html

總結(jié)

以上是生活随笔為你收集整理的Gym100187B的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。