[nk] Niuke monthly competition 51 f-average question

Preface

$Tag:$ mathematics thinking law The prefix and
Portal :

The question :
Give you an array , You need to figure out Sum of all sub segment averages

The answer is right $10^9+7$ modulus , If the simplest answer is $\frac{a}{b}$, Then you need to find the smallest nonnegative integer $x$ bring $x\times b\equiv a(10^9+7)$

Ideas :
We consider the interval of operations Length classification , namely $t=1,2....n$

$t=1$
The obvious answer is $S_n$( Represents the prefix and )

$t=2$
The answer is $S_n+S_{n-1}-S_1$

… The rest is the same

So we can $O(n)$ Find out the value of each segment

At the end of the statistics , We find one for each paragraph Multiply the inverse , The denominator
code :

ll qmi(ll a,ll b){
    
	ll res = 1;
	while(b){
    
		if(b&1) res = res*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return res;
}

ll n,a[N],pre[N],dp[N];

void solve(){
    
	cin>>n;
	
	for(int i=1;i<=n;i++){
    
		cin>>pre[i];
		pre[i] = (pre[i] + pre[i-1])%mod;
	}
	
	for(int i=1;i<=n;i++){
    
		if(i<=n/2+n%2)
			dp[i] = (dp[i-1] + (pre[n+1-i] - pre[i - 1] + mod))%mod;
			else dp[i] = dp[n+1-i];
	}
	
	ll ans = 0;
	for(int i=1;i<=n;i++){
    
		ans = (ans + dp[i]*qmi(i,mod-2))%mod;
	}
	
	cout<<ans<<endl;
	
	
}