题解

题面描述

给定三个长度为 $n$ 的数组：

• $a_i$ 表示第 $i$ 个网页的访问量
• $b_i$ 表示第 $i$ 个网页的维护成本
• $c_i$ 表示第 $i$ 个网页的系数

对于第 $i$ 个网页，我们定义

也就是说，若网页的访问量与维护成本之差大于 $c_i$ 则判定该网页受欢迎，否则不受欢迎。

现在小红随机选取一个连续子区间 $[l, r]$ ($1\le l\le r\le n$)，如果该区间内受欢迎的网页数量多于不受欢迎网页的数量，则判定整个网站受欢迎；否则不受欢迎。
要求求出网站受欢迎的概率。注意答案要求表示为不可约分数 $\frac{p}{q}$，并输出

其中 $q^{-1}$ 是 $q$ 关于模 $M=10^9+7$ 的乘法逆元。

思路

1. 网页判定转换
   设每个网页对应一个数值 $v_i$：

   • 若 $a_i-b_i>c_i$，则令 $v_i=1$；
   • 否则令 $v_i=-1$。

2. 连续区间判定问题转换
   对于连续区间 $[l,r]$，受欢迎网页的数量减去不受欢迎网页的数量为

   $$\sum_{i=l}^{r}v_i.$$

   当该和大于 $0$ 时，说明区间内受欢迎网页多于不受欢迎网页。

3. 前缀和与区间和的转换
   定义前缀和数组 $pre$，其中
   $pre[0]=0$,$\quad pre[i]$=$pre[i-1]+v_i\quad (1\le i\le n).$ 由区间和性质可知，区间和为

   $$pre[r]-pre[l-1]>0 \iff pre[l-1]<pre[r].$$

   因此问题转化为：统计所有满足 $0\le i<j\le n$ 且 $pre[i]<pre[j]$ 的对数。

4. 数据结构求解
   由于 $n\le10^5$，可以利用树状数组（Binary Indexed Tree, BIT）对前缀和进行离散化后统计。

   • 首先将所有 $pre[i]$ 离散化。
   • 然后遍历 $pre$ 数组，对于每个位置 $j$，使用 BIT 查询之前有多少个 $pre[i]$ ($i<j$) 满足 $pre[i]<pre[j]$，累加结果后再更新 BIT。

5. 概率计算及模逆元
   设满足条件的区间数为 $count$，总区间数为

   $$total=\frac{n(n+1)}{2}.$$

   概率为 $\frac{count}{total}$。
   根据题目要求，需要计算

   $$ans=(count \times total^{-1})\bmod (10^9+7).$$

   模逆元可以通过快速幂计算得到：

   $$total^{-1}=total^{M-2}\bmod M.$$

代码分析

• C++ 解法
  利用 BIT 来统计前缀和对数。首先构造网页判定数组 $v$，计算前缀和，再对所有前缀和进行离散化，最后利用 BIT 统计满足条件的区间对数，计算概率并利用快速幂求模逆元。

• Python 解法
  思路与 C++ 一致，利用列表模拟 BIT 实现相同功能。

• Java 解法
  同样通过离散化前缀和并利用 BIT 完成区间统计，同时使用快速幂计算模逆元。

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;

// 树状数组（BIT）结构体
struct BIT {
    int n;
    vector<ll> tree;
    BIT(int n) : n(n) {
        tree.assign(n+1, 0);
    }
    // 更新下标 idx 的值
    void update(int idx, ll val) {
        for(; idx <= n; idx += idx & -idx)
            tree[idx] += val;
    }
    // 查询前 idx 项和
    ll query(int idx) {
        ll res = 0;
        for(; idx; idx -= idx & -idx)
            res += tree[idx];
        return res;
    }
};

