problem1 link
将$a_{0},a_{1},...,a_{n-1}$看做$a_{0}x^{0}+a_{1}x^{1}+...+a_{n-1}x^{n-1}$。那么第一种操作相当于乘以$1+x$模$x^{n}-1$，第二种操作相当于乘以$1+x^{n-1}$模$x^{n}-1$。所以操作的顺序无关。所以只需要枚举两种操作各用了多少次即可
problem2 link
对于$m$个数字$x_{1},x_{2},..,x_{m}$来说，设$a=frac{sum_{i=1}^{m}x_{i}}{m}$，那么$frac{1}{m}sum_{i=1}^{m}(x_{i}-a)^{2}=frac{1}{m}left (sum_{i=1}^{m}x_{i}^{2}-frac{left (sum_{i=1}^{m}x_{i} ight )^{2}}{m^{2}} ight )$
所以，对于子树$T$,可以计算包含子树树根的大小为$m$的连通块有多少个，同时记录所有情况的$s_{1}=sum_{i=1}^{m}x_{i}^{2},s_{2}=left (sum_{i=1}^{m}x_{i} ight )^{2}$之和。这样就是一个树上的动态规划。
problem3 link
首先，将所有的限制按照最近公共祖先分配到每个对应的结点上。那么现在就是每个子树有一些限制。
首先，分配结点以满足左右子树的限制。对于当前结点，枚举当前结点映射为最后的哪一个结点。
这时候对于限制，可以确定每个限制的$(x,y)$，$x$或者$y$：（１）一定在左侧;（２）一定在右侧；（３）都可以；（４）不是一定在左侧或者右侧但是$x$和$y$不能在一侧。第三类情况最后可以随意分配，比较简单。第四种情况暴力枚举$x$在左侧还是右侧。这样就可以确定所有的结点。
code for problem1
#include <algorithm>
#include <string>
#include <vector>
class LR {
public:
std::string construct(const std::vector<long long> &s,
const std::vector<long long> &t) {
if (s == t) {
return "";
}
int n = static_cast<int>(s.size());
long long x0 = std::accumulate(s.begin(), s.end(), 0ll);
long long x1 = std::accumulate(t.begin(), t.end(), 0ll);
if (x0 == 0) {
return "No solution";
}
int k = 0;
while (x0 < x1) {
++k;
x0 <<= 1;
}
if (x0 != x1) {
return "No solution";
}
auto Check = [&](std::vector<long long> s, int x, int y) {
for (int i = 0; i < x; ++i) {
long long t = s[n - 1];
for (int i = n - 1; i > 0; --i) {
s[i] += s[i - 1];
}
s[0] += t;
}
for (int i = 0; i < y; ++i) {
long long t = s[0];
for (int i = 0; i < n - 1; ++i) {
s[i] += s[i + 1];
}
s[n - 1] += t;
}
return s == t;
};
for (int i = 0; i <= k; ++i) {
if (Check(s, i, k - i)) {
return std::string(i, 'L') + std::string(k - i, 'R');
}
}
return "No solution";
}
};
code for problem2
#include <vector>
using BigDouble = __float128;
class AverageVarianceSubtree {
struct Node {
BigDouble s1 = 0.0;
BigDouble s2 = 0.0;
BigDouble s3 = 0.0;
BigDouble number = 0;
void Reset() {
s1 = s2 = s3 = 0.0;
number = 0;
}
Node Merge(const Node &other) {
Node result;
result.s1 = s1 * other.number + other.s1 * number;
result.s2 = s2 * other.number + other.s2 * number + 2 * s3 * other.s3;
result.s3 = s3 * other.number + other.s3 * number;
result.number = number * other.number;
return std::move(result);
}
void Add(const Node &other) {
s1 += other.s1;
s2 += other.s2;
s3 += other.s3;
number += other.number;
}
};
public:
double average(const std::vector<int> &p, const std::vector<int> &weight) {
n = static_cast<int>(p.size()) + 1;
tree.resize(n);
for (int i = 0; i < n - 1; ++i) {
tree[i + 1].push_back(p[i]);
tree[p[i]].push_back(i + 1);
}
this->weights = weight;
dp.resize(n);
for (int i = 0; i < n; ++i) {
dp[i].resize(n + 1);
}
BigDouble sum = 0;
BigDouble total = 0;
Dfs(0, -1);
for (int root = 0; root < n; ++root) {
for (int i = 1; i <= n; ++i) {
sum += (dp[root][i].s1 * i - dp[root][i].s2) / i / i;
total += dp[root][i].number;
}
}
return static_cast<double>(sum / total);
}
private:
void Dfs(int u, int prev) {
long long w1 = weights[u];
long long w2 = w1 * w1;
dp[u][0].number = 1;
for (auto v : tree[u]) {
if (v == prev) {
continue;
}
Dfs(v, u);
std::vector<Node> f(n + 1);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
if (i + j <= n) {
f[i + j].Add(dp[v][i].Merge(dp[u][j]));
}
}
}
dp[u] = std::move(f);
}
for (int i = n - 1; i >= 0; --i) {
dp[u][i + 1].s1 = dp[u][i].s1 + dp[u][i].number * w2;
dp[u][i + 1].s2 =
dp[u][i].s2 + dp[u][i].number * w2 + 2 * w1 * dp[u][i].s3;
dp[u][i + 1].s3 = dp[u][i].s3 + dp[u][i].number * w1;
dp[u][i + 1].number = dp[u][i].number;
}
}
std::vector<std::vector<int>> tree;
std::vector<int> weights;
std::vector<std::vector<Node>> dp;
int n = 0;
};
code for problem3
#include <unordered_set>
#include <vector>
class BinaryTreeAndPermutation {
struct Node {
long long contain_ps = 0;
long long contain = 0;
long long used = 0;
int left = -1;
int right = -1;
int total = 0;
std::vector<std::pair<int, int>> constrains;
int n = 0;
void Used(int t) { used |= 1ll << t; }
void AddConstrain(int x, int y) {
for (const auto &e : constrains) {
if ((e.first == x && e.second == y) ||
(e.first == y && e.second == x)) {
return;
}
}
constrains.emplace_back(x, y);
}
size_t UnUsedNodeNumber() const {
size_t num = 0;
for (int i = 0; i < n; ++i) {
if ((contain & (1ll << i)) != 0 && (used & (1ll << i)) == 0) {
++num;
}
}
return num;
}
int UnUsedNode() const {
for (int i = 0; i < n; ++i) {
if ((contain & (1ll << i)) != 0 && (used & (1ll << i)) == 0) {
return i;
}
}
return -1;
}
long long AllPs() const {
long long m = 0;
for (const auto &x : constrains) {
m |= 1ll << x.first;
m |= 1ll << x.second;
}
return m;
}
bool Has(int x) const { return (contain_ps & (1ll << x)) != 0; }
};
public:
std::vector<int> findPermutation(const std::vector<int> &lef,
const std::vector<int> &rig,
const std::vector<int> &a,
const std::vector<int> &b,
const std::vector<int> &c) {
n = static_cast<int>(lef.size());
tree.resize(n);
for (int i = 0; i < n; ++i) {
tree[i].left = lef[i];
tree[i].right = rig[i];
tree[i].n = n;
}
for (size_t i = 0; i < a.size(); ++i) {
tree[c[i]].AddConstrain(a[i], b[i]);
}
result.resize(n, -1);
if (!Dfs(0)) {
return {};
}
for (int i = 0; i < n; ++i) {
if (result[i] == -1) {
result[i] = tree[0].UnUsedNode();
tree[0].Used(result[i]);
}
}
return result;
}
private:
bool Split(
const std::vector<std::pair<int, int>> &undecided,
std::vector<std::pair<std::unordered_set<int>, std::unordered_set<int>>>
*result) {
int m = static_cast<int>(undecided.size());
std::vector<bool> visited(m);
for (int i = 0; i < m; ++i) {
if (!visited[i]) {
result->emplace_back();
auto &curr = result->back();
curr.first.insert(undecided[i].first);
curr.second.insert(undecided[i].second);
while (true) {
bool updated = false;
for (int j = i + 1; j < m; ++j) {
if (!visited[j]) {
int x = undecided[j].first;
int y = undecided[j].second;
if ((curr.first.count(x) > 0 && curr.first.count(y)) > 0 ||
(curr.second.count(x) > 0 && curr.second.count(y) > 0)) {
return false;
}
if (curr.first.count(x) > 0 || curr.second.count(y) > 0) {
curr.first.insert(x);
curr.second.insert(y);
updated = true;
visited[j] = true;
} else if (curr.first.count(y) > 0 || curr.second.count(x) > 0) {
curr.first.insert(y);
curr.second.insert(x);
updated = true;
visited[j] = true;
}
}
}
if (!updated) {
break;
}
}
}
}
return true;
}
bool Check(int root, int root_p) {
Node &node = tree[root];
Node &left = tree[node.left];
Node &right = tree[node.right];
if (root_p != -1 && ((left.contain_ps & (1ll << root_p)) != 0 ||
(right.contain_ps & (1ll << root_p)) != 0)) {
return false;
}
std::unordered_set<int> must_left;
std::unordered_set<int> must_right;
std::unordered_set<int> root_pair;
std::vector<std::pair<int, int>> undecided;
for (const auto &x : node.constrains) {
if (x.first == root_p && x.second == root_p) {
continue;
}
if (x.first == root_p) {
if (!left.Has(x.second) && !right.Has(x.second)) {
root_pair.insert(x.second);
}
} else if (x.second == root_p) {
if (!left.Has(x.first) && !right.Has(x.first)) {
root_pair.insert(x.first);
}
} else if (left.Has(x.first) || right.Has(x.second)) {
if (!left.Has(x.first)) {
must_left.insert(x.first);
}
if (!right.Has(x.second)) {
must_right.insert(x.second);
}
} else if (left.Has(x.second) || right.Has(x.first)) {
if (!left.Has(x.second)) {
must_left.insert(x.second);
}
if (!right.Has(x.first)) {
must_right.insert(x.first);
}
} else {
undecided.push_back(x);
}
}
for (auto x : must_left) {
if (must_right.count(x) > 0) {
return false;
}
}
for (auto x : must_right) {
if (must_left.count(x) > 0) {
return false;
}
}
for (const auto &e : undecided) {
if (root_pair.count(e.first) > 0) {
root_pair.erase(e.first);
}
if (root_pair.count(e.second) > 0) {
root_pair.erase(e.second);
}
}
while (true) {
bool deleted = false;
for (size_t i = 0; i < undecided.size(); ++i) {
int x = undecided[i].first;
int y = undecided[i].second;
if ((must_left.count(x) > 0 && must_left.count(y) > 0) ||
(must_right.count(x) > 0 && must_right.count(y) > 0)) {
return false;
}
if ((must_left.count(x) > 0 && must_right.count(x) > 0) ||
(must_left.count(y) > 0 && must_right.count(y) > 0)) {
return false;
}
if (must_left.count(x) > 0 || must_right.count(y) > 0) {
must_left.insert(x);
must_right.insert(y);
deleted = true;
undecided.erase(undecided.begin() + i);
break;
} else if (must_left.count(y) > 0 || must_right.count(x) > 0) {
must_left.insert(y);
must_right.insert(x);
deleted = true;
undecided.erase(undecided.begin() + i);
break;
}
}
if (!deleted) {
break;
}
}
for (int x : must_left) {
root_pair.erase(x);
}
for (int x : must_right) {
root_pair.erase(x);
}
if (tree[node.left].UnUsedNodeNumber() < must_left.size() ||
tree[node.right].UnUsedNodeNumber() < must_right.size()) {
return false;
}
std::vector<std::pair<std::unordered_set<int>, std::unordered_set<int>>>
splits;
if (!Split(undecided, &splits)) {
return false;
}
size_t total = must_left.size() + must_right.size() + root_pair.size();
for (const auto &e : splits) {
total += e.first.size() + e.second.size();
}
if (static_cast<int>(total) > tree[root].total) {
return false;
}
int m = static_cast<int>(splits.size());
bool valid_assign = false;
for (int i = 0; i < (1 << m); ++i) {
size_t left_num = 0;
size_t right_num = 0;
for (int j = 0; j < m; ++j) {
size_t num1 = splits[j].first.size();
size_t num2 = splits[j].second.size();
if ((i & (1 << j)) == 0) {
left_num += num1;
right_num += num2;
} else {
left_num += num2;
right_num += num1;
}
}
if (left_num + must_left.size() <= tree[node.left].UnUsedNodeNumber() &&
right_num + must_right.size() <=
tree[node.right].UnUsedNodeNumber()) {
valid_assign = true;
for (int j = 0; j < m; ++j) {
if ((i & (1 << j)) == 0) {
must_left.insert(splits[j].first.begin(), splits[j].first.end());
must_right.insert(splits[j].second.begin(), splits[j].second.end());
} else {
must_right.insert(splits[j].first.begin(), splits[j].first.end());
must_left.insert(splits[j].second.begin(), splits[j].second.end());
}
}
break;
}
}
if (!valid_assign) {
return false;
}
for (auto x : root_pair) {
if (tree[node.left].UnUsedNodeNumber() > must_left.size()) {
must_left.insert(x);
} else {
must_right.insert(x);
}
}
for (auto x : must_left) {
int t = tree[node.left].UnUsedNode();
result[x] = t;
tree[node.left].Used(t);
}
for (auto x : must_right) {
int t = tree[node.right].UnUsedNode();
result[x] = t;
tree[node.right].Used(t);
}
node.used = tree[node.left].used | tree[node.right].used;
if (root_p != -1) {
result[root_p] = root;
node.used |= 1ll << root;
}
node.contain =
tree[node.left].contain | tree[node.right].contain | 1ll << root;
return true;
}
bool Dfs(int root) {
Node &node = tree[root];
if (node.left == -1) {
node.contain = 1ll << root;
node.total = 1;
if (!node.constrains.empty()) {
int p = node.constrains.front().first;
for (const auto &x : node.constrains) {
if (p != x.first || p != x.second) {
return false;
}
}
node.contain_ps = 1ll << p;
node.used = 1ll << root;
result[p] = root;
}
return true;
}
if (!Dfs(node.left) || !Dfs(node.right)) {
return false;
}
long long cur_ps = node.AllPs();
long long left_ps = tree[node.left].contain_ps;
long long right_ps = tree[node.right].contain_ps;
node.contain_ps = cur_ps | left_ps | right_ps;
node.total = 1 + tree[node.left].total + tree[node.right].total;
Node &left = tree[node.left];
Node &right = tree[node.right];
int root_p = -1;
for (const auto &x : node.constrains) {
if ((left.Has(x.first) && left.Has(x.second)) ||
(right.Has(x.first) && right.Has(x.second)) ||
(left.Has(x.first) && right.Has(x.first)) ||
(left.Has(x.second) && right.Has(x.second))) {
return false;
}
if (x.first == x.second) {
if (root_p != -1 && root_p != x.first) {
return false;
}
root_p = x.first;
}
}
if (root_p != -1) {
return Check(root, root_p);
} else {
if (Check(root, -1)) {
return true;
}
for (int i = 0; i < n; ++i) {
if ((cur_ps & (1ll << i)) != 0 && Check(root, i)) {
return true;
}
}
return false;
}
}
std::vector<int> result;
std::vector<Node> tree;
int n = 0;
};