یک گراف سادهی همبند 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
برای حل این مسئله، باید تعداد رنگآمیزیهای متفاوت نهایی گراف را که بر اساس فرآیند پراکندگی مهرههای قرمز و سیاه ایجاد میشود، محاسبه کنیم. فرآیند به این صورت است که در هر گام تصادفی یکی از دو رنگ قرمز یا سیاه انتخاب شده و مهرههای آن رنگ در تمامی رئوس همسایه گسترش مییابند. هر راس به محض دریافت اولین مهره از یک رنگ، رنگ آن تعیین میشود و دیگر تغییر نخواهد کرد.
گامهای حل مسئله:
-
محاسبه فاصلهها:
- فاصله هر راس از راس
r(فاصله قرمز) و راسb(فاصله سیاه) را با استفاده از الگوریتم BFS محاسبه میکنیم.
- فاصله هر راس از راس
-
تعیین انتخابهای آزاد:
- برای هر راس، اگر فاصله آن از
rبرابر با فاصله آن ازbباشد، این راس میتواند به دو صورت قرمز یا سیاه رنگ شود. تعداد این رئوس را به عنوانkتعیین میکنیم. - اگر فاصله از
rکمتر از فاصله ازbباشد، این راس باید قرمز باشد و اگر فاصله ازbکمتر بود، باید سیاه باشد.
- برای هر راس، اگر فاصله آن از
-
محاسبه تعداد رنگآمیزیهای مختلف:
- تعداد رنگآمیزیهای متفاوت برابر است با (2^k) که در آن
kتعداد رئوس با فاصلههای مساوی ازrوbاست. - در نهایت، مقدار نهایی را بر (10^9 + 7) باقیمانده میکنیم تا خروجی نهایی به دست آید.
- تعداد رنگآمیزیهای متفاوت برابر است با (2^k) که در آن
با این تحلیل، کد زیر پیادهسازی شده است:
import sys import sys import sys from collections import deque MOD = 10**9 +7 def main(): import sys sys.setrecursionlimit(1 << 25) n, m, r, b = map(int, sys.stdin.readline().split()) adj = [[] for _ in range(n+1)] for _ in range(m): u,v = map(int, sys.stdin.readline().split()) adj[u].append(v) adj[v].append(u) def bfs(start): dist = [ -1 ] * (n+1) q = deque() q.append(start) dist[start]=0 while q: u = q.popleft() for v in adj[u]: if dist[v]==-1: dist[v]=dist[u]+1 q.append(v) return dist dr = bfs(r) db = bfs(b) k=0 for v in range(1,n+1): if v == r or v == b: continue if dr[v]==db[v] and dr[v]!= -1: k+=1 ans = pow(2,k, MOD) print(ans) if __name__ == "__main__": main()توضیح نهایی: این کد ابتدا فاصله هر راس از رئوس
rوbرا محاسبه میکند. سپس تعداد رئوس با فاصلههای مساوی ازrوbرا شمارش کرده و نهایتاً تعداد رنگآمیزیهای ممکن را به صورت (2^k) محاسبه میکند. نتیجه نهایی بر (10^9 + 7) باقیمانده و چاپ میشود. -
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.