Integration【2019牛客暑期多校训练营（第一场）B】【待定系数法】

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

题目描述

Bobo knows that ∫∞011+x2 dx=π2.∫0∞11+x2 dx=π2.

Given n distinct positive integers a1,a2,…,ana1,a2,…,an, find the value of
1π∫∞01∏ni=1(a2i+x2) dx.1π∫0∞1∏i=1n(ai2+x2) dx.

It can be proved that the value is a rational number pqpq.
Print the result as (p⋅q−1)mod(109+7)(p⋅q−1)mod(109+7).

输入描述:

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,…,ana1,a2,…,an.

* 1≤n≤1031≤n≤103
* 1≤ai≤1091≤ai≤109
* {a1,a2,…,an}{a1,a2,…,an} are distinct.
* The sum of n2n2 does not exceed 107107.

输出描述:

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

  求这样的一个函数，既然知道积分，我们这里可以用待定系数法来求解问题。

  我们假设，原式可以拆分成C1/(a1^2 + x^2) + C2/(a2^2 + x^2) + …… + Cn/(an^2 + x^2) = 原式（积分里面的那个），那么我们假如要求C1是不是要吧整个式子两端同乘以(a1^2 + x^2)然后，我们可以假设(x^2 = -a1^2)是不是就可以用以求解C1了？

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e5 + 7;
const ll mod = 1e9 + 7;
int N;
ll a[maxN], mu[maxN];
ll fast_mi(ll a, ll b = mod - 2)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
int main()
{
    while(scanf("%d", &N) != EOF)
    {
        for(int i=1; i<=N; i++) scanf("%lld", &a[i]);
        for(int i=1; i<=N; i++)
        {
            mu[i] = 1LL;
            for(int j=1; j<=N; j++)
            {
                if(j == i) continue;
                mu[i] = mu[i] * ( a[j] * a[j] % mod - a[i] * a[i] % mod + mod) % mod;
            }
            mu[i] = fast_mi(mu[i]);
        }
        ll ans = 0;
        for(int i=1; i<=N; i++)
        {
            ll tmp = fast_mi(2) * fast_mi(a[i])  % mod * mu[i] % mod;
            ans = ( ans + tmp ) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}