Create your own test cases and solve them! What can you observe?

What is the length of the $$$n$$$-th stick?

Can we do something similar for the remaining sticks?

So the algorithm is as follows:

1. Initialize an array $$$b = [1, 2, \ldots, n]$$$. This represents the lengths of the remaining sticks.
2. For each $$$i$$$ from $$$n - 1$$$ to $$$1$$$:
   • If $$$s_i = \texttt{ \lt }$$$, then set $$$a_{i + 1} = \min(b)$$$.
   • If $$$s_i = \texttt{ \gt }$$$, then set $$$a_{i + 1} = \max(b)$$$.
   • Now remove $$$a_{i + 1}$$$ from $$$b$$$, and continue.
3. In the end, we have $$$1$$$ remaining element in $$$b$$$. This is the value of $$$a_1$$$.

The time complexity of this solution is $$$O(n^2)$$$.

We can notice that at any point, $$$b$$$ has the form $$$[l, l + 1, \ldots, r]$$$.

So we can represent $$$b$$$ using two integers $$$l$$$ and $$$r$$$:

• When we remove $$$\min(b)$$$, we increase $$$l$$$ by $$$1$$$.
• When we remove $$$\max(b)$$$, we decrease $$$r$$$ by $$$1$$$.

Now the time complexity of our solution is $$$O(n)$$$.

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int l = 1;
    int r = n;
    vector<int> a(n);
    for (int i = n - 2; i >= 0; i--) {
        if (s[i] == '<') {
            a[i + 1] = l;
            l++;
        }
        if (s[i] == '>') {
            a[i + 1] = r;
            r--;
        }
    }
    a[0] = l;

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}

Let's look at the third test case in the example. We have $$$k = 2$$$, and the answer is $$$x = 303$$$. If we take out $$$302$$$ gloves, then it's possible that we only have matching pairs of $$$1$$$ color.

How can we generalize this fact for any $$$k$$$ and $$$x$$$?

So we can solve the problem as follows:

• Let $$$y$$$ be the maximum number of gloves we can take out so that there are at most $$$(k - 1)$$$ matching pairs of different colors. Then the answer to the problem is $$$x = y + 1$$$.

Set $$$m = k - 1$$$. Now we need to find the maximum number of gloves so that there are at most $$$m$$$ matching pairs of different colors.

Try solving it for $$$m = 0$$$ first.

When $$$m = 0$$$, we want to find the maximum number of gloves so that there are no matching pairs.

Therefore, for each color $$$i$$$, we can either take all the left gloves, or all the right gloves. So we should choose the type with more gloves.

Formally, let $$$a_i = \max(l_i, r_i)$$$. Then the maximum number of gloves we can take is $$$y = a_1 + a_2 + \ldots + a_n$$$.

Now, using the solution for $$$m = 0$$$, solve it for $$$m = 1$$$. Then solve it for $$$m = 2$$$, and so on.

When $$$m = 0$$$, we take $$$a_i$$$ gloves of color $$$i$$$. So we're left with $$$b_i = \min(l_i, r_i)$$$ gloves of color $$$i$$$ that we haven't taken.

To get from $$$m = 0$$$ to $$$m = 1$$$, we can additionally form matching pairs of $$$1$$$ color. Therefore, we can choose a color $$$i$$$, and take the remaining $$$b_i$$$ gloves. So we should choose the color $$$i$$$ with the maximum value of $$$b_i$$$.

In other words, for $$$m = 1$$$, the maximum number of gloves we can take is $$$y = a_1 + a_2 + \ldots + a_n + \max(b_1, b_2, \ldots, b_n)$$$.

To get from $$$m = 0$$$ to $$$m = 2$$$, we can additionally form matching pairs of $$$2$$$ different colors. Therefore, we can choose two different colors $$$i$$$ and $$$j$$$, and take the remaining $$$b_i + b_j$$$ gloves. So we should choose the two colors $$$i$$$ and $$$j$$$ with the maximum value of $$$b_i + b_j$$$.

We can generalize this idea for any $$$m$$$.

