ADAPANEL - Ada and Panels
Ada the Ladybug has proved successful in solving some hard problems, so a construction company has asked her to solve a problem for them. There are multiple cities in the country and each city owns exactly one panel-block. There are also unidirectional roads between some pairs of cities (note that circular self-roads and multi-roads with several traffic lines are allowed). A city can sell its panel-block to any city, to which they could transport the panel block, and from which they can bring back their reward for it (i.e. there must be a path from actual city to destination city and back). As long a city has K panel-blocks, it builds a prefab of height K which looks exactly same as each other prefab of height K.
The construction company notes all the heights down and puts them in an array. They are wondering how many distinct arrays are possible by moving the panel blocks between cities. However there is a catch. Consider a set of cities in which each city is reachable by every other city. Since we can easily shuffle the panel blocks between such a set of cities, we can create new permutations with the same set of heights. The construction company will NOT count any such cases. Hence they will only consider the distinct set of heights for such a set of cities.
You have proved successful in helping Ada with some hard problems, so she has asked you to help her. Your job is following - count the number of possible structures which could arise. Since this number might be pretty big, you have to output it modulo 109+7.
Input
The first line contains two integers 1 ≤ N, M ≤ 2*105, the number of cities an the number of unidireectional roads between them.
The next M lines contains two integers 0 ≤ a, b < N, the road from city a to city b
Output
Print a single line - the number of possible structures modulo 1000000007.Example Input
7 9 0 1 1 2 2 3 3 1 2 0 4 5 5 4 6 4 5 6
Example Output
15
Example Input 2
7 7 0 1 1 2 2 3 3 4 4 5 5 6 6 0
Example Output 2
15
Example Input 3
6 3 0 1 3 2 4 5
Example Output 3
1
Example Input 4
8 7 0 1 1 0 2 3 3 2 4 5 5 6 6 4
Example Output 4
12
hide comments
hf2002:
2024-09-06 01:29:20
This is the third time I read this shitty statement in different periods and I understand nothing. |
|
Rafail Loizou:
2023-08-03 03:42:44
I solved this problem 2 years ago. A guy that I help train stumbled upon it randomly and saw that I solve it (and probably is reading this comment now) and asked for me to give an explanation on how I solved it. I'm reading my code for an hour now and I can't seem to understand the wicked combinatorics formulas I used to get the AC. It was all intuitive back then but now without any comments around other than me swearing on debug loops I guess I will have to re-solve the problem from scratch. SMH... At least anybody reading this comment: Learn from MY mistake so you don't REPEAT them and write comments even for math formulas to show how you derived them and explain your thinking step-by-step. It's in-efficient and a pity not to have that type of information in the future.
|
|
nadstratosfer:
2021-01-07 00:01:16
Interesting problem comprising 2 difficult and otherwise unrelated concepts. Reasonable TL allows AC in PyPy. Once again good job, Morass. |
|
sanjitpd_777:
2020-09-15 10:27:31
Add some explanation. |
|
kanishk779:
2019-03-24 15:15:36
What is the meaning of the distinct array in this problem? |
Added by: | Morass |
Date: | 2017-07-31 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |