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; }