[nk] 牛客月赛51 F-平均题

前言

T a g : Tag : Tag:数学 思维 规律 前缀和
传送门 :

题意 :
给你一个数组,你需要求出 所有子段平均数之和

答案对 1 0 9 + 7 10^9+7 109+7取模,如果答案最简是 a b \frac{a}{b} ba​,那么需要找到最小的非负整数 x x x使得 x × b ≡ a ( 1 0 9 + 7 ) x×b\equiv a(10^9+7) x×b≡a(109+7)

思路 :
我们考虑对操作的区间进行 长度分类,即 t = 1 , 2.... n t=1,2....n t=1,2....n

t = 1 t=1 t=1
显然答案就是 S n S_n Sn​(表示前缀和)

t = 2 t=2 t=2
答案是 S n + S n − 1 − S 1 S_n+S_{n-1}-S_{1} Sn​+Sn−1​−S1​

…其余同理

因此我们可以 O ( n ) O(n) O(n) 的求出每一段的值

最后统计答案的时候,我们对每一段进行求一个 乘法逆元即可,即分母
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>pre[i];
		pre[i] = (pre[i] + pre[i-1])%mod;
	}
	
	for(int i=1;i