P4221 [WC2018] State Partition

**Abusing the judge for this problem will result in a ban!**

Xiao S currently has $n$ cities. The population of the $i$-th city is $w_i$, and there may be bidirectional roads between cities. Now Xiao S will partition these $n$ cities into several states. Each state contains at least one city, and each city belongs to exactly one state. Suppose Xiao S partitions the cities into $k$ states. Let $V_i$ be the set of all cities contained in the $i$-th state. A road is defined to be an internal road of a state if and only if both of its endpoint cities are within that state. A state is called illegal if and only if there exists a path within this state that starts and ends at the same city, does not pass through any city outside this state, traverses every internal road of this state exactly once, and visits every city of this state at least once (the path length may be $0$). Define the satisfaction of the $i$-th state as the $p$-th power of the proportion of the $i$-th state's population in the total population of the first $i$ states, that is: $$\left(\dfrac{\sum _ {x \in V _ i} w _ x}{\sum _ {j = 1} ^ i \sum _ {x \in V _ j} w _ x}\right) ^ p$$ Define the satisfaction of a partition as the product of the satisfactions of all states. Compute the sum of the satisfactions of all legal partitions. Take the answer modulo $998244353$. Two partitions $\{V_1, V _ 2, \cdots, V_k\}$ and $\{C_1, C _ 2, \cdots, C_s\}$ are different if and only if $k \neq s$, or there exists some $1 \leq i \leq k$ such that $V_i \neq C_i$.

The first line contains three integers $n, m, p$, denoting the number of cities, the number of roads between cities, and the constant $p$ in the statement. The next $m$ lines each contain two positive integers $u, v$, describing an undirected road. There are no multiple edges and no self-loops. Line $m+2$ contains $n$ positive integers, where the $i$-th integer is $w_i$.

Output a single integer, which is the value of the answer modulo $998244353$. That is, let the answer in lowest terms be $a/b$, where $a$ and $b$ are coprime. Output an integer $x$ such that $b x \equiv a \pmod{ 998244353}$ and $0 \leq x < 998244353$. It can be proven that such an integer $x$ is unique.

$[ \text{Hint} ]$ $x^{p-1} \equiv 1 \pmod p$, where $p$ is a prime and $x \in [1, p)$. Constraints (guaranteed for all testdata): $0 \leq n \leq 21$, $0 \leq m \leq \dfrac{n \times (n-1)}{2}$, $0 \leq p \leq 2$, $1 \leq w_i \leq 100$. Translated by ChatGPT 5