Problem D: Weighted Permutation Sum

Given a sequence of numbers, consider generating all its non-empty subsequences, constructing a permutation by repeatedly removing the last element until one remains, and summing the final remaining numbers across all such processes. The problem requires computing the total sum over all subsequences.

For analysis, consider a sorted array vals of length n with elements v_1 ≤ v_2 ≤ ... ≤ v_n. Define coefficient array coeff = [1, 1, 2, 4, 8, ..., 2^{n-2}] for n≥2, where coeff[j] corresponds to the multiplier for the element at position j in the final order after deletions. The contribution for a specific subsequence, when sorted, is the dot product Σ (v_i * coeff_i).

We need to compute the total contribution of each original element v_i across all subsequences where it appears.

• Within the subsequence containing v_i, there are i-1 smaller elements and n-i larger elements.
• To have v_i occupy the j-th position in the sorted subsequence, we must choose exactly j-1 smaller elements from the i-1 available. This selection can be done in C(i-1, j-1) ways.
• The coefficient at position j is coeff[j].
• The n-i larger elements can be either included or excluded independently, contributing a factor of 2^{n-i}.
• Therefore, the total contribution of v_i is v_i * Σ_{j=1}^{i} [C(i-1, j-1) * coeff[j] * 2^{n-i}].

Simplify the inner sum S(i) = Σ_{j=1}^{i} C(i-1, j-1) * coeff[j]. Since coeff[1] = 1 and for j ≥ 2, coeff[j] = 2^{j-2}:

S(i) = Σ_{j=2}^{i} C(i-1, j-1) * 2^{j-2} + C(i-1, 0) * 1
Let k = j - 1. Then j ≥ 2 => k ≥ 1.
S(i) = Σ_{k=1}^{i-1} C(i-1, k) * 2^{k-1} + 1
     = (1/2) * Σ_{k=1}^{i-1} C(i-1, k) * 2^{k} + 1
By the binomial theorem, Σ_{k=0}^{i-1} C(i-1, k) * 2^{k} = (1+2)^{i-1} = 3^{i-1}.
Thus Σ_{k=1}^{i-1} C(i-1, k) * 2^{k} = 3^{i-1} - C(i-1, 0)*2^{0} = 3^{i-1} - 1.
Therefore S(i) = (3^{i-1} - 1) / 2 + 1 = (3^{i-1} + 1) / 2.

Consequently, the total contribution of element v_i is v_i * ((3^{i-1} + 1) / 2) * 2^{n-i}. The overall answer is the sum of these contributions for all i from 1 to n.

Implementation uses a modular integer class ModInt.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

struct ModNum {
    ll val;
    ModNum(ll v = 0) { val = (v % MOD + MOD) % MOD; }
    ModNum operator+(ModNum o) const { return ModNum(val + o.val); }
    ModNum operator-(ModNum o) const { return ModNum(val - o.val); }
    ModNum operator*(ModNum o) const { return ModNum(val * o.val); }
    ModNum operator/(ModNum o) const { return *this * o.inv(); }
    ModNum pow(ll e) const {
        ModNum res(1), base(val);
        while (e) {
            if (e & 1) res = res * base;
            base = base * base;
            e >>= 1;
        }
        return res;
    }
    ModNum inv() const { return pow(MOD - 2); }
    friend ostream& operator<<(ostream& os, ModNum m) { return os << m.val; }
};

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    ModNum total(0);
    for (int idx = 0; idx < n; idx++) {
        int i = idx + 1; // 1-based index for formula
        ModNum coeff = (ModNum(3).pow(i - 1) + 1) / ModNum(2);
        ModNum factor = coeff * ModNum(2).pow(n - i);
        total = total + ModNum(arr[idx]) * factor;
    }
    cout << total << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) solve();
    return 0;
}

Problem E: Count of Sequences with Pairwise XOR Zero

Construct sequences of length n where each element is an integer from 0 to 2^m - 1. The condition is that for every adjacent pair (x, y), the bitwise XOR x ^ y must equal zero, implying x == y. Additionally, the sequence must not consist entirely of identical numbers (i.e., it cannot be a constant sequence). Count the number of valid sequences modulo a prime.

Let total = 2^m be the number of choices for a single element. We derive a recurrence. Let dp_len denote the number of valid sequences of length len. For a sequence of length n:

• The first element can be any of the total values.
• For positions 2 to n-1, each element must equal its predecessor, so each has exactly one choice given the previous one.
• The last element must equal the first element to satisfy a_n ^ a_1 == 0. This fixes the last element. Thus, a naive count would be total * 1^{n-2} * 1 = total. However, this includes the constant sequences where all elements are identical, which are invalid. Let invalid_len be the number of constant sequences of length len that violate the non-constant rule. For length n, invalid_n = total (all identical). Therefore, valid sequences seem to be total - total = 0, which is incorrect because we overlooked constraints on the second-to-last element.

