2019牛客多校第一场

感谢老陈的翻译

B. Integration

题目大意

$$已知\int_0^{\infty}\frac{1}{1+x^2}dx=\frac{\pi}{2}.给定数组a,求\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod{\left( a_i^2+x^2 \right) }}dx的值. 假设结果为\frac{p}{q},输出p \cdot q^{-1}.$$

思路

先把所给公式分母下面的公式拿出来化简

$$\frac{1}{\prod_{i=1}^{n}\left( a_{i}^2+x^2\right )}$$ $$\begin{align}&\frac{1}{\prod_{i=1}^{n}\left( a_{i}^2+x^2\right )}\\ =&\frac{1}{\left(a_1^2+x^2\right) \left(a_2^2+x^2\right) }\times \frac{1}{\prod_{i=3}^{n}\left( a_{i}^2+x^2\right )} \\ =& \frac{1}{ a_2^2-a_1^2 }\times \left( \frac{1}{a_1^2+x^2}- \frac{1}{a_2^2+x^2 }\right)\times \frac{1} {\prod_{i=3}^{n}\left( a_{i}^2+x^2 \right)}\\ =& \frac{1}{ a_2^2-a_1^2 }\times \left( \frac{1}{a_1^2+x^2}\times\frac{1}{a_3^2+x^2}- \frac{1}{a_2^2+x^2 }\times\frac{1}{a_3^2+x^2}\right)\times \frac{1} {\prod_{i=4}^{n}\left( a_{i}^2+x^2 \right)}\\ =& \left(\frac{1}{(a_2^2-a_1^2)(a_3^2-a_1^2)}\frac{1}{(a_1^2+x^2)}+\frac{1}{(a_1^2-a_2^2)(a_3^2-a_2^2)}\frac{1}{(a_2^2+x^2)}+\frac{1}{(a_1^2-a_3^2)(a_2^2-a_3^2)}\frac{1}{(a_3^2+x^2)} \right )\times \frac{1} {\prod_{i=4}^{n}\left( a_{i}^2+x^2 \right)} \end{align}$$

然后总结公式继续化简

$$\begin{aligned} &\sum\limits_{i=1}^{n}\frac{1}{\prod\limits_{j=1,j\not=i}^{n}(a_j^2-a_i^2)}\int_0^{\infty}\frac{1}{a_i^2+x^2}dx&\\ =&\sum\limits_{i=1}^{n}\frac{1}{\prod\limits_{j=1,j\not=i}^{n}(a_j^2-a_i^2)\times a_i^2}\int_0^{\infty}\frac{1}{1+(\frac{x}{a_i})^2}dx&\\ =&\sum\limits_{i=1}^{n}\frac{1}{\prod\limits_{j=1,j\not=i}^{n}(a_j^2-a_i^2)\times a_i}\int_0^{\infty}\frac{1}{1+(\frac{x}{a_i})^2}d\left(\frac{x}{a_i}\right)\\ = &\sum\limits_{i=1}^{n}\frac{1}{2\times\prod\limits_{j=1,j\not=i}^{n}(a_j^2-a_i^2)\times a_i}\end{aligned}$$

感谢瓜皮大佬hhh

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1010;
const int mod=1e9+7;
ll a[maxn];
ll  quickMod(ll a, ll p, ll mod) {
	a%=mod;
    ll base=1;
    while(p) {
        if(p&1) base=base*a%mod;
        a=a*a%mod; 
		p>>=1;
    }
    return base;
}
int main(){
	int n;
	while(~scanf("%d",&n)){
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			ll temp=1;
			for(int j=1;j<=n;j++){
				if(i!=j) temp=temp*((a[j]*a[j]%mod-a[i]*a[i]%mod)%mod+mod)%mod; 
			}
			temp=quickMod(temp,mod-2,mod);
			temp=temp*quickMod(2*a[i],mod-2,mod)%mod;
			ans=(ans+temp)%mod;
		}
		printf("%lld\n",ans);
	}
}