[noi simulation race] I don't know which CF paper title it is (probability expectation, martingale's stop time theorem)

Topic

Answer key

The paper ：（ Cannot read ） Bloomberg 《 Martingales and a class of probability and expectation problems about stopping time 》

Time theorem of martingale

Martingale is a special kind of stochastic process , Originated from the mathematical description of fair gambling games . Suppose we were watching a gambling game from the beginning , Now we have got the former $t$ Second observation , So when the first $t+1$ second Expectations of observations Equal to the $t$ Of a second Observed value when , We just call this a fair gambling game .

random process ： In a random background , moment $i$ There will be state $X_i$ , Record them in turn to obtain the random process .

martingale ： For a random process $\{X_0,X_1,...\}$ , If $E(X_{n+1}|X_0,X_1,...,X_n)=X_n$ , We call this stochastic process martingale .

notes ：$E(X_{n+1}|X_0,X_1,...,X_n)$ It's conditional expectation , And guaranteed Expected state The definition of is existing and reasonable .

Stop time theorem ： For any dwell $t$ （ End the observation at this time , stay I don't know the random process in the middle Discuss the expectation of pause state ）, Yes $E(X_t)=X_0$ .

Conclusion of potential energy function

Consider a random process $\{A_0,A_1,...\}$, When it is determined that the termination status is $A_t$ When , How to find the stop time $t$ The expectations of the $E(t)$ , We can construct a function $\Phi (A)$ , Satisfy ：

• $E(\Phi (A_{n+1})-\Phi (A_n)|A_0,A_1,...,A_n)=-1$ , Potential energy is expected to decrease with time .
• $\Phi (A_t)$ Constant value , And $\Phi (A_i)=\Phi (A_t)$ If and only if $i=t$ , The final state only corresponds to a potential energy .

By construction $B_i=\Phi (A_i)+i$ , You know $E(B_{n+1}|B_0,B_1,...,B_n)=B_n$ , therefore $\{B_i\}$ It is also a martingale , According to the stop time theorem , Yes $E(B_t)=B_0\Rightarrow E(\Phi (A_t)+t)=\Phi (A_0)\Rightarrow \Phi (A_t)+E(t)=\Phi (A_0)$

So get the calculation method of pause expectation $E(t)=\Phi (A_0)-\Phi (A_t)$ .

Back to this scrap problem

( Put together a six word title

We define state by $n$ Dimension vector , Then we can legally define the expectation of the state , And I was surprised to find that the random process is martingale ！

Now we have to define a potential energy function $\Phi (\vec{A})$ , Meet each expectation and reduce 1 .

Might as well try. $\Phi (\vec{A})=\sum f(a_i)$ , Make $m=\sum a_i$（$m$ It is the same. ）, Examine each $a_i$ and $f(a_i)$ The change of , Available by definition
$$\sum _{i=1}^n\frac{a_i(m-a_i)}{m(m-1)}\left(f(a_i+1)-f(a_i)+f(a_i-1)-f(a_i)\right)=-1$$

Try to construct ？ If you can become ${\sum }_{i=1}^n\frac{a_i(1-m)}{m(m-1)}$ How nice , Make
$$(f(a_i+1)-f(a_i))-(f(a_i)-f(a_i-1))=\frac{1-m}{m-a_i}$$

Look at the left side of the formula and you will find it very beautiful , Make $h(x)$ by $f(x)$ The function after the difference twice （${\sum }_{i=1}^{n}h(i)=f(n+1)-f(n)$）, that
$$h(x)=\frac{1-m}{m-x}$$

We can directly prefix and find all $f(a_i)$ , Time complexity $O(a\log P)$ , But we still need to find $f(m)$ , The most efficient method of direct recursion is time and space $O(m)$ Of , But we notice that this subscript is exactly equal to $m$ , Can have wonderful properties ：
$$f(m)=\sum _{i=0}^{m-1}\sum _{j=0}^i\frac{1-m}{m-j}=\sum _{j=0}^{m-1}\frac{1-m}{m-j}\cdot (m-j)=m(1-m)$$

shock ！ It takes only one multiplication to get the answer ！

Total time complexity $O(a\log P)$ .

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

const int MOD = 1000000007;
int n,m,s,o,k;
inline int qkpow(int a,int b) {
    
	int res = 1;
	while(b > 0) {
    
		if(b & 1) res = res *1ll* a % MOD;
		a = a *1ll* a % MOD; b >>= 1;
	} return res;
}
int a[MAXN];
int f[MAXN];
int main() {
    
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	n = read(); m = 0;
	for(int i = 1;i <= n;i ++) a[i] = read(),m += a[i];
	for(int i = 1;i <= MAXN-5;i ++) {
    
		f[i] = (MOD+1-m) *1ll* qkpow(m-i+1,MOD-2) % MOD;
	}
	for(int i = 1;i <= MAXN-5;i ++) (f[i] += f[i-1]) %= MOD;
	for(int i = 1;i <= MAXN-5;i ++) (f[i] += f[i-1]) %= MOD;
	int ans = m*1ll*(m-1) % MOD;
	for(int i = 1;i <= n;i ++) {
    
		(ans += f[a[i]]) %= MOD;
	}
	AIput(ans,'\n');
	return 0;
}