擅长解密的小红同学（多重集排列）

电玩女神 2022-09-10 03:19 123阅读 0赞

[链接][Link 1]

对于这题来说，求期望就是求排列的种类。

简单证明：（0代表失败，1代表成功）
    
    1次	1
    
    2次	01
    
    3次	001
    
    .
    
    .
    
    .
    
    n次  000 ...0001
    
    当n趋于无穷的时候，所有的方法都被尝试过一遍。

**排列种类数：**

多重集排列问题：直接排列，然后取消相同元素的顺序：

a n s = ( n 0 + n 1 + n 2 + . . . + n 9 ) ! / n 1 ! ∗ n 2 ! ∗ . . . ∗ n 9 ! ans = (n\_0 + n\_1 + n\_2 +...+n\_9)! / n\_1! \* n\_2! \* ... \* n\_9! ans=(n0\+n1\+n2\+...\+n9)!/n1!∗n2!∗...∗n9!

坑点： a i a\_i ai的数据范围虽然是  0 < = a i < = 1 e 6 0 <= a\_i <= 1e6 0<=ai<=1e6

但是 ans 的分母可以达到 1e7，所以数组要开到1e7

--------------------

9.4补充：这个分布的期望就是1/p， 可以用数学严格证明，概率论课上给过结论，p = 1/所有的排列， 因此期望等于所有的排列。

ac code：

// Problem: 擅长解密的小红同学
    // Contest: NowCoder
    // URL: https://ac.nowcoder.com/acm/contest/11214/B
    // Memory Limit: 524288 MB
    // Time Limit: 2000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define ff first
    #define ss second
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b; i>=a; --i)
    typedef pair<int,int> PII;
    typedef long long ll;
    typedef unsigned long long ull;
    
    const int mod = 1e9 + 7;
    const int N = 1e7 + 7;
    
    ll arr[15], fac[N];
    
    ll qmi(ll a, ll b)
    { 
    	ll res = 1;
    	while(b)
    	{ 
    		if(b&1) res = res * a % mod;
    		b >>= 1;
    		a = a * a % mod;
    	}
    	return res;
    }
    
    void init()
    { 
    	fac[0] = 1;
    	for(int i = 1; i < N; i++)
    	{ 
    		fac[i] = fac[i-1] * i % mod;
    	}
    }
    
    void solve()
    { 
    	ll sum = 0;
    	for(int i = 1; i <= 10; i++) cin >> arr[i], sum += arr[i];
    	ll ans = fac[sum];
    	rep(i,1,10) 
    	{ 
    		ans = ans * qmi(fac[arr[i]], mod-2) % mod;
    	}
    	cout << ans << endl;
    }
    
    int main()
    { 
    	init();
    	solve();
    	return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/11214/B