So the algorithm is as follows:

1. Set $$$m = k - 1$$$.
2. For each $$$i$$$ from $$$1$$$ to $$$n$$$, let $$$a_i = \max(l_i, r_i)$$$ and $$$b_i = \min(l_i, r_i)$$$.
3. Set $$$y = a_1 + a_2 + \ldots + a_n$$$.
4. Sort the values of $$$b$$$ in descending order.
5. Add the $$$m$$$ largest values of $$$b$$$ to $$$y$$$.
6. The answer is $$$x = y + 1$$$.

The time complexity of this solution is $$$O(n \log n)$$$.

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n, k;
    cin >> n >> k;
    int m = k - 1;

    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    vector<int> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    vector<int> a(n), b(n);
    long long y = 0;
    for (int i = 0; i < n; i++) {
        a[i] = max(l[i], r[i]);
        b[i] = min(l[i], r[i]);
        y += a[i];
    }

    sort(b.begin(), b.end(), greater<>());
    for (int i = 0; i < m; i++) {
        y += b[i];
    }

    long long x = y + 1;
    cout << x << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}

We are given an $$$n \times n$$$ matrix of positive integers. There are two types of operations we can perform:

• When we hire worker $$$i$$$ from company A, let's call it row operation $$$i$$$.
• When we hire worker $$$j$$$ from company B, let's call it column operation $$$j$$$.

Each row and column operation can be performed at most once.

After performing the operations, the matrix must satisfy the following:

• Horizontal Condition: No two horizontally adjacent elements are the same.
• Vertical Condition: No two vertically adjacent elements are the same.

Suppose the matrix does not satisfy the Horizontal Condition, so there is a position $$$(i, j)$$$ such that $$$h_{i,j} = h_{i, j + 1}$$$.

What operations can we perform to fix this? Don't worry about other positions for now. We just want $$$h_{i,j} \neq h_{i, j + 1}$$$.

We can either:

• Only perform column operation $$$j$$$, and increase $$$h_{i, j}$$$ by $$$1$$$;
• Or only perform column operation $$$(j + 1)$$$, and increase $$$h_{i, j + 1}$$$ by $$$1$$$.

Notice that when we perform row operation $$$i$$$, we increase both $$$h_{i, j}$$$ and $$$h_{i, j + 1}$$$ by $$$1$$$. Therefore, the difference between the two elements does not change.

Formally, when we perform row operation $$$i$$$, the value $$$d = h_{i, j} - h_{i, j + 1}$$$ does not change.

From our previous observations, we see that:

• Only column operations affect the Horizontal Condition.
• Only row operations affect the Vertical Condition.

So we can solve for the Horizontal Condition and the Vertical Condition independently.

Using DP, we will calculate:

• The minimum total cost of the row operations required to satisfy the Vertical Condition.
• The minimum total cost of the column operations required to satisfy the Horizontal Condition.

To get the answer, we add the two costs.

Let $$$dp(i, x)$$$ be the minimum total cost of the row operations required so that:

• The first $$$i$$$ rows of the matrix satisfy the Vertical Condition.
• If $$$x = 0$$$, then we do not perform row operation $$$i$$$.
• If $$$x = 1$$$, then we perform row operation $$$i$$$.

If it is impossible, then $$$dp(i, x) = \infty$$$.

Our base cases are $$$dp(1, 0) = 0$$$ and $$$dp(1, 1) = a_1$$$.

For $$$i \gt 1$$$, initialize $$$dp(i, x)$$$ to $$$\infty$$$. Our $$$dp(i, x)$$$ will depend on some $$$dp(i - 1, y)$$$.

Now we need to check if row $$$(i - 1)$$$ and row $$$i$$$ satisfy the Vertical Condition:

• The elements in row $$$i - 1$$$ are: $$$(h_{i - 1, 1} + y), (h_{i - 1, 2} + y), \ldots, (h_{i - 1, n} + y)$$$.
• The elements in row $$$i$$$ are: $$$(h_{i, 1} + x), (h_{i, 2} + x), \ldots, (h_{i, n} + x)$$$.