The correct reasoning accounts for the condition a_{n-1} == a_n because a_{n-1} ^ a_n == 0. But since a_n == a_1, this forces a_{n-1} == a_1. Consequently, for the first n-2 elements, we must have a_1 == a_2 == ... == a_{n-1}, which implies the sequence is constant, contradicting the non-constant requirement. Therefore, for n ≥ 3, no sequence satisfies both a_i == a_{i+1} for all i and a_n == a_1 without being constant. Wait, the original problem statement likely had a different interpretation.

Let's reinterpret: The condition x ^ y == 0 for all adjacent pairs is equivalent to x == y. Therefore, all elements in the sequenec must be equal. The only additional condition is that the sequence is not constant. This yields zero valid sequences for n≥2. However, the provided recurrence suggests a different problem: sequences where the XOR of all adjacent pairs equals zero, but perhaps the intended condition is that the XOR of consecutive pairs is zero, i.e., (a_i ^ a_{i+1}) == 0 for each i, which indeed forces equality. The provided formula f_n = 2^m * (2^m - 1)^{n-2} - f_{n-2} * (2^m - 1) hints at a constraint where the sequence cannot have two consecutive equal elements? Let's analyze the given recurrence.

Let P = 2^m. Define f_n as the number of sequences of length n with elements in [0, P-1] such that a_i ^ a_{i+1} == 0 for all i from 1 to n-1, and with the additionla constraint that a_1 ^ a_n == 0 (forming a cycle), but the sequence is not constant. This is a circular arrangement. Consider linear sequences satisfying a_i == a_{i+1} for i=1..n-1. They are all constant. To have a cycle where a_1 == a_n, the linear constraint forces all elements equal. So the only sequences are constants, which are excluded, giving zero. The recurrence does not match.

Given the provided matrix setup, the actual problem likely counts sequences where no two adjacent elements are equal, and the XOR condition is a_i ^ a_{i+1} != 0? The recurrence f_n = P * (P-1)^{n-2} - f_{n-2} * (P-1) aligns with counting sequences with no two consecutive equal elements, while also ensuring the first and last are not equal? This is a standard necklace / linear arrangement count.

We proceed with the given recurrence and matrix exponentiation. The state vector includes f_n, f_{n-1}, f_{n-2}, and (P-1)^{n-1}. The transition matrix is:

[ 0,  -(P-1),   0,   P ]
[ 1,   0,       0,   0 ]
[ 0,   1,       0,   0 ]
[ 0,   0,       0,  P-1 ]

with initial values for n=1,2,3 derived manually.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

struct ModNum { /* same as above */ };

struct SquareMatrix {
    int size;
    vector<vector<ModNum>> data;
    SquareMatrix(int sz = 0) : size(sz), data(sz, vector<ModNum>(sz, 0)) {}
    SquareMatrix(vector<vector<ModNum>> mat) : data(mat) { size = mat.size(); }
    SquareMatrix operator*(const SquareMatrix& other) const {
        SquareMatrix result(size);
        for (int i = 0; i < size; i++)
            for (int k = 0; k < size; k++)
                if (data[i][k].val)
                    for (int j = 0; j < size; j++)
                        result.data[i][j] = result.data[i][j] + data[i][k] * other.data[k][j];
        return result;
    }
    SquareMatrix pow(ll exponent) const {
        SquareMatrix base = *this, result(size);
        for (int i = 0; i < size; i++) result.data[i][i] = 1;
        while (exponent) {
            if (exponent & 1) result = result * base;
            base = base * base;
            exponent >>= 1;
        }
        return result;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    ModNum P = ModNum(2).pow(m);          // total choices per position
    ModNum P_minus_1 = P - 1;             // choices for a differing element

    vector<ModNum> init(4);
    init[1] = 0;                          // f1
    init[2] = 0;                          // f2
    init[3] = P * P_minus_1 - P_minus_1; // f3, derived from formula
    if (n == 1) { cout << 0 << '\n'; return; }
    if (n == 2) { cout << 0 << '\n'; return; }
    if (n == 3) { cout << init[3] << '\n'; return; }

    vector<vector<ModNum>> trans_mat(4, vector<ModNum>(4, 0));
    trans_mat[0][1] = ModNum(0) - P_minus_1;  // - (P-1)
    trans_mat[0][3] = P;
    trans_mat[1][0] = 1;
    trans_mat[2][1] = 1;
    trans_mat[3][3] = P_minus_1;

    vector<ModNum> state(4);
    state[0] = init[3];                     // f_{n-1} initially f3 for n=4
    state[1] = init[2];                     // f_{n-2} = f2
    state[2] = init[1];                     // f_{n-3} = f1
    state[3] = P_minus_1 * P_minus_1;       // (P-1)^{2}

    SquareMatrix trans(trans_mat);
    trans = trans.pow(n - 4);               // advance to length n
    ModNum result = 0;
    for (int row = 0; row < 4; row++)
        result = result + trans.data[0][row] * state[row];
    cout << result << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) solve();
    return 0;
}