Feladat

Adjuk meg, hogy a C_n gráfban, vagyis az n hosszú körben hány párosítás található. A csúcsokat megkülönböztetjük. Párosítás alatt az élek egy csúcsdiszjunkt részhalmazát értjük, azaz néhány élt úgy, hogy semelyik kettőnek nincs közös végpontja.

Például C₄-ben 7 párosítás található: ha a csúcsokat a kör mentén sorra 1,2,3,4-gyel jelöljük, akkor ezek az üres párosítás, valamint 12, 23, 34, 41, 12-34 és 23-41.

Ez a szám persze nagyon nagy lehet, és az eredeti feladatban el is várták, hogy nagyszám-aritmetikát írjon az ember, de nekem ez most nem fontos, úgyhogy elég az eredményt modulo 1 000 000 000 kiírni.

Megjegyzés: Mivel nem pont ez volt kitűzve, ezt így ne küldjétek be az UVA-ra. Amúgy is úgy tűnik, hogy rosszul teszteli ezt a versenyt, mert még egy megoldást sem fogadott el róla.

input

Az n egész szám 3<n<10 000 000

output

Egy egész szám, a párosítások száma mod 1 000 000 000.

NWERC 2012

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.