// 快速幂求模
ll modExp(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while(exp > 0) {
        if(exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<ll> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    
    vector<int> v(n);
    for (int i = 0; i < n; i++){
        v[i] = (a[i] - b[i] > c[i]) ? 1 : -1;
    }
    
    // 计算前缀和：pre[0]=0, pre[i]=pre[i-1]+v[i-1]
    vector<ll> pre(n+1, 0);
    for (int i = 1; i <= n; i++){
        pre[i] = pre[i-1] + v[i-1];
    }
    
    // 离散化前缀和数组
    vector<ll> vals = pre;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    
    auto getID = [&](ll x){
        return (int)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
    };
    
    BIT bit(vals.size());
    ll countPairs = 0;
    // 遍历所有前缀和，下标 j 对应 pre[j]
    for (int j = 0; j <= n; j++){
        int id = getID(pre[j]);
        // 查询之前有多少个前缀和小于当前值
        countPairs += bit.query(id-1);
        bit.update(id, 1);
    }
    
    ll total = (ll)n*(n+1)/2;
    ll invTotal = modExp(total, MOD-2, MOD);
    ll ans = (countPairs % MOD) * invTotal % MOD;
    cout << ans << "\n";
    return 0;
}

Python 代码

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
MOD = 10**9 + 7

# 快速幂求模函数
def modExp(a, b, mod):
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b //= 2
    return res

# 树状数组（BIT）类
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
    # 更新下标 idx 的值
    def update(self, idx, val):
        while idx <= self.n:
            self.tree[idx] += val
            idx += idx & -idx
    # 查询前 idx 项和
    def query(self, idx):
        s = 0
        while idx:
            s += self.tree[idx]
            idx -= idx & -idx
        return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    v = []
    for i in range(n):
        if a[i] - b[i] > c[i]:
            v.append(1)
        else:
            v.append(-1)
    # 计算前缀和：pre[0]=0, pre[i]=pre[i-1]+v[i-1]
    pre = [0]*(n+1)
    for i in range(1, n+1):
        pre[i] = pre[i-1] + v[i-1]
    # 离散化前缀和
    vals = sorted(set(pre))
    comp = {x: i+1 for i, x in enumerate(vals)}
    bit = BIT(len(vals))
    countPairs = 0
    # 遍历前缀和数组，统计满足 pre[i] < pre[j] 的对数
    for j in range(n+1):
        idx = comp[pre[j]]
        countPairs += bit.query(idx-1)
        bit.update(idx, 1)
    total = n*(n+1)//2  # 总区间数
    invTotal = modExp(total, MOD-2, MOD)
    ans = countPairs % MOD * invTotal % MOD
    print(ans)
    
if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;
public class Main {
    static final int MOD = 1000000007;
    
    // 快速幂求模函数
    static long modExp(long a, long b, long mod) {
        long res = 1;
        a %= mod;
        while(b > 0) {
            if((b & 1) == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }
    
    // 树状数组（BIT）类
    static class BIT {
        int n;
        long[] tree;
        public BIT(int n) {
            this.n = n;
            tree = new long[n+1];
        }
        // 更新下标 idx 的值
        public void update(int idx, long val) {
            while(idx <= n) {
                tree[idx] += val;
                idx += idx & -idx;
            }
        }
        // 查询前 idx 项和
        public long query(int idx) {
            long sum = 0;
            while(idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] parts = br.readLine().trim().split(" ");
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = Long.parseLong(parts[i]);
        parts = br.readLine().trim().split(" ");
        long[] b = new long[n];
        for (int i = 0; i < n; i++)
            b[i] = Long.parseLong(parts[i]);
        parts = br.readLine().trim().split(" ");
        long[] c = new long[n];
        for (int i = 0; i < n; i++)
            c[i] = Long.parseLong(parts[i]);
        int[] v = new int[n];
        for (int i = 0; i < n; i++){
            if(a[i] - b[i] > c[i])
                v[i] = 1;
            else
                v[i] = -1;
        }
        // 计算前缀和：pre[0]=0, pre[i]=pre[i-1]+v[i-1]
        long[] pre = new long[n+1];
        pre[0] = 0;
        for (int i = 1; i <= n; i++){
            pre[i] = pre[i-1] + v[i-1];
        }
        // 离散化前缀和，使用 TreeSet
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i <= n; i++){
            set.add(pre[i]);
        }
        HashMap<Long, Integer> comp = new HashMap<>();
        int idx = 1;
        for(Long x: set) {
            comp.put(x, idx++);
        }
        BIT bit = new BIT(comp.size());
        long countPairs = 0;
        // 遍历前缀和数组，统计满足 pre[i] < pre[j] 的对数
        for (int j = 0; j <= n; j++){
            int id = comp.get(pre[j]);
            countPairs += bit.query(id-1);
            bit.update(id, 1);
        }
        long total = (long)n*(n+1)/2; // 总区间数
        long invTotal = modExp(total, MOD-2, MOD);
        long ans = (countPairs % MOD) * invTotal % MOD;
        System.out.println(ans);
    }
}

题目内容

小红开发了一个属于自己的网站，为了验证自己的网站中的哪个网页受大多数人喜欢，她统计了网站中各网页的访问量。第 $i$ 个网页的访问量记为 $a_i$ ，$a_i$ 越大说明此网页越受欢迎。然而，维护网站的成本也不小，第 $i$ 个网页的维护成本记为 $b_i$，$b_i$ 越大说明此网页越难维护。

对于第 $i$ 个网页，我们定义，当网页的访问量与维护成本之差满足 $a_i-b_i > c_i$ 时，该网页被判定为受欢迎；否则判定为不受欢迎。

现在小红准备随机选定一个连续子区间 $[l,r] (1 ≤l≤r≤n)$，如果区间中受欢迎的网页数量大于不受欢迎的网页数量，则小红认为此网站是受欢迎的，否则是不受欢迎的。

小红想要知道，依据这种方式，有多大的概率能够判定得到，自己的网站是受欢迎的?为了避免精度问题，请将答案对 $(10^9+7)$ 取模后输出。

提示:本题中，在进行除法的取模时，即计算 $(p×q^{-1}$ $mod$ $M)$ ，其中 $q^{-1}$ 可以使用公式 $(q^{M-2}$ $mod$ $M)$ 得到：例如，在计算 $\frac 54$ $mod$ $M$时，根据公式 $4^{-1}=(4^{M-2}$ $mod$ $M)=250$ $000$ $002$，得到 $(p×q^{-1}$ $mod$ $M)=5×250$ $000$ $002$ $mod$ $M= 250$ $000$ $003$ 。

输入描述

第一行输入一个整数 $n(1 ≤ n ≤ 10^5)$ 表示网页的数量。

第二行输入 $n$ 个整数 $a_i(1 ≤ a_i< 10^9)$表示第 $i$ 个网页的访问量。

第三行输入 $n$ 个整数 $b_i(1 ≤ b_i< 10^9)$ 表示第 $i$ 个网页的维护成本。

第四行输入 $n$ 个整数 $c_i (1 ≤ c_i < 10^9)$ 表示第 $i$ 个网灭页系数。

输出描述

可以证明答案可以表示为一个不可约分数$\frac qp$，为了避免精度问题，请直接输出整数$(p×q^{-1}$ $mod$ $M)$ 作为答案，其中 $M =(10^9+7)$，$q^{-1}$ 是满足 $q×q^{-1}≡1$($mod$ $M$)的整数。

更具体地，你需要找到一个整数 $x ∈[0,M)$ 满足 $x×q$ 对 $M$ 取模等于 $p$，您可以查看样例解释得到更具体的说明。

样例1

输入

3
3 2 6
1 2 3
1 1 2

输出

500000004

说明

第一个网页是 $a_1-b_1=3-1=2>1$，受欢迎

第二个网页是 $a_2-b_2=2-2=0<1$，不受欢迎

第三个网页是 $a_3-b_3=6-3=3>2$，受欢迎。

如果随机选择区间，一共有六种不同的选法，分别是：

选择区间 $[1,1]$，唯一 一个网页是受欢迎的，所以网站也受欢迎；

选择区间 $[1,2]$，一个网页受欢迎、一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[1,3]$，两个网页受欢迎、一个网页不受欢迎，所以网站受欢迎；

选择区间 $[2,2]$，唯一 一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[2,3]$，一个网页受欢迎、一个网页不受欢迎，所以网站不受欢迎；

选择区间 $[3,3]$，唯一 一个网页是受欢迎的，所以网站也受欢迎。

这样，网站有$\frac 36$ 的概率是受欢迎的。我们能够找到，

$500$ $000$ $004$ $× 2=1$ $000$ $000$ $008$ ，对 $10^9+7$ 取后恰好等于分子 $1$，所以 $500$ $000$ $004$ 是需要输出的答案。