Marşrutlaşdırma sxemləri#11241
Gəlin zirvədən ibarət bir şəbəkəni nəzərdən keçirək, burada zirvələr ilə işarələnmişdir. Hər bir zirvə ya göndərici, ya alıcı, ya da heç biri kimi təyin olunur. Göndəricilərin sayı alıcıların sayına bərabərdir (S \ge 1).
Şəbəkədəki iki zirvə arasındakı əlaqələr, hər biri i → j şəklində olan istiqamətli kənarların siyahısı ilə təsvir edilir ki, bu da zirvə -nin zirvə -yə məlumat ötürə biləcəyini göstərir. Maraqlıdır ki, bu kənarların hamısı i < j xüsusiyyətini təmin edir, i > j xüsusiyyətini təmin edən kənar istisna olmaqla. Dövr yoxdur (yəni i → i tipli kənarlar yoxdur).
Marşrutlaşdırma sxemi, göndəricilərdən alıcılara qədər olan istiqamətli yolların çoxluğundan ibarətdir ki, bu yollardan heç biri ümumi son nöqtəyə malik deyil. Yəni yollar müxtəlif göndəriciləri müxtəlif alıcılara birləşdirir. Göndərici -dən alıcı -ə qədər olan yol zirvələrin ardıcıllığı kimi təsvir edilə bilər
belə ki, v_i → v_{i+1} istiqamətli kənarları bütün 0 \le i < e üçün mövcuddur. Bir zirvə eyni yolda bir neçə dəfə görünə bilər.
Hər bir istiqamətli kənarın yalnız bir dəfə keçildiyi müxtəlif marşrutlaşdırma sxemlərinin sayını hesablayın. Cavab çox böyük ola biləcəyi üçün onu 10^9 + 7 modulu ilə çıxarın. Məhdudiyyətlərə cavab verən ən azı bir marşrutlaşdırma sxeminin mövcudluğu təmin edilir.
Hər bir giriş dəsti testdən ibarətdir. Bütün testlər üçün n^2 cəminin 2 \cdot 10^4-dən çox olmayacağı təmin edilir.
Birinci sətir testlərin sayını t~(1 \le t \le 20) ehtiva edir.
Hər bir testin birinci sətiri tam ədədləri n~(2 \le n \le 100) və k~(0 \le k \le 2) ehtiva edir. Qeyd edək ki, girişdə açıq şəkildə müəyyən edilmir.
Hər bir testin ikinci sətiri uzunluğu olan bir sətir ehtiva edir. Sətirin -ci simvolu -ci zirvənin göndərici olduğunu göstərirsə , alıcı olduğunu göstərirsə , heç biri olmadığını göstərirsə olur. və simvollarının sayı bərabərdir. Ən azı bir simvolu var.
Testin hər bir sətiri sıfır və birlərdən ibarət bit sətiri ehtiva edir. -ci sətirdəki -ci bit, zirvə -dən zirvə -yə istiqamətli kənarın mövcud olduğunu göstərirsə , əks halda olur. Döngələr olmadığı üçün əsas diaqonalda bütün sıfırlar var. Bundan əlavə, əsas diaqonalın altında dəqiq ədəd var.
Ardışık testlər oxunaqlılığı artırmaq üçün boş sətirlərlə ayrılmışdır.
Hər bir test üçün hər bir kənarın yalnız bir dəfə keçildiyi marşrutlaşdırma sxemlərinin sayını 10^9 + 7 modulu ilə çıxarın. Məhdudiyyətlərə cavab verən ən azı bir etibarlı marşrutlaşdırma sxeminin mövcudluğu təmin edilir.
Nümunə 1. Birinci test üçün kənarlar aşağıdakı kimidir:
Dörd marşrutlaşdırma sxemi mövcuddur:
İkinci test üçün kənarlar aşağıdakı kimidir:
Mümkün marşrutlaşdırma sxemlərindən biri:
Ümumi halda, göndəricilər \{1, 2, 3\} alıcıların \{5, 6, 7\} bəzi permutasiyasına marşrutlaşdırıla bilər və göndəricilər alıcıların bəzi permutasiyasına marşrutlaşdırıla bilər, bu da 6 \cdot 2 = 12 cavabını verir.
Nümunə 2. Birinci test üçün kənarlar aşağıdakı kimidir:
Üç marşrutlaşdırma sxemi mövcuddur:
İkinci test üçün kənarlar aşağıdakı kimidir:
Yalnız bir marşrutlaşdırma sxemi mövcuddur:
Nümunə 1
Nümunə 2
Nümunə 3