If no two vertically adjacent elements are the same, then:

• For $$$x = 0$$$, set $$$dp(i, x) = \min(dp(i, x), dp(i - 1, y))$$$.
• For $$$x = 1$$$, set $$$dp(i, x) = \min(dp(i, x), dp(i - 1, y) + a_i)$$$.

The minimum total cost required so that the entire matrix satisfies the Vertical Condition is $$$\min(dp(n, 0), dp(n, 1))$$$.

Similarly, we can solve for the Horizontal Condition.

The time complexity of this solution is $$$O(n^2)$$$.

To avoid repetition, we can solve for the Horizontal Condition by transposing the matrix and treating it as the Vertical Condition instead.

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

long long solveHor(int n, vector<vector<int>>& h, vector<int>& a) {
    vector<vector<long long>> dp(n, vector<long long>(2, INF));
    dp[0][0] = 0;
    dp[0][1] = a[0];

    for (int i = 1; i < n; i++) {
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 2; y++) {
                bool ok = true;
                for (int j = 0; j < n; j++) {
                    ok &= (h[i - 1][j] + y != h[i][j] + x);
                }
                if (ok) {
                    if (x == 0) {
                        dp[i][x] = min(dp[i][x], dp[i - 1][y]);
                    }
                    if (x == 1) {
                        dp[i][x] = min(dp[i][x], dp[i - 1][y] + a[i]);
                    }
                }
            }
        }
    }

    return min(dp[n - 1][0], dp[n - 1][1]);
}

void transpose(int n, vector<vector<int>>& h) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            swap(h[i][j], h[j][i]);
        }
    }
}

void test() {
    int n;
    cin >> n;

    vector<vector<int>> h(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> h[i][j];
        }
    }

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    long long horCost = solveHor(n, h, a);
    transpose(n, h);
    long long verCost = solveHor(n, h, b);
    long long totalCost = horCost + verCost;

    if (totalCost >= INF) {
        cout << -1 << '\n';
    }
    else {
        cout << totalCost << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}

What can we say about the number of lightbulbs that are turned on for any valid configuration in the input?

Can the number of lightbulbs that are turned on be even?

Let's use the idea of parity to come up with stricter conditions.

Consider the lightbulbs on the vertical line $$$x = c$$$. What can we say about the number of lightbulbs that are turned on?

From our previous observations, we can uniquely determine the value of $$$s$$$. Can we do the same for the value of $$$t$$$?

Consider the lightbulbs on the diagonal line $$$x + y = c$$$. What can we say about the number of lightbulbs that are turned on?

So, to summarize, we find two lines:

• The vertical line that has an odd number of lightbulbs turned on
• The diagonal line that has an odd number of lightbulbs turned on

The intersection of these two lines is the position of the treasure.

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n;
    cin >> n;

    map<int, int> cntVer, cntDiag;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        cntVer[x]++;
        cntDiag[x + y]++;
    }

    int s;
    for (auto [c, cnt]: cntVer) {
        if (cnt % 2 == 1) {
            s = c;
            break;
        }
    }

    int t;
    for (auto [c, cnt]: cntDiag) {
        if (cnt % 2 == 1) {
            t = c - s;
            break;
        }
    }

    cout << s << " " << t << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}

First, we'll treat all the black teddy bears as $$$0$$$ and all the pink teddy bears as $$$1$$$.

So we are given a binary array of length $$$n$$$. In one operation, we can choose three consecutive elements and sort them in ascending order. Now we need to find the minimum number of operations required to sort the array.

There are four possible types of operations, depending on the values of the elements:

• Operation A: $$$(0, 1, 0) \rightarrow (0, 0, 1)$$$
• Operation B: $$$(1, 0, 0) \rightarrow (0, 0, 1)$$$
• Operation C: $$$(1, 0, 1) \rightarrow (0, 1, 1)$$$
• Operation D: $$$(1, 1, 0) \rightarrow (0, 1, 1)$$$

