Counting Bipartite Graphs | Practice Problems

Counting Bipartite Graphs

★★★★★

5

3 votes

Combinatorics, Easy, Graphs, Inclusion-Exclusion, Math

Details

Problem

You are given two sets of vertices such that the first set contains $n$ vertices labeled $1$ to $n$ and the second set contains $m$ vertices labeled $1$ to $m$ .

Add edges between these vertices such that no two vertices from the same set are adjacent and each vertex is incident on at least one edge. Find out the number of graphs that can be formed under the above constraints.

CONSTRAINTS:
$1 \leq n \leq m \leq 10^6$

INPUT:
A single line containing two integers $n$ and $m$ .

OUTPUT:
A single integer denoting the answer. Since the answer can be large, output it modulo $998244353$ .

Sample Input

2 2

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Denote a pair $(u,v)$ as an edge where u is a vertex from the first set and v from the second.

Then the edge sets for the 7 graphs are:

${(1, 1), (2, 2)}$
${(1, 2), (2, 1)}$
${(1, 1), (1, 2), (2, 2)}$
${(1, 1), (1, 2), (2, 1)}$
${(1, 1), (2, 1), (2, 2)}$
${(1, 2), (2, 1), (2, 2)}$
${(1, 1), (1, 2), (2, 1), (2, 2)}$

Contributers:

Niyaz Nigmatullin