B Integration

题意：

给定$a_1,a_2,...,a_n$, 计算 $$\frac{1}{π}\int_{0}^{\infty}\frac{1}{\prod\limits_{i=1}^{n}(a_i^2+x^2)}dx$$ 在mod（1E9+7）意义下的答案。

思路：

裂项化乘为和的方法

可以得到

$$\frac{1}{2}\sum_{i=1}^n \quad \frac{1}{\prod_{j=1,j \ne i}^n \quad a_j^2 - a_i^2} \quad \frac{1}{a_i}$$

参考：https://www.cnblogs.com/Dillonh/p/11209476.html

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

template<class T> void _R(T &x) { cin >> x; }

void _R(int &x) { scanf("%d", &x); }

void _R(ll &x) { scanf("%lld", &x); }

void _R(double &x) { scanf("%lf", &x); }

void _R(char &x) { scanf(" %c", &x); }

void _R(char *x) { scanf("%s", x); }

void R() {}

template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

const int inf = 0x3f3f3f3f;

const int mod = 1e9+;

/**********showtime************/

            const int maxn = 1e3+;

            int a[maxn];

            ll ksm(ll a, ll b) {

                ll res = ;

                while(b > ) {

                    if(b & ) res = res * a % mod;

                    a = a * a % mod;

                    b = b >> ;

                }

                return res;

            }

int main(){

            int n;

            while(~scanf("%d", &n)){

                for(int i=; i<=n; i++) scanf("%d", &a[i]);

                ll sum = ;

                for(int i=; i<=n; i++) {

                    ll tmp = ;

                    for(int j=; j<=n; j++) {

                        if(i == j) continue;

                        ll s = (1ll*a[j] * a[j]%mod - 1ll*a[i]*a[i]%mod + mod)%mod;

                        tmp = tmp * ksm(s, mod-) % mod;

                    }

                    tmp = tmp * ksm(a[i], mod-) % mod;

                    sum = (sum + tmp )% mod;

                }

                sum = sum * ksm(, mod-) % mod;

                printf("%lld\n", sum);

            }

            return ;

}

C Euclidean Distance

贪心或者拉格朗日乘子法

D Parity of Tuples

fwt

G Substrings 2

字符串

H XOR

线性基

I Points Division

DP，线段树，折线

巴特西

2019NC#1