69eloChess's blog

By 69eloChess, history, 3 months ago, In English

You are given an integer N and a prime P. Count the number, modulo P, of undirected connected graphs G of N vertices numbered 1 to N that satisfy the following conditions:

There are no self-loops in G. Note that multiple edges are allowed.

For all edges (u,v) in G, if we delete (u,v) from G, G remains connected. In other words, G is edge-biconnected.

For all edges (u,v) in G, if we delete (u,v) from G, G is no longer edge-biconnected. Two graphs are considered different if and only if there exists a pair of distinct vertices (u,v) such that the numbers of edges connecting u and v in the two graphs are different.

N<=50, P<=1e9

Input : Two integers N and P

Output: Print the answer.

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Hint:

Credits: Kubic

»
3 months ago, # |
  Vote: I like it +23 Vote: I do not like it

This ain't 1400, it's the hardest problem of the last AGC.

E — Biconnected Graph

»
3 months ago, # |
  Vote: I like it -17 Vote: I do not like it

This problem can be solved by using the concept of Graph Theory and the properties of edge-biconnected graphs. The idea is to count the number of ways to add edges to a tree of N-1 vertices (since we have N vertices and we need to choose one vertex as the root) without creating any self-loops and ensuring that the graph remains edge-biconnected.

Here is a Python code that solves this problem:

Code

This code calculates the number of ways to add edges to a tree of N-1 vertices without creating any self-loops and ensuring that the graph remains edge-biconnected. This is done by counting the number of ways to choose 2 edges from the remaining N-2 vertices to connect the tree with the remaining N-1 vertices.

The time complexity of this code is O(1) and the space complexity is O(1), making it efficient for solving this problem.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Too easy, do better

can you solve it attractors