Problem Link:
Author: tseccodecell
DIFFICULTY:
Medium
PRE-REQUISITES:
Basic Combinatorics, Lucas Theorem
PROBLEM:
Find the number of graphs possible N vertices and M edges.
All vertices and edges must be used for a graph and at least one graph will be possible for every input.
QUICK EXPLANATION:
The answer for each input is given by :- {^{^nC_2}C_m} % 2713
this can be easily computed using lucas theorem, preprocess some values for faster computation
Explanation:
The number of different simple undirected graphs with n vertices and m edges is {^{^nC_2}C_m}.
Let us prove this:
No. of ways to choose any two vertices : {^nC_2} as it is undirected so arrangement dosen’t matter
This can be thought of as having {^nC_2} edges to choose from
Now, we have to choose ‘m’ edges from {^nC_2} possible edges, which is given by {^{^nC_2}C_m}
Alternative proof:
Let us consider the adjacency matrix of the graph
Total cells = n^2
As the graph is simple, there are no self loops, so we eliminate the diagonal cells.
So, now we’re left with n^2 - n cells
Since the graph is undirected, mat[i][j] = mat[j][i], so we’ll only have to choose from one half(bottom or top) as other half cell will be automatically filled
Therefore, cells to fill = (n^2 - n)/2
Since we have ‘m’ edges, we have to fill ‘m’ cells among these cells
So ways to fill it is ^{(n^2 - n)/2}C_m
Okay, so now we know that we have to find {^{^nC_2}C_m} % 2713,
but if we go about finding {^{^nC_2}C_m} directly and then do modulus, it will take too much time(time complexity will be huge) for the given constraints. see here for more information on such topics
If we analyze the modulus value, we come to know that it is a prime and a small one
So the best way to find our answer is to use Lucas Theorem(Link 1 , Link 2)
Basically you need to convert the numbers in base 2713 and then multiply the successive combinations
If we preprocess the combinations, time complexity for each test case would be: O(log_pn)
Pitfalls:
The assumption that {^{^nC_2}C_m} \bmod 2713 can be written as ^{(nC2 \bmod 2713)} C_{(m \bmod 2713)} \bmod 2713 is incorrect especially for large values
Some test cases with answers:
Input:
13
1000000000 11543263
1000000000 153126357391543263
37889434 334278564736253
99335555 417333344
1837 741
8242 2914
24191 19337
9219 3957
10 44
16347 5200
8385 8335
21132 7180
156600 1378774
Output:
0
0
471
0
2340
1838
874
2605
45
0
1808
0
1735
Time Complexity: O(p^2 + log_pn)
Space Complexity: O(p^2)