Anyanın Oyunu#11272

Anyanın Oyunu (Həll təhlili)

Məsələdə $n$ təpə ilə müxtəlif nömrələnmiş ağacların sayını tapmaq tələb olunur. Və ya eyni şeydir ki, $n$ təpəsi olan tam qrafda kök ağacların sayını tapmaq lazımdır.

Xatırladaq ki, qraf tamdır, əgər onun hər təpə cütü bir tərəflə birləşibsə.

Teorema. $n$ təpəli tam qrafdan olan kök ağaclar və uzunluğu $n - 2$ n - 2 olan Prüfer kodları arasında qarşılıqlı bir şəkildə təkcə uyğunluq mövcuddur.

Lemma. Longluğu $n - 2$ n - 2 olan fərgli Prüfer kodlarının sayı $n^{n - 2}$ n^{n - 2} bərabərdir.

Nəticədə, Anya'nın təsvir edə biləcəyi müxtəlif çəkilərin sayı (yəni $n$ təpəli nömrələnmiş ağacların sayı) $n^{n - 2}$ n^{n-2} bərabərdir.

Məsələn

$n = 4$ n = 4 üçün 16 müxtəlif ağac mövcuddur. Hər ağac altında ona uyğun gələn Prüfer kodu göstərilmişdir.

Alqoritmin tətbiqi

Testlərin sayını oxuyuruq $t es t s$ .

scanf("%d",&tests);
for (t = 1; t <= tests; t++)
{

Hər bir test üçün $n$ dəyərini oxuyuruq.

  scanf("%d",&n);

$n^{n - 2}$ n^{n - 2} dəyərini modulu $2000000011$ ilə hesablayırıq və çap edirik.

  res = 1;
  for (i = 0; i < n - 2; i++)
    res = (res * n) % 2000000011;
  printf("Case #%d: %lld\n",t,res);
}