Let's think of a greedy solution first. Which operations are better than others?

We can evaluate an operation by how much it reduces the number of inversions in the array:

• Operation A reduces the number of inversions by $$$1$$$.
• Operation B reduces the number of inversions by $$$2$$$.
• Operation C reduces the number of inversions by $$$1$$$.
• Operation D reduces the number of inversions by $$$2$$$.

Therefore, ideally, we'd only perform operations B and D.

Let $$$x$$$ be the number of inversions in the original array. Then the answer is at least $$$\left\lceil \frac{x}{2} \right\rceil$$$.

Suppose we keep performing operations B and D until we can no longer do so. What will the array look like?

Since the array has a sequence of alternating $$$1$$$'s and $$$0$$$'s, we should think about parity.

Let $$$a$$$ be the number of $$$0$$$'s in the entire array, and $$$b$$$ be the number of $$$0$$$'s in the even positions.

When the array is sorted, all the $$$0$$$'s will be at the beginning of the array. So in the end, $$$b = \left\lfloor \frac{a}{2} \right\rfloor$$$.

Consider how each type of operation changes the value of $$$b$$$:

• Operation A either increases or decreases the value of $$$b$$$ by $$$1$$$.
• Operation B does not change the value of $$$b$$$.
• Operation C either increases or decreases the value of $$$b$$$ by $$$1$$$.
• Operation D does not change the value of $$$b$$$.

Therefore, we can only use operations A and C to change the value of $$$b$$$.

Let $$$d = \lvert \, \left\lfloor \frac{a}{2} \right\rfloor - b \, \rvert$$$. Then we need at least $$$d$$$ operations of type A or type C.

After these $$$d$$$ operations, the array will have $$$(x - d)$$$ inversions. We can show that $$$(x - d)$$$ must be even.

Then, we perform $$$\frac{x - d}{2}$$$ operations of type B or type D to reduce the number of inversions to $$$0$$$.

So the answer to the problem is: $$$d + \frac{x - d}{2} = \frac{x + d}{2}$$$.

#include <bits/stdc++.h>
using namespace std;

void test() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    long long x = 0;
    int a = 0;
    int b = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'B') {
            a++;
            if ((i + 1) % 2 == 0) {
                b++;
            }
        }
        if (s[i] == 'P') {
            x += a;
        }
    }

    int d = abs(a / 2 - b);
    cout << (x + d) / 2 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        test();
    }
    
    return 0;
}

Let's call a set of statements satisfiable if it's possible that all of them are true.

How do we check if a set of statements is satisfiable?

When a segment of statements $$$[s_l, s_r]$$$ is satisfiable, what can we say about other segments of statements?

We'll use the two pointers method. For each $$$s_r$$$, let $$$low(s_r)$$$ be the smallest $$$s_l$$$ such that $$$[s_l, s_r]$$$ is satisfiable. To answer a question $$$s_l\,s_r$$$, we just check that $$$s_l \geq low(s_r)$$$.

When we increment $$$s_r$$$, we will add statement $$$(s_r + 1)$$$. So we must increment $$$s_l$$$ and remove statements from the beginning of the segment until $$$[s_l, s_r + 1]$$$ is satisfiable.

Now we need to efficiently check if we can add a new statement to our current set of statements.

Let's rephrase how to determine if a set of statements is satisfiable.

• For statements of the form $$$0\,a_l\,a_r$$$, we'll call $$$[a_l, a_r]$$$ a $$$0$$$-segment.

• Similarly, for statements of the form $$$1\,b_l\,b_r$$$, we'll call $$$[b_l, b_r]$$$ a $$$1$$$-segment.

• When $$$0$$$-segments overlap and form a larger segment, we'll call it a $$$0$$$-component.

Then, a set of statements is satisfiable if there does not exist a $$$1$$$-segment that is fully covered by a $$$0$$$-component.

When we add a $$$1$$$-segment $$$[b_l, b_r]$$$, we need to check if it will be fully covered by a $$$0$$$-component.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, let $$$count(i)$$$ be the number of $$$0$$$-segments that contain viewer $$$i$$$.

