2019牛客暑期多校训练营（第一场） Integration（定积分）

链接：https://ac.nowcoder.com/acm/contest/881/B
来源：牛客网
 

Bobo knows that 

Given n distinct positive integers a1,a2,…,anfind the value of

It can be proved that the value is a rational number
Print the result as 

输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,an

* 1≤n≤1e3
* 1≤ai≤1e9
* {a1,a2,…,an} are distinct.
* The sum of n*n does not exceed 1e7.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

1
1
1
2
2
1 2

输出

复制

500000004
250000002
83333334

思路，裂项相消+积分公式

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll a[1005];
int n;
ll ksm(ll a,ll b){
	ll s=1;
	while(b){
		if(b&1)s = s * a % mod;
		a= a *a %mod;
		b>>=1;
	}
	return s%mod;
}
int main(){
    while(~scanf("%d",&n)){
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			ll temp=1;
			for(int j=1;j<=n;j++){
				if(j!=i){
					temp*=(a[j]*a[j]-a[i]*a[i])%mod;
					temp=(temp%mod+mod)%mod;
				}
			}
			ans+=ksm(temp*(a[i]<<1)%mod,mod-2)%mod;
			ans%=mod; 
		} 
		printf("%lld\n",ans);
	}
	return 0;
}