problem1 link
二分答案。然后判断。将所有的机器按照$a_{i}$排序，$a_{i}$相同的按照$b_{i}$排序。用一个优先队列维护这些机器。这样对于第$i$个部分，拿出队列开始的机器来生产该部分；如果队列开头的机器生产的部分没用完，则将其左区间$a_{t}$设置为$a_{t}+1$然后重新塞到队列里。
problem2 link
首先由$A_{i}$得到$A_{i-1}$的方式为$A_{i-1}=((A_{i}+2^{50}-b)$^$a)$&$(2^{50}-1)$。然后就是一个数字一个数字暴力计算$B$值。总的累积复杂度是$O(n)$的。
problem3 link
令$f[i][j]$ 表示$vals[i]*vals[j]$对答案有贡献的概率。
令$dp[i][j][n]$表示$(i,j)$对答案有贡献且序列中总的元素个数为$n$的概率（那么$f[i][j]=dp[i][j][n]$）。考虑整个序列的长度从长度为 $n-1$转移到$n$。那么对于$dp[i][j][n]$来说，可以从下面三种情况转移而来：
（1）$dp[i-1][j-1][n-1]$: 在前面新增一个元素
（2）$dp[i][j-1][n-1]$: 在中间新增一个元素
（3）$dp[i][j][n-1]$: 在后面新增一个元素
code for problem1
#include <algorithm>
#include <queue>
#include <vector> class FleetFunding {
public:
int maxShips(int m, const std::vector<int> &k, const std::vector<int> &a,
const std::vector<int> &b) {
int n = static_cast<int>(k.size());
struct node {
int L, R, cnt; node() = default;
node(int L, int R, int cnt) : L(L), R(R), cnt(cnt) {}
bool operator<(const node &A) const {
if (L != A.L) return L > A.L;
return R > A.R;
}
};
auto Check = [&](int M) {
if (M == 0) {
return true;
}
std::priority_queue<node> Q;
for (int i = 0; i < n; ++i) {
Q.push(node(a[i], b[i], k[i]));
}
for (int i = 1; i <= m; ++i) {
if (Q.empty()) {
return false;
}
int sum = 0;
while (sum < M) {
if (Q.empty() || Q.top().L != i) {
return false;
}
if (sum + Q.top().cnt < M) {
sum += Q.top().cnt;
Q.pop();
} else {
node p = Q.top();
Q.pop();
p.cnt -= M - sum;
++p.L;
if (p.L <= p.R && p.cnt > 0) {
Q.push(p);
}
break;
}
}
while (!Q.empty() && Q.top().L == i) {
node p = Q.top();
Q.pop();
++p.L;
if (p.L <= p.R) {
Q.push(p);
}
}
}
return true;
}; int sum = 0;
for (int i = 0; i < n; ++i) {
sum += k[i];
}
int low = 0, high = sum / m;
int result = 0;
while (low <= high) {
int M = (low + high) >> 1;
if (Check(M)) {
result = std::max(result, M);
low = M + 1;
} else {
high = M - 1;
}
}
return result;
}
};
code for problem2
class LimitedMemorySeries2 {
public:
int getSum(int n, long long x0, long long a, long long b) {
constexpr int kMod = 1000000007;
constexpr long long M = (1ll << 50) - 1;
auto NextX = [&](long long x) { return ((x ^ a) + b) & M; };
auto PreX = [&](long long x) { return ((x + M + 1 - b) ^ a) & M; };
auto Cal = [&](int id, long long x, int n) {
int ll = id, rr = id;
int result = 0;
long long lx = x, rx = x;
while (ll - 1 >= 0 && rr + 1 < n) {
lx = PreX(lx);
rx = NextX(rx);
if (lx < x && x > rx) {
++result;
--ll;
++rr;
} else {
break;
}
}
return result;
};
int result = 0;
long long t = x0;
for (int i = 0; i < n; ++i) {
result = (result + Cal(i, t, n)) % kMod;
t = NextX(t);
}
return result;
}
};
code for problem3
#include <vector>
class CoinFlips {
public:
double getExpectation(const std::vector<int> &vals, int prob) {
const double p = prob / 1000000000.0;
int n = static_cast<int>(vals.size());
std::vector<double> p2(n + 1);
p2[0] = 1.0;
for (int i = 1; i <= n; ++i) {
p2[i] = p2[i - 1] * (1 - p);
}
std::vector<std::vector<double>> prefix(n + 1, std::vector<double>(n + 1));
std::vector<std::vector<double>> prefix_sum(n + 1,
std::vector<double>(n + 1));
for (int len = 3; len <= n; ++len) {
for (int i = 1; i <= len; ++i) {
prefix[len][i] = p2[i - 1] * p;
if (i == 1) {
prefix[len][i] += p2[len];
}
prefix_sum[len][i] = prefix_sum[len][i - 1] + prefix[len][i];
}
}
std::vector<std::vector<std::vector<double>>> f(
2, std::vector<std::vector<double>>(n + 1, std::vector<double>(n + 1)));
int pre = 0, cur = 1;
for (int len = 3; len <= n; ++len) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
f[cur][i][j] = 0;
}
}
for (int L = 1; L <= len; ++L) {
for (int R = L + 2; R <= len; ++R) {
f[cur][L][R] =
prefix_sum[len][L - 1] * f[pre][L - 1][R - 1] +
(prefix_sum[len][R - 1] - prefix_sum[len][L]) * f[pre][L][R - 1] +
(1 - prefix_sum[len][R]) * f[pre][L][R];
if (L + 2 == R) {
f[cur][L][R] += p2[L] * p;
}
}
}
pre ^= 1;
cur ^= 1;
}
double result = 0.0;
for (int i = 0; i < n; ++i) {
for (int j = i + 2; j < n; ++j) {
result += vals[i] * vals[j] * f[pre][i + 1][j + 1];
}
}
return result;
}
};