Then, we can add $$$[b_l, b_r]$$$ if $$$\min(count(b_l), count(b_l + 1), \ldots, count(b_r)) = 0$$$.

The values of $$$count(i)$$$ can be maintained using a segment tree.

When we add a $$$0$$$-segment $$$[a_l, a_r]$$$, it might merge several $$$0$$$-components. So first we need to find the $$$0$$$-component $$$[c_l, c_r]$$$ that contains $$$[a_l, a_r]$$$:

• $$$c_l$$$ is the smallest value such that $$$\min(count(c_l), count(c_l + 1), \ldots, count(a_l)) \gt 0$$$.
• $$$c_r$$$ is the largest value such that $$$\min(count(a_r), count(a_r + 1), \ldots, count(c_r)) \gt 0$$$.

Both of these values can be found by performing a walk on the segment tree.

Now we need to check if there's a $$$1$$$-segment that's fully covered by $$$[c_l, c_r]$$$.

Sort all the $$$1$$$-segments in the input by ascending value of $$$b_r$$$.

Then, for all segments that satisfy $$$b_r \leq c_r$$$, find the one with largest value of $$$b_l$$$. If $$$b_l \geq c_l$$$, then $$$[b_l, b_r]$$$ is fully covered by $$$[c_l, c_r]$$$.

We can maintain another segment tree with prefix-max queries.

First, try solving it if Alice doesn't ignore any queries.

We can represent the queries using a table. Let's look at the second test case in the example:

Each row is a query. Column $$$x$$$ contains Alice's responses if her number was $$$x$$$.

Let's treat $$$\texttt{L}$$$ as $$$-1$$$, $$$\texttt{R}$$$ as $$$1$$$, and $$$\texttt{N}$$$ as $$$0$$$.

Then, our strategy works if each row has a sum of $$$0$$$ and all $$$n$$$ columns are distinct.

Since there are only $$$3$$$ possible values, we need at least $$$q = \left\lceil \log_3(n) \right\rceil$$$ queries. In fact, this lower bound can be achieved.

We generate all $$$3^{q}$$$ possible columns: $$$[x_1, x_2, \ldots, x_q]$$$, where $$$x_i \in$$$ $$$\text{\{}$$$$$$-1, 0, 1$$$$$$\text{\}}$$$.

Now we need to choose $$$n$$$ of them so that they sum to $$$0$$$.

To do this, we can choose one pair of columns at a time:

• First, we choose $$$[x_1, x_2, \ldots, x_q]$$$;
• Then, we choose $$$[-x_1, -x_2, \ldots, -x_q]$$$.

We see that each pair of columns sums to $$$0$$$.

If $$$n$$$ is odd, we can include $$$[0, 0, \ldots, 0]$$$.

Now let's try to solve the original problem. For our strategy to work, it must satisfy the following:

• Each row has a sum of $$$0$$$.
• No two columns are the same.
• No two columns differ by exactly $$$1$$$ element.

To achieve this, we only need $$$1$$$ additional query.

Here's another way to think about it:

• For each column, no matter which element is ignored, we should be able to uniquely determine the missing value.

We use the same solution as before, but with $$$1$$$ more element:

• For each column $$$[x_1, x_2, \ldots, x_q]$$$, add an element $$$x_{q + 1}$$$ such that $$$(x_1 + x_2 + \ldots + x_{q + 1})\mod 3 = 0$$$.

Because the sum of each column is $$$0$$$ modulo $$$3$$$, we can uniquely recover any missing element.

Is this FFT?

Let's consider the XOR convolution. Given two polynomials $$$A(x)$$$ and $$$B(x)$$$ with degree at most $$$(2^{m} - 1)$$$, the XOR convolution $$$C(x) = A(x) \star B(x)$$$ is defined as follows:

To efficiently compute the XOR convolution, we can use FWHT.

First, let $$$s(k, i) = (-1)^{\text{popcount}(k\,\&\,i)}$$$.

