F - Double Chance(期望，数学，树状数组优化)[AtCoder Beginner Contest 276]

题目如下：

F - Double Chance 题目链接

思路 or 题解：

期望公式：$\sum val\times p$
还可以细分：
如果两次抽出的值是相同的，都是 $x$，那么抽出的方案数为 $cn{t}_x\times cn{t}_x$。
如果两次抽出的值不同，那么抽出的方案数为：$cn{t}_x\times mi{n}_x$
$mi{n}_x$ 指的是小于$x$的个数

综上所述：
抽出最大值为$x$的概率为: $\frac{cn{t}_x^2+cn{t}_x\ast mi{n}_x\ast 2}{m^2}\ast x$
其中 $m$ 为袋子里的元素个数

时间复杂度: $O(n^2\ast log{n}^2)$

优化：

此处我们将上述公式的 $m^2$ 中的 $m$ 改成输出中的 $n$，方便分数加法，最后乘上 $\frac{n^2}{m^2}$ 即可

式子变为：
$\frac{(2cn{t}_x-1)+2mi{n}_x}{n^2}\times x$

显然 $cnt$ 和 $\frac{2cn{t}_x}{n^2}$ 都可以用树状数组存，以 $x$ 为下标即可。

AC代码：

#define int long long
//#define int long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int MOD = 998244353;
const int N = 400009;
int n;
int ksm(int a, int b, int p)
{
    a %= p;
    int ret = 1;
    while (b)
    {
        if (b % 2)
            ret = ret * a % p;
        a = a * a % p;
        b /= 2;
    }
    return ret;
}
#define getny(x, p) (ksm(x, (p)-2, p))
#define fracny(x, y, p) (((x) % (p)) * getny(y, p) % (p))

int cnt[N];

int pfn;

#define lowbit(x) ((x) & (-(x)))
int c[N]; // cnt
void add(int x, int v)
{
    for (int i = x; i <= 2e5; i += lowbit(i))
        c[i] += v;
}
int query(int x)
{
    int ret = 0;
    for (int i = x; i; i -= lowbit(i))
        ret += c[i];
    return ret;
}
int c1[N]; //((cnt*2)/(n^2))*x
void add1(int x, int v)
{
    for (int i = x; i <= 2e5; i += lowbit(i))
        c1[i] += v;
}
int query1(int x)
{
    int ret = 0;
    for (int i = x; i; i -= lowbit(i))
        ret += c1[i];
    return ret;
}

#define gm(x) (((x) % MOD + MOD) % MOD)

int ans;

void add(int x)
{
    pfn++;

    cnt[x]++;
    add(x, 1);
    add1(x, fracny(2, n * n, MOD) * x % MOD);
    ans = (ans + fracny(2 * cnt[x] - 1 + query(x - 1) * 2, n * n, MOD) * x % MOD) % MOD;

    ans = (ans + gm(query1(2e5) - query1(x))) % MOD;
}

void solve()
{
    buff;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x, add(x);
        cout << ans * fracny(n * n, pfn * pfn, MOD) % MOD << '\n';
    }
}
signed main()
{
    buff;
    solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

参考文章
感谢：