[CTS2024] The Gate of All Beings
This is a constructive problem on tree traversal. Observation of large test cases shows the answer does not exceed 3. It is posssible to traverse the entire tree with paths of length at most 3.
The answer is typically 0 or 1, except for small trees or star-shaped graphs. For small n (≤ 8), a brute-force search over permutations is feasible. Star graphs are handled as a special case. For other instances, generate a random permutation of nodes, starting with s and ending with t. Iteratively swap pairs of nodes until the total path distance is ≤ 1.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_NODES = 50005;
vector<int> graph[MAX_NODES];
int depth[MAX_NODES], parent[MAX_NODES], heavyChild[MAX_NODES], chainTop[MAX_NODES];
int subtreeSize[MAX_NODES];
void computeDepthsAndSizes(int node, int par) {
depth[node] = depth[par] + 1;
parent[node] = par;
subtreeSize[node] = 1;
heavyChild[node] = 0;
for (int neighbor : graph[node]) {
if (neighbor != par) {
computeDepthsAndSizes(neighbor, node);
subtreeSize[node] += subtreeSize[neighbor];
if (subtreeSize[neighbor] > subtreeSize[heavyChild[node]]) {
heavyChild[node] = neighbor;
}
}
}
}
void decomposeTree(int node, int topNode) {
chainTop[node] = topNode;
if (heavyChild[node]) {
decomposeTree(heavyChild[node], topNode);
}
for (int neighbor : graph[node]) {
if (neighbor != parent[node] && neighbor != heavyChild[node]) {
decomposeTree(neighbor, neighbor);
}
}
}
int findLCA(int u, int v) {
while (chainTop[u] != chainTop[v]) {
if (depth[chainTop[u]] < depth[chainTop[v]]) swap(u, v);
u = parent[chainTop[u]];
}
return depth[u] < depth[v] ? u : v;
}
int calculateDistance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[findLCA(u, v)];
}
bool isStarGraph(int nodeCount) {
for (int i = 1; i <= nodeCount; ++i) {
if ((int)graph[i].size() == nodeCount - 1) {
return true;
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int testCases, nodeCount, start, end;
cin >> testCases;
mt19937 rng(random_device{}());
while (testCases--) {
cin >> nodeCount >> start >> end;
for (int i = 1; i <= nodeCount; ++i) graph[i].clear();
for (int i = 1, u, v; i < nodeCount; ++i) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
depth[0] = -1;
computeDepthsAndSizes(1, 0);
decomposeTree(1, 1);
if (nodeCount <= 8) {
vector<int> perm(nodeCount + 1);
int minDist = INT_MAX;
vector<int> bestPath(nodeCount + 1);
for (int i = 1; i <= nodeCount; ++i) perm[i] = i;
do {
if (perm[1] != start || perm[nodeCount] != end) continue;
int currentDist = 0;
for (int i = 2; i <= nodeCount; ++i) {
currentDist ^= calculateDistance(perm[i], perm[i-1]);
}
if (currentDist < minDist) {
minDist = currentDist;
bestPath = perm;
}
} while (next_permutation(perm.begin() + 1, perm.begin() + nodeCount + 1));
for (int i = 1; i <= nodeCount; ++i) cout << bestPath[i] << " ";
cout << "\n";
} else {
vector<int> perm(nodeCount + 1);
perm[1] = start;
perm[nodeCount] = end;
int idx = 1;
for (int i = 1; i <= nodeCount; ++i) {
if (i != start && i != end) perm[idx++] = i;
}
if (isStarGraph(nodeCount)) {
for (int i = 1; i <= nodeCount; ++i) cout << perm[i] << " ";
cout << "\n";
continue;
}
int currentCost = 0;
for (int i = 2; i <= nodeCount; ++i) currentCost ^= calculateDistance(perm[i], perm[i-1]);
while (currentCost > 1) {
int pos1 = rng() % (nodeCount - 2) + 2;
int pos2 = rng() % (nodeCount - 2) + 2;
while (pos1 == pos2) pos2 = rng() % (nodeCount - 2) + 2;
currentCost ^= calculateDistance(perm[pos1], perm[pos1-1]);
currentCost ^= calculateDistance(perm[pos1], perm[pos1+1]);
currentCost ^= calculateDistance(perm[pos2], perm[pos2-1]);
currentCost ^= calculateDistance(perm[pos2], perm[pos2+1]);
swap(perm[pos1], perm[pos2]);
currentCost ^= calculateDistance(perm[pos1], perm[pos1-1]);
currentCost ^= calculateDistance(perm[pos1], perm[pos1+1]);
currentCost ^= calculateDistance(perm[pos2], perm[pos2-1]);
currentCost ^= calculateDistance(perm[pos2], perm[pos2+1]);
}
for (int i = 1; i <= nodeCount; ++i) cout << perm[i] << " ";
cout << "\n";
}
}
return 0;
}
P10813 Swap Operation
For sorting network problems, a classic technique involves transforming the sequence A_n into a binary representation B_n(V) where B_i(V) = [A_i ≤ V]. A sequence A is sortable if and only if all its binary representations B(V) are sortable.
Precomputation can determine the validity of all 2^n binary sequences, but this is O(m·2^n). Since only O(n) distinct values are meaningful after discretization, we use state-compressed DP. Let dp[i][S] be the number of ways to have the state S for threshold i, with at least one element equal to i. The transition involves filling the next value, which can be optimized using Sum-over-Subsets (SOS) DP to achieve O(n²·2^n).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int MAX_N = 18;
int nodeCount, maxVal, comparatorCount;
int inputX[MAX_N*2], inputY[MAX_N*2];
bool isValidState[1 << MAX_N];
ll stateDP[1 << MAX_N], sosDP[1 << MAX_N];
bool checkSortability(int stateMask) {
vector<bool> values(nodeCount + 1);
for (int i = 0; i < nodeCount; ++i) {
values[i+1] = (stateMask >> i) & 1;
}
for (int i = 0; i < comparatorCount; ++i) {
if (values[inputX[i]] > values[inputY[i]]) {
swap(values[inputX[i]], values[inputY[i]]);
}
}
for (int i = 1; i < nodeCount; ++i) {
if (values[i] > values[i+1]) return false;
}
return true;
}
ll modPow(ll base, ll exp) {
ll result = 1;
while (exp) {
if (exp & 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
ll nCr(ll n, ll r) {
if (r < 0 || r > n) return 0;
ll res = 1;
for (int i = 1; i <= r; ++i) {
res = res * (n - i + 1) % MOD;
res = res * modPow(i, MOD-2) % MOD;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> nodeCount >> maxVal >> comparatorCount;
for (int i = 0; i < comparatorCount; ++i) {
cin >> inputX[i] >> inputY[i];
}
for (int mask = 0; mask < (1 << nodeCount); ++mask) {
isValidState[mask] = checkSortability(mask);
}
stateDP[0] = 1;
ll totalAnswer = 0;
for (int val = 1; val <= nodeCount; ++val) {
fill(sosDP, sosDP + (1 << nodeCount), 0);
for (int mask = 0; mask < (1 << nodeCount); ++mask) {
sosDP[mask] = stateDP[mask];
}
for (int bit = 0; bit < nodeCount; ++bit) {
for (int mask = 0; mask < (1 << nodeCount); ++mask) {
if (mask & (1 << bit)) {
sosDP[mask] = (sosDP[mask] + sosDP[mask ^ (1 << bit)]) % MOD;
}
}
}
for (int mask = 0; mask < (1 << nodeCount); ++mask) {
stateDP[mask] = (sosDP[mask] - stateDP[mask] + MOD) % MOD;
if (!isValidState[mask]) stateDP[mask] = 0;
}
totalAnswer = (totalAnswer + nCr(maxVal, val) * stateDP[(1 << nodeCount) - 1]) % MOD;
}
cout << totalAnswer << "\n";
return 0;
}
The Only Survival
This problem involves constructing a graph where edge weights must satisfy w ∈ [dist(1,v) - dist(1,u), lim]. The solution uses a DFS over integer partitions to count valid configurations. For each partition of nodes into distance groups, we calculate the number of ways to assign edges, ensuring at least one edge meets the minimum weight requirement.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 15;
int nodeCount, distConstraint, weightLimit;
ll modulo;
ll partitionCounts[MAX_N];
ll finalAnswer;
ll modPow(ll base, ll exp) {
ll result = 1;
while (exp) {
if (exp & 1) result = result * base % modulo;
base = base * base % modulo;
exp >>= 1;
}
return result;
}
ll nCr(int n, int r) {
if (r < 0 || r > n) return 0;
ll res = 1;
for (int i = 1; i <= r; ++i) {
res = res * (n - i + 1) % modulo;
res = res * modPow(i, modulo-2) % modulo;
}
return res;
}
void explorePartitions(int currentDist, int nodesAssigned, ll currentWays) {
if (currentDist > distConstraint) {
ll term = 1;
for (int i = 0; i <= distConstraint; ++i) {
term = term * modPow(weightLimit - (distConstraint - i), partitionCounts[i]) % modulo;
}
finalAnswer = (finalAnswer + currentWays * modPow(term, nodeCount - nodesAssigned) % modulo * modPow(weightLimit, (nodeCount - nodesAssigned) * (nodeCount - nodesAssigned - 1LL) / 2) % modulo) % modulo;
return;
}
ll termBase = 1, termSubtract = 1;
for (int i = 0; i < currentDist; ++i) {
termBase = termBase * modPow(weightLimit - (currentDist - i) + 1, partitionCounts[i]) % modulo;
termSubtract = termSubtract * modPow(weightLimit - (currentDist - i), partitionCounts[i]) % modulo;
}
ll waysToAddGroup = (termBase - termSubtract + modulo) % modulo;
for (int groupSize = (currentDist == distConstraint ? 1 : 0); nodesAssigned + groupSize <= nodeCount; ++groupSize) {
partitionCounts[currentDist] = groupSize;
ll nextWays = currentWays * modPow(waysToAddGroup, groupSize) % modulo * modPow(weightLimit, groupSize * (groupSize - 1LL) / 2) % modulo * nCr(nodeCount - nodesAssigned - 1, groupSize - (currentDist == distConstraint ? 1 : 0)) % modulo;
explorePartitions(currentDist + 1, nodesAssigned + groupSize, nextWays);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> nodeCount >> distConstraint >> weightLimit >> modulo;
if (weightLimit < distConstraint) {
cout << "0\n";
return 0;
}
partitionCounts[0] = 1;
nodeCount--;
explorePartitions(1, 0, 1);
cout << finalAnswer << "\n";
return 0;
}
A Mysterious Formula
The problem asks for the number of ways to partition n distinct balls into identical boxes, with each box containing at least two balls. The solution uses Stirling numbers of the second kind and inclusion-exclusion.
The formula derived is: $$ ans = \sum_{i=0}^{n} \frac{(i-1)^n}{i!} \sum_{k=0}^{n-i} \frac{(-1)^k}{k!} $$
This can be computed in O(n) time by precomputing factorials and inverse factorials.
TEST_90: Interval History Sum
This problem involves querying the histoircal sum of an array. The solution models the problem with a segment tree, where each node stores the current sum, the historical sum, and the length. Updates (additive and XOR-like) are represented as matrix multiplications. To optimize, only the changing elements of the matrix are tracked.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_ARR = 1000005;
struct Matrix {
ll data[4];
Matrix() : data{0,0,0,0} {}
Matrix(ll a, ll b, ll c, ll d) : data{a, b, c, d} {}
ll& operator[](int i) { return data[i]; }
const ll& operator[](int i) const { return data[i]; }
};
Matrix multiply(const Matrix& a, const Matrix& b) {
return Matrix{
a[0]*b[1] + b[0],
a[1]*b[1],
a[2] + a[1]*b[2],
a[3] + b[3] + a[0]*b[2]
};
}
const Matrix IDENTITY_MATRIX = Matrix(0, 1, 0, 0);
Matrix getXorMatrix() { return Matrix(1, -1, 0, 0); }
Matrix getTimMatrix() { return Matrix(0, 1, 1, 0); }
struct Node {
ll currentSum, historicalSum, length;
Matrix lazyTag;
Node() : currentSum(0), historicalSum(0), length(0), lazyTag(IDENTITY_MATRIX) {}
} tree[MAX_ARR * 4];
Node mergeNodes(const Node& left, const Node& right) {
Node res;
res.currentSum = left.currentSum + right.currentSum;
res.historicalSum = left.historicalSum + right.historicalSum;
res.length = left.length + right.length;
return res;
}
Node applyMatrix(const Node& node, const Matrix& mat) {
Node res;
res.currentSum = node.currentSum * mat[1] + node.length * mat[0];
res.historicalSum = node.historicalSum + node.currentSum * mat[2] + node.length * mat[3];
res.length = node.length;
res.lazyTag = multiply(node.lazyTag, mat);
return res;
}
void buildTree(int idx, int left, int right) {
if (left == right) {
tree[idx] = Node{0, 0, 1, IDENTITY_MATRIX};
} else {
int mid = (left + right) / 2;
buildTree(idx*2, left, mid);
buildTree(idx*2+1, mid+1, right);
tree[idx] = mergeNodes(tree[idx*2], tree[idx*2+1]);
}
}
void pushDown(int idx) {
tree[idx*2] = applyMatrix(tree[idx*2], tree[idx].lazyTag);
tree[idx*2+1] = applyMatrix(tree[idx*2+1], tree[idx].lazyTag);
tree[idx].lazyTag = IDENTITY_MATRIX;
}
void updateTree(int idx, int segLeft, int segRight, int updateLeft, int updateRight, bool isTimUpdate) {
if (updateRight < segLeft || segRight < updateLeft) return;
if (updateLeft <= segLeft && segRight <= updateRight) {
tree[idx] = applyMatrix(tree[idx], isTimUpdate ? getTimMatrix() : getXorMatrix());
return;
}
pushDown(idx);
int mid = (segLeft + segRight) / 2;
updateTree(idx*2, segLeft, mid, updateLeft, updateRight, isTimUpdate);
updateTree(idx*2+1, mid+1, segRight, updateLeft, updateRight, isTimUpdate);
tree[idx] = mergeNodes(tree[idx*2], tree[idx*2+1]);
}
ll queryTree(int idx, int segLeft, int segRight, int queryLeft, int queryRight) {
if (queryRight < segLeft || segRight < queryLeft) return 0;
if (queryLeft <= segLeft && segRight <= queryRight) {
return tree[idx].historicalSum;
}
pushDown(idx);
int mid = (segLeft + segRight) / 2;
return queryTree(idx*2, segLeft, mid, queryLeft, queryRight) +
queryTree(idx*2+1, mid+1, segRight, queryLeft, queryRight);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int arrLen, queryNum;
cin >> arrLen;
vector<int> sequence(arrLen + 1), lastPos(arrLen + 1, 0);
for (int i = 1; i <= arrLen; ++i) cin >> sequence[i];
cin >> queryNum;
vector<vector<pair<int, int>>> queries(arrLen + 1);
for (int i = 1; i <= queryNum; ++i) {
int l, r; cin >> l >> r;
queries[r].push_back({l, i});
}
buildTree(1, 1, arrLen);
vector<ll> results(queryNum + 1);
for (int i = 1; i <= arrLen; ++i) {
if (lastPos[sequence[i]] != 0) {
updateTree(1, 1, arrLen, lastPos[sequence[i]] + 1, i, false);
}
updateTree(1, 1, arrLen, 1, i, true);
for (auto& query : queries[i]) {
results[query.second] = queryTree(1, 1, arrLen, query.first, i);
}
lastPos[sequence[i]] = i;
}
for (int i = 1; i <= queryNum; ++i) cout << results[i] << "\n";
return 0;
}
CF995F Cowmpany Cowmpensation
This is a counting problem on trees. We want to count the number of ways to assign labels from 1 to D to nodes such that the labels induce a surjective function onto their set. The solution uses a tree DP and inclusion-exclusion.
The DP state dp[i][j] represents the number of ways to label the subtree of i with labels up to j. The transition involves multiplying the prefix sums of children's DPs. Inclusion-exclusion is then applied to count only surjective functions.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_NODES = 3005;
const int MOD = 1000000007;
int nodeCount, maxLabel;
vector<int> children[MAX_NODES];
ll binomialCoeff[MAX_NODES][MAX_NODES];
ll dp[MAX_NODES][MAX_NODES], prefixSum[MAX_NODES][MAX_NODES];
ll exactCoverDP[MAX_NODES], finalAnswer;
ll modPow(ll base, ll exp) {
ll result = 1;
while (exp) {
if (exp & 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
ll nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return binomialCoeff[n][r];
}
void computeTreeDP(int node) {
for (int label = 1; label <= nodeCount; ++label) dp[node][label] = 1;
for (int child : children[node]) {
computeTreeDP(child);
for (int label = 1; label <= nodeCount; ++label) {
dp[node][label] = dp[node][label] * prefixSum[child][label] % MOD;
}
}
for (int label = 1; label <= nodeCount; ++label) {
prefixSum[node][label] = (prefixSum[node][label-1] + dp[node][label]) % MOD;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> nodeCount >> maxLabel;
for (int i = 2; i <= nodeCount; ++i) {
int parent; cin >> parent;
children[parent].push_back(i);
}
for (int i = 0; i <= nodeCount; ++i) {
binomialCoeff[i][0] = 1;
for (int j = 1; j <= i; ++j) {
binomialCoeff[i][j] = (binomialCoeff[i-1][j] + binomialCoeff[i-1][j-1]) % MOD;
}
}
computeTreeDP(1);
exactCoverDP[1] = 1;
finalAnswer = maxLabel % MOD;
for (int labelSetSize = 2; labelSetSize <= min(nodeCount, maxLabel); ++labelSetSize) {
exactCoverDP[labelSetSize] = dp[1][labelSetSize];
for (int j = 1; j < labelSetSize; ++j) {
exactCoverDP[labelSetSize] = (exactCoverDP[labelSetSize] - nCr(labelSetSize-1, j-1) * exactCoverDP[j] % MOD + MOD) % MOD;
}
ll term = modPow(maxLabel, labelSetSize);
for (int i = 0; i < labelSetSize; ++i) term = term * (maxLabel - i) % MOD;
term = term * modPow(modPow(labelSetSize, MOD-2), labelSetSize) % MOD;
finalAnswer = (finalAnswer + term * exactCoverDP[labelSetSize]) % MOD;
}
cout << finalAnswer << "\n";
return 0;
}
Tree Tweaking
Given a permutation used to build a BST, we can rearrange a contiguous subarray of insertions. The goal is to minimize the sum of node depths. The insight is that the sum of depths equals the sum of subtree sizes. The subtree size of a node is determined by its predecessor and successor in the value space.
The problem reduces to dividing the value space into segments and using DP on each segment to find the optimal insertion order. The DP state dp[l][r] computes the minimal contribution for inserting keys in a segment.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100005;
const int MAX_SEG = 205;
int nodeCount;
int insertOrder[MAX_N];
int rearrangeL, rearrangeR;
ll minDepthSum;
set<int> valueSet;
vector<int> segmentValues[MAX_N];
void addValue(int val) {
auto successor = valueSet.upper_bound(val);
auto predecessor = successor;
predecessor--;
minDepthSum += (*successor - *predecessor - 1);
valueSet.insert(val);
}
ll computeSegmentDP(int leftBound, int rightBound) {
vector<int> values;
values.push_back(leftBound);
sort(segmentValues[rightBound].begin(), segmentValues[rightBound].end());
for (int val : segmentValues[rightBound]) values.push_back(val);
values.push_back(rightBound);
int valCount = values.size() - 1;
vector<vector<ll>> dp(valCount, vector<ll>(valCount, 1e9));
for (int len = 1; len < valCount; ++len) {
for (int i = 1; i + len - 1 < valCount - 1; ++i) {
int j = i + len - 1;
for (int k = i; k <= j; ++k) {
ll cost = (k > i ? dp[i][k-1] : 0) + (k < j ? dp[k+1][j] : 0);
if (cost < dp[i][j]) {
dp[i][j] = cost;
}
}
dp[i][j] += values[j+1] - values[i-1] - 1;
}
}
return dp[1][valCount-2];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> nodeCount;
for (int i = 1; i <= nodeCount; ++i) cin >> insertOrder[i];
cin >> rearrangeL >> rearrangeR;
valueSet.insert(0);
valueSet.insert(nodeCount + 1);
for (int i = 1; i < rearrangeL; ++i) addValue(insertOrder[i]);
for (int i = rearrangeL; i <= rearrangeR; ++i) {
int pred = *valueSet.lower_bound(insertOrder[i]);
segmentValues[pred].push_back(insertOrder[i]);
}
for (auto it = valueSet.begin(); it != valueSet.end(); ) {
auto prevIt = it;
++it;
if (prevIt != valueSet.begin() && !segmentValues[*prevIt].empty()) {
minDepthSum += computeSegmentDP(*prev(prevIt), *prevIt);
}
}
for (int i = rearrangeL; i <= rearrangeR; ++i) valueSet.insert(insertOrder[i]);
for (int i = rearrangeR + 1; i <= nodeCount; ++i) addValue(insertOrder[i]);
cout << minDepthSum << "\n";
return 0;
}
Chords
This problem counts non-crossing chord diagrams on a circle. The solution uses an interval DP where each interval [l, r] represents a connected component. The DP calculates the number of valid pairings within the interval, subtracting disconnected configurations.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_POINTS = 605;
const int MOD = 1000000007;
template<int mod>
struct ModInt {
int val;
ModInt(int v = 0) : val(v % mod) { if (val < 0) val += mod; }
ModInt operator+(ModInt o) { return ModInt(val + o.val); }
ModInt operator-(ModInt o) { return ModInt(val - o.val); }
ModInt operator*(ModInt o) { return ModInt((ll)val * o.val % mod); }
static ModInt power(ModInt a, int e) { /* ... */ }
};
typedef ModInt<MOD> mint;
int pointCount, chordCount;
int partner[MAX_POINTS];
int freePointsInInterval[MAX_POINTS][MAX_POINTS];
mint intervalDP[MAX_POINTS][MAX_POINTS], pairingCounts[MAX_POINTS];
mint totalDiagrams;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> pointCount >> chordCount;
pointCount *= 2;
pairingCounts[0] = 1;
for (int i = 2; i <= pointCount; i += 2) {
pairingCounts[i] = pairingCounts[i-2] * (i - 1);
}
for (int i = 1; i <= chordCount; ++i) {
int u, v; cin >> u >> v;
partner[u] = v; partner[v] = u;
}
for (int l = 1; l <= pointCount; ++l) {
freePointsInInterval[l][l-1] = 0;
for (int r = l; r <= pointCount; ++r) {
freePointsInInterval[l][r] = freePointsInInterval[l][r-1] + (partner[r] ? 0 : 1);
}
}
for (int len = 2; len <= pointCount; len += 2) {
for (int l = 1; l + len - 1 <= pointCount; ++l) {
int r = l + len - 1;
bool isComponent = true;
for (int k = l; k <= r; ++k) {
if (partner[k] && (partner[k] < l || partner[k] > r)) {
isComponent = false;
break;
}
}
if (!isComponent) continue;
intervalDP[l][r] = pairingCounts[freePointsInInterval[l][r]];
for (int k = l + 1; k < r; k += 2) {
intervalDP[l][r] = intervalDP[l][r] - intervalDP[l][k] * pairingCounts[freePointsInInterval[k+1][r]];
}
totalDiagrams = totalDiagrams + intervalDP[l][r] * pairingCounts[pointCount - 2*chordCount - freePointsInInterval[l][r]];
}
}
cout << totalDiagrams.val << "\n";
return 0;
}
[SCOI2016] Adorable
This problem involves stamping numbers with constraints on digit positions. The solution uses a union-find data structure optimized with a logarithmic decomposition (similar to ST tables) to efficiently merge intervals of positions. Relations are propagated from larger intervals down to single digits.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_LEN = 100005;
const int LOG = 18;
const int MOD = 1000000007;
template<int size>
struct UnionFind {
int parent[size], rank[size];
void reset(int n) { for (int i = 1; i <= n; ++i) parent[i] = i, rank[i] = 0; }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) parent[x] = y;
else { parent[y] = x; if (rank[x] == rank[y]) rank[x]++; }
}
bool connected(int x, int y) { return find(x) == find(y); }
} ufLayers[LOG];
int numberLength, stampCount;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> numberLength >> stampCount;
for (int i = 0; i < LOG; ++i) ufLayers[i].reset(numberLength);
for (int i = 1, a, b, c, d; i <= stampCount; ++i) {
cin >> a >> b >> c >> d;
for (int k = LOG - 1; k >= 0; --k) {
if (a + (1 << k) - 1 <= b) {
ufLayers[k].unite(a, c);
a += (1 << k);
c += (1 << k);
}
}
}
for (int k = LOG - 1; k > 0; --k) {
for (int i = 1; i + (1 << k) - 1 <= numberLength; ++i) {
int root = ufLayers[k].find(i);
ufLayers[k-1].unite(i, root);
ufLayers[k-1].unite(i + (1 << (k-1)), root + (1 << (k-1)));
}
}
ll result = 9;
for (int i = 2; i <= numberLength; ++i) {
if (ufLayers[0].find(i) == i) {
result = result * 10 % MOD;
}
}
cout << result << "\n";
return 0;
}