Then, $$$F(A(x))$$$ is defined as follows:

Given $$$A^{\,\prime}(x) = F(A(x))$$$, we can uniquely determine $$$A(x) = F^{-1}(A^{\,\prime}(x))$$$ using the inverse of FWHT.

To compute $$$F(A(x))$$$ and $$$F^{-1}(A^{\,\prime}(x))$$$, we can use SOS DP.

Define the dot product $$$D(x) = A(x) \cdot B(x)$$$ as follows: $$$\displaystyle [x^k]D(x) = [x^k]A(x) \cdot [x^k]B(x)$$$

We can show that $$$F(A(x) \star B(x)) = F(A(x)) \cdot F(B(x))$$$ for any two polynomials $$$A(x)$$$ and $$$B(x)$$$.

Let's solve the problem. For each interval $$$[l_i, r_i]$$$, let $$$A_i(x) = x^{l_i} + x^{l_i + 1} + \ldots + x^{r_i}$$$.

We want to find $$$A_1(x) \star A_2(x) \star \ldots \star A_n(x)$$$. To do this, we'll compute $$$F^{-1}(F(A_1(x)) \cdot F(A_2(x)) \cdot \ldots \cdot F(A_n(x)))$$$.

We can note that $$$\displaystyle [x^k]F(A_i(x)) = \sum_{l_i \leq j \leq r_i} s(k, j)$$$

Let $$$f(k, r) = \displaystyle \sum_{0 \leq j \leq r} s(k, j)$$$. Then $$$\displaystyle [x^k]F(A_i(x)) = f(k, r_i) - f(k, l_i - 1)$$$.

Now we need to find a way to compute $$$f(k, r)$$$ efficiently.

Let $$$p$$$ be the ($$$0$$$-indexed) position of the least significant bit of $$$k$$$.

Let $$$c = \left\lfloor \frac{r}{2^{p + 1}} \right\rfloor$$$. Then $$$f(k, r) = \displaystyle f(k, c \cdot 2^{p+1} - 1) + \sum_{c \cdot 2^{p + 1} \leq j \leq r} s(k, j)$$$

Due to cancellation of terms, we have $$$f(k, c \cdot 2^{p+1} - 1) = 0$$$.

We can also see that $$$s(k, j) = s(2^p, j) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, \left\lfloor \frac{j}{2^{p + 1}} \right\rfloor\right) = s(2^p, j) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, c\right)$$$

Therefore, $$$\displaystyle f(k, r) = \left(\sum_{c \cdot 2^{p + 1} \leq j \leq r} s(2^p, j)\right) \cdot s\left(\left\lfloor \frac{k}{2^{p + 1}} \right\rfloor, c\right)$$$.

Returning to $$$F(A_i(x))$$$, we get:

where:

• $$$a_i$$$ and $$$b_i$$$ are constants independent of $$$k$$$.
• $$$k^{\,\prime} = \left\lfloor \frac{k}{2^{p + 1}} \right\rfloor$$$, $$$c_i = \left\lfloor \frac{r_i}{2^{p + 1}} \right\rfloor$$$, and $$$d_i = \left\lfloor \frac{l_i - 1}{2^{p + 1}} \right\rfloor$$$.

But wait! This is just $$$[x^{k^{\,\prime}}]F(a_i \cdot x^{c_i} + b_i \cdot x^{d_i})$$$. So we'll let $$$B_i(x) = a_i \cdot x^{c_i} + b_i \cdot x^{d_i}$$$.

Therefore,

Now we need to find a way to compute $$$F(B_1(x) \star B_2(x) \star \ldots \star B_n(x))$$$ efficiently.

First, we can normalize each polynomial: $$$a \cdot x^c + b \cdot x^d = (a + b \cdot x^{c\,\oplus\,d}) \star x^c$$$

Now all polynomials have the form $$$a_i + b_i \cdot x^{c_i}$$$.

Next, we can convolve polynomials with matching powers of $$$x$$$:

Now the expression is of the form:

Finally, we have:

This can be computed using SOS DP.