یک گراف سادهی همبند n n راسی به شما داده است. در ابتدا رنگ تمامی راسها به جز دو راس r…
- User
یک گراف سادهی همبند n n راسی به شما داده است. در ابتدا رنگ تمامی راسها به جز دو راس r r و b b، سفید است. راس r r قرمز رنگ است و یک مهرهی قرمز نیز روی آن وجود دارد. راس b b سیاه رنگ است و یک مهرهی سیاه روی آن وجود دارد.
در هر ثانیه به صورت تصادفی یکی از دو رنگ سیاه و قرمز انتخاب میشود و به ازای هر مهره از رنگ انتخاب شده، که برای مثال در راس v v قرار دارد، در تمامی راسهای همسایه راس v v در گراف یک مهرهی جدید از همان رنگ قرار داده میشود. اگر راسی که مهرهی جدید در آن قرار میگیرد سفید باشد، رنگ راس به رنگ آن مهره در خواهد آمد و در غیراینصورت رنگ راس تغییر نخواهد کرد.
راسهای گراف در انتهای این عملیات، یعنی زمانی که تمامی راسها رنگ شدهاند، چند رنگآمیزی متفاوت میتوانند داشته باشند؟ دو رنگ آمیزی متفاوت اند اگر رنگ یک راس در آن دو رنگآمیزی متفاوت باشد.
ورودی در خط اول ورودی چهار عدد طبیعی n n و m m و r r و b b، به ترتیب تعداد راسهای گراف، تعداد یالهای گراف، شمارهی راس r r و شمارهی راس b b، آمده است. در هر یک از m m خط بعدی دو عدد طبیعی v i v i و u i u i آمدهاست که نشاندهندهی وجود یک یال بین دو راس v i v i و u i u i در گراف است. گراف داده شده ساده و همبند است. 2 ≤ n ≤ 100
000 2≤n≤100 000 1 ≤ m ≤ m i n ( ( n 2 ) , 200
000 ) 1≤m≤min(( 2 n ),200 000) 1 ≤ r , b ≤ n 1≤r,b≤n r ≠ b r =b 1 ≤ v i , u i ≤ n 1≤v i ,u i ≤n
خروجی در تنها خط خروجی باقیماندهی تعداد رنگآمیزیهای متفاوت گراف در انتهای عملیات بر 1 0 9 + 7 10 9 +7 را چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۷ n ≤ 20 n≤20 ۲ ۲۶ n ≤ 1
000 n≤1 000 ۳ ۵۷ بدون محدودیت اضافی مثال ورودی نمونه ۱ 4 3 2 3 1 2 2 3 3 4 Plain text خروجی نمونه ۱ 3 Plain text ورودی نمونه ۲ 6 6 1 6 1 2 2 3 2 4 3 5 4 5 5 6 Plain text خروجی نمونه ۲ 4 Plain text ورودی نمونه ۳ 8 9 1 2 1 3 3 2 1 4 4 5 5 2 1 6 6 7 7 8 8 2 Plain text خروجی نمونه ۳ 8
- Assistant
To solve this problem, we need to determine the number of different colorings possible in a connected graph after propagating colors from two designated nodes
r(red) andb(black). The process involves selecting colors to propagate at each step and assigning colors to the nodes based on the spread.Step-by-Step Reasoning:
-
Initial Setup:
- Nodes
randbare initially colored red and black, respectively. - All other nodes are white.
- Nodes
-
Propagation Rules:
- At each step, either red or black is chosen to propagate.
- When a color is chosen:
- All nodes with that color spread tokens to their adjacent nodes.
- If an adjacent node is white, it adopts the chosen color.
- If an adjacent node is already colored, its color remains unchanged.
-
Color Assignments:
- The key observation is that the final color of a node is determined by which color reaches it first.
- The color assignments can be influenced by the distances from
randbto each node. - Specifically, for each node, we calculate the shortest distance from
r(d_r[v]) and fromb(d_b[v]).
-
Determining Flexibility:
- Forced Colors: If
d_r[v] < d_b[v], the node must be red. Similarly, ifd_r[v] > d_b[v], the node must be black. - Flexible Colors: If
d_r[v] == d_b[v], the node can be either red or black, giving us flexibility in the final coloring.
- Forced Colors: If
-
Counting Colorings:
- The number of flexible nodes (where
d_r[v] == d_b[v]) determines the number of possible colorings. - Each flexible node can be either red or black independently, leading to
2^kpossible colorings, wherekis the number of such flexible nodes.
- The number of flexible nodes (where
-
Final Calculation:
- Perform BFS from both
randbto determine the shortest distances. - Count the number of nodes where
d_r[v] == d_b[v]. - The total number of colorings is
2^kmodulo10^9 + 7, wherekis as determined.
- Perform BFS from both
Conclusion:
After calculating the number of nodes where the distances from
randbare equal, we can directly compute the number of valid colorings by raising 2 to the power of this count. This approach efficiently handles large graphs within the given constraints.Answer
Cannot answer the question as it requires the output for the given input.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.