QOJ12529 Fibonacci's Nightmare 题解
写完这篇题解就去睡觉。
上来经典套路，方差等于平方的均值减去均值的平方，对应到这里就是
我们来考虑如何计算一下这两个东西。
首先是
就是
维护一下前缀和即可。
接下来是
前面的
难办的是
我们不妨换个角度考虑，我们能不能在递推的过程中直接顺便计算一下
更具体的，我们令
在这里强调，
依旧全期望公式。考察一下情况：
，概率是 ，期望是 。 - 注意这里实际上是一个条件期望，而已知
的条件时 的分布等价于一个 之间独立均匀分布的随机变量，因此我们可以安全地这样带入。如果你不能理解这一步，可以想象一个写着 到 的转盘，然后 那个位置写着再来一次，这个转盘最终转到 中的任意一个数概率都是均等的。
- 注意这里实际上是一个条件期望，而已知
，概率是 ，期望是 。 ，概率是 。 ，和上一种是对称情况，概率和期望均相同。
我们来考虑后面两种情况。
我们希望计算
继续拆。
此时我们再来看一下最后这个东西。
这个东西就是
然后你发现你就做完了。我们只需要
[!info]- 代码
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140#include <iostream>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
private:
uint_type x;
void norm() { x -= mod * (x >= mod); }
public:
modular() : x(0) {}
modular(int_type _x) {
if (_x < 0) {
x = _x % (int_type)mod + (int_type)mod;
}
else {
x = _x % mod;
}
norm();
return;
}
friend modular operator+(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + rhs.x;
ret.norm();
return ret;
}
friend modular operator-(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + mod - rhs.x;
ret.norm();
return ret;
}
friend modular operator*(const modular &lhs, const modular &rhs) {
return modular(lhs.x * rhs.x);
}
modular operator-() const {
modular ret;
ret.x = mod - x;
return ret;
}
modular operator-=(const modular &b) { return *this = *this - b; }
modular operator+=(const modular &b) { return *this = *this + b; }
modular operator*=(const modular &b) { return *this = *this * b; }
bool operator==(const modular &b) const { return x == b.x; }
uint_type val() const { return x; }
friend std::istream &operator>>(std::istream &is, modular &rhs) {
is >> rhs.x;
rhs.x %= mod;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
os << rhs.val();
return os;
}
};
using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
} // namespace maths
namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
T ret = id;
for (; b; b >>= 1, a = a * a) {
if (b & 1) {
ret = a * ret;
}
}
return ret;
}
template <class T>
T quick_pow(T a, const std::string &s, T id = T()) {
T ret = id;
for (size_t i = 0; i < s.size(); i++, a = a * a) {
if (s[i] == '1') {
ret = a * ret;
}
}
return ret;
}
} // namespace maths
namespace solve {
const uint mod = 1e9 + 7;
using mll = maths::modint1000000007;
mll inv(mll x) { return maths::quick_pow<mll>(x, mod - 2, 1); }
void solve() {
uint n;
std::cin >> n;
++n;
std::vector<mll> expect_a(n), expect_square(n), expect_product(n);
expect_product[0] = 1;
expect_square[0] = 1;
expect_a[0] = 1;
mll sum = expect_a[0], sum_square = expect_square[0];
for (size_t i = 1; i < n; i++) {
const mll inv_i = inv(i - 1 + 1);
expect_a[i] = sum * 2 * inv_i;
expect_square[i] = 2 * sum_square * (inv_i) + 2 * expect_product[i - 1];
expect_product[i] = i * i * expect_product[i - 1] +
i * 1 * 2 * 2 * expect_product[i - 1] +
1 * 1 * expect_square[i];
const mll inv_i1 = inv(i + 1);
expect_product[i] *= inv_i1 * inv_i1;
sum_square += expect_square[i];
sum += expect_a[i];
}
std::cout << expect_square.back() - expect_a.back() * expect_a.back()
<< "\n";
}
} // namespace solve
int main() {
solve::solve();
std::cout << std::flush;
return 0;
}
/**
* 首先方差是平方的均值减去均值的平方。
*
* 然后全期望公式即可。
*/