PALLIND - Bob And Palindromes - CodeChef

Question

Cześć,
Próbuję rozwiązać to zadanie: https://www.codechef.com/problems/PALLIND i nic mi do głowy nie przychodzi.
Rozumiem, że x = {1, 2, 3, ..., 25, 26}, a oczekiwana wartość w tym przypadku to będzie coś w stylu E[xi] = xi * P(xi), gdzie xi to i-ty element z x, a funkcja P określa prawdopodobieństwo dla otrzymania palindroma po dodaniu xi elementu. Więc tak na prawdę, główny problem to znaleźć jakie wartości przyjmuje P(xi), a potem zsumuje E[xi].

No ale utknąłem, bo:
Dla 1 operacji, moje prawdopodobieństwo to 26/26, bo 1 znak jest zawsze palindromem.
Dla 2 operacji, moje prawdopodobieństwo to 1/26, bo muszę wylosować ten sam znak co w 1 operacji.
Dla 3 operacji, moje prawdopodobieństwo to 0, bo jeśli mam 2 takie same znaki, to dodając 3 na pewno nie uzyskam palindroma. Tu pojawią się problem, bo jeśli w 2 operacji nie stworzył bym palindroma, to stworzył bym go w 3. Ale jeśli zliczam prawdopodobieństwa dla sukcesu, to nie mogę podążać tą ścieżką (bo niby co miałbym wpisać w 2? 0 byłoby nieprawdą, a 25/26 jest prawdopodobieństwem dla porażki), więc ignoruję tę możliwość.
Dla 4 operacji, jeśli zliczam nastawiam się na sukcesy, to obecny string wygląda w stylu "aab", więc muszę dodać b żeby dostać palindrom, czyli prawdopodobieństwo to 1/26.

Widzę więc, intuicyjnie, że dla nieparzystego xi funkcja P(xi) = 0, a dla reszty przyjmie 1/26. No ale kolejny problem, bo jeśli mam dane N, to skąd mam wiedzieć jakie xi używać? W sensie, że np. jeśli N = 2, to mam liczyć oczekiwaną wartość dla 21 i 22, czy może dla 0 i 1, a może dla 3 i 4 albo dla 10 i 11? Albo lepszy przykład, jeśli N > 26, to jakie xi używać?

Jak podejść do tego zadanka? Gdzie popełniam błąd?

Comments

Dla nieparzystych prawdopodobieństwo to nie będzie 0. Też nie rozumiem trochę rozumowania bo możemy przecież otrzymać palindrom np. aaa

Answer 1

Trzeba skorzystać z takiej własności, że E[X_1 + X_2] = E[X_1] + E[X_2].

Jeśli teraz przez X_j oznaczymy zmienną losową, która zwraca 1 gdy skonstruowane słowo długości j jest palindromem i 0 w przeciwnym wypadku to wystarczy obliczyć:

E[X_1 + X_2 + ... + X_n] gdzie n jest podane na wejściu

Pozostało zastanowić się jak liczyć E[X_j]

Comments

To nie musi być dokładnie szereg arytmetyczny/geometryczny. Może być zmodyfikowany

---

Aa, widzę. Po prostu wyciągnąć 2 przed nawias i wtedy mam geometryczny w tym nawiasie z q = 1/26. Wtedy mogę policzyć sumę ciągu bardzo szybko, a jeśli N-1 (ponieważ omijam 1 , pierwszy wyraz z oryginalnego ciągu) jest nieparzyste, to odejmuję od sumy 1/b. Ale znowu to samo :/ Działa dla przykładowych danych, przechodzi tylko pierwszy przypadek głównego testu. Pojęcia nie mam czemu, overflow nigdzie nie zauważyłem. https://pastebin.com/gezdYguT

---

na pewno nie możesz korzystać z double

---

funkcja inverse zawsze zwraca tę odwrotność % m. Moje a1 to oryginalnie 1/26, więc jeśli dobrze myślę, to pierwszy nawias można zredukować do inverse(a). Wydaje mi się, że problem jest tu, że liczę inverse z (1-q), co daje ujemny wynik. Chyba nie powinno tak wyglądać, ale jak na to zaradzić? Ogółem wydaje mi się, że całość wyglądać powinna tak:
 

	const long long q = inverse(26);
	long long gp_sum = (1 + (2 * (q * (((1 - pow_mod(q, n)) * (inverse(1 - q) + mod)) % mod)) % mod)) % mod;
	if (((n - 1) & 1) != 0)
		gp_sum -= inverse(b);

no ale jak zwykle nie działa. 

---

https://pastebin.com/6A7u77yv tak to powinno wyglądać