2019牛客暑期多校训练营（第一场） B Integration 【裂项相消法】

题意：

给n个不同整数, 求的值。

题目链接：

https://ac.nowcoder.com/acm/contest/881/B

题解：

参考大神博客:传送门

所谓裂项就是：

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
const int maxn = 1e5+5;
ll a[maxn], cnt[maxn];
ll quick_pow(ll a, ll b){
	ll ans = 1;
	while(b){
		if(b & 1){
			ans = ans * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
int main(){
	ll tmp = quick_pow(2, mod-2);
	int n;
	while(~scanf("%d", &n)){
		for(int i = 1; i <= n; i++){
			scanf("%lld", &a[i]);
		}
		for(int i = 1; i <= n; i++){
			cnt[i] = 1;		
			for(int j = 1; j <= n; j++){
				if(i == j) continue;
				cnt[i] = (cnt[i] * (a[j] * a[j] % mod - a[i] * a[i] % mod) % mod + mod) % mod;
			}
			cnt[i] = quick_pow(cnt[i], mod - 2) % mod;
			cnt[i] = (cnt[i] * quick_pow(a[i], mod - 2)) % mod;
			cnt[i] = cnt[i] * tmp % mod;
		}
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans = ((ans + cnt[i]) % mod + mod) % mod;
		}
		cout<<ans<<endl;
		
	}
}