Prva i druga polovina broja se mogu birati nezavisno. Ako postoji \(b_k\) načina da se odabere polovina broja tako da je zbir cifara u toj polovini jednak \(k\), onda postoji \(b_k^2\) načina da se odabere ceo broj tako da je zbir obe polovine međusobno jednak i jednak \(k\). Konačno rešenje se onda dobija sabiranjem ovih vrednosti za sve moguće zbirove \(k\) (a to su zbirovi od \(0\) do \(9n\)).
Razmotrimo polinom \(P(x) = 1 + x + x^2 + \ldots + x^9\). Možemo smatrati da svaki njegov koeficijent (a svaki je jednak 1) daje broj načina za koje jednocifreni broj ima zbir cifara redom 0, 1, pa do 9. Razmotrimo polinom
\[\begin{eqnarray*} P(x)^2 &=& (1 + x + x^2 + \ldots + x^9)(1 + x + x^2 + \ldots + x^9) \\ &=& 1 + 2x + 3x^2 + x^3 + \ldots + 9x^8 + 10x^9 + 9x^{10} + \ldots 2x^{17} +1x^{18}. \end{eqnarray*}\]
Koeficijent uz \(x^k\) sada daje broj načina da se broj \(k\) dobije kao zbir cifara nekog dvocifrenog broja. Na sličan način koeficijent uz \(x^k\), polinoma \(P(x)^m\) daje broj načina da se broj \(k\) dobije kao zbir cifara nekog \(m\)-tocifrenog broja.
Zaista, polinom \(P(x)^m\) dobija se sabiranjem proizvoda svih mogućih \(m\)-torki monoma iz \(P(x)\). Postoji bijekcija između \(m\)-tocifrenih brojeva i tih \(m\)-torki monoma iz \(P(x)\), takva da se svakoj cifri \(c\) dodeljuje monom \(x^c\). Proizvod monoma takve \(m\)-torke je monom \(x^k\), gde je \(k\) zbir cifara \(m\)-tocifrenog broja koji odgovara toj \(m\)-torki. Zato je broj \(m\)-tocifrenih brojeva čiji je zbir cifara \(k\) (broj \(b_{mk}\)) jednak broju \(m\)-torki monoma čiji je proizvod \(x^k\). Zbir svih tih monoma je \(b_{mk}x^k\), tako da se broj \(b_{mk}\) zaista može odrediti kao koeficijent uz \(x^k\) polinoma \(P(x)^m\).
Za učitani paran broj \(n\) možemo odrediti koeficijente polinoma \(P(x)^{\frac{n}{2}}\) i zatim rezultat možemo dobiti kao zbir kvadrata svih dobijenih koeficijenata. Stepen se može odrediti kombinacijom brzog stepenovanja (svako množenje polinoma se može vršiti pomoću brze Furijeove transformacije). Takođe, moguće je samo pronaći brzu Furijeovu transformaciju polinoma \(P\), zatim vrednost u svakoj tački zasebno stepenovati (brzim stepenovanjem), pa rezultat rekonstruisati inverznom Furijeovom transformacijom.
Primećujemo da smo prebrojavanje kombinatornih objekata ovaj put sveli na operacije nad polinomima (drugi uobičajeni način prebrojavanja je zasnovan na dinamičkom progamiranju). Polinomi ili redovi čiji koeficijenti daju broj kombinatornih objekata nazivaju se funkcije generatrise i predstavljaju veoma značajnu tehniku u kombinatorici.
Svako množenje polinoma primenom FFT je složenosti \(O(n\log{n})\). Ako se izvodi brzo stepenovanje na stepen \(n/2\), vrši se \(O(\log{n})\) množenja polinoma, pa je ukupna složenost \(O(n\log^2{n})\). Ako bi se izvršila samo brza Furijeova transformacija polinoma \(P(x)\), zatim stepenovale njegove vrednosti u tačkama, pa rezultat dobio inverznom brzom Furijeovom transformacijom, složenost bi bila \(O(n \log{n})\).
// brzim stepenovanjem odredjuje se stepen polinoma P^k
ComplexVector stepen(const ComplexVector& a, int k) {
if (k == 0)
// Polinom P(x) = 1 predstavljen vektorom date duzine
return one(a.size());
if (k % 2 == 0)
return stepen(proizvod(a, a), k/2);
else
return proizvod(a, stepen(a, k-1));
}
// za svaki broj iz [0, maxZbir] odredjujemo broj nacina da se taj
// broj predstavi kao zbir brojCifara cifara (pri cemu se u obzir
// uzima i redosled cifara)
vector<long long> brojParticija(int brojCifara, int maksZbir) {
// najmanji stepen dvojke veci ili jednak od maksZbir+1
int n = pow2(maksZbir + 1);
// polinom P(x) = 1 + x + ... + x^9 sa vektorom koeficijenata duzine n
ComplexVector P(n, 0);
for (int i = 0; i < 10; i++)
P[i] = 1;
// stepen P(x)^brojCifara
ComplexVector Pbc = power(P, brojCifara);
// konvertujemo kompleksne brojeve (koeficijente polinoma) u cele
vector<long long> rezultat(n);
for (int i = 0; i < n; i++)
rezultat[i] = round(Pn2[i].real());
return rezultat;
}
// izracunava broj 2n-tocifrenih brojeva kod kojih je zbir prvih n i
// zbir drugih n cifara jednak
long long brojBrojeva(int n) {
// za svaki broj od 0 do 9*n nas zanima koliko postoji razlicitih
// n-tocifrenih brojeva ciji je zbir cifara taj broj
vector<long long> bp = brojParticija(n, 9*n);
// ukupan broj brojeva cija leva i desna polovina imaju isti broj cifara
long long ukupnoBrojeva = 0;
// za svaki moguci zbir cifara polovine broja
for (int zbirCifara = 0; zbirCifara <= 9*n; zbirCifara++) {
// postoji bp[zbirCifara] nacina da napravimo levu polovinu i
// bp[zbirCifara] nacina da napravimo desnu polovinu broja
// tj. bp[zbirCifara]*bp[zbirCifara] nacina da odaberemo broj kome
// i leva i desna polovina imaju zbir cifara zbirCifara
ukupnoBrojeva += bp[zbirCifara] * bp[zbirCifara];
}
return ukupnoBrojeva;
}#include <iostream>
#include <vector>
#include <complex>
using namespace std;
typedef complex<double> Complex;
typedef vector<Complex> ComplexVector;
// brza Furijeova transformacija vektora a duzine n=2^k
// bool parametar inverse odredjuje da li je direktna ili inverzna
ComplexVector fft(const ComplexVector& a, bool inverse) {
// broj koeficijenata polinoma
int n = a.size();
// ako je stepen polinoma 0, vrednost u svakoj tacki jednaka
// je jedinom koeficijentu
if (n == 1)
return ComplexVector(1, a[0]);
// izdvajamo koeficijente na parnim i na neparnim pozicijama
ComplexVector Peven(n / 2), Podd(n / 2);
for (int i = 0; i < n / 2; i++) {
Peven[i] = a[2 * i];
Podd[i] = a[2 * i + 1];
}
// rekurzivno izracunavamo Furijeove transformacije tih polinoma
ComplexVector fftEven = fft(Peven, inverse),
fftOdd = fft(Podd, inverse);
// objedinjujemo rezultat
ComplexVector result(n);
for (int k = 0; k < n / 2; k++) {
// odredjujemo primitivni n-ti koren iz jedinice
double coeff = inverse ? -1.0 : 1.0;
Complex w = exp((coeff * 2 * k * M_PI / n) * 1i);
// racunamo vrednost polinoma u toj tacki
result[k] = fftEven[k] + w * fftOdd[k];
result[k + n/2] = fftEven[k] - w * fftOdd[k];
}
// vracamo konacan rezultat
return result;
}
// funkcija vrsi direktnu Furijeovu transformaciju polinoma ciji su
// koeficijenti odredjeni nizom a duzine 2^k
ComplexVector fft(const ComplexVector& a) {
return fft(a, false);
}
// funkcija vrsi inverznu Furijeovu transformaciju polinoma ciji su
// koeficijenti odredjeni nizom a duzine 2^k
ComplexVector ifft(const ComplexVector& a) {
ComplexVector rez = fft(a, true);
// nakon izracunavanja vrednosti, potrebno je jos podeliti
// sve koeficijente duzinom vektora
int n = a.size();
for (int k = 0; k < n; k++)
rez[k] /= n;
return rez;
}
// proizvod polinoma
ComplexVector proizvod(const ComplexVector& a, const ComplexVector& b) {
int n = a.size();
ComplexVector fa = fft(a), fb = fft(b);
ComplexVector fc(n);
for (int i = 0; i < n; i++)
fc[i] = fa[i] * fb[i];
return ifft(fc);
}
ComplexVector one(int n) {
ComplexVector result(n, 0);
result[0] = 1;
return result;
}
// najmanji stepen dvojke koji je veći ili jednak x
int pow2(int n) {
int p = 1;
while (p < n)
p *= 2;
return p;
}
// brzim stepenovanjem odredjuje se stepen polinoma P^k
ComplexVector stepen(const ComplexVector& a, int k) {
if (k == 0)
// Polinom P(x) = 1 predstavljen vektorom date duzine
return one(a.size());
if (k % 2 == 0)
return stepen(proizvod(a, a), k/2);
else
return proizvod(a, stepen(a, k-1));
}
// za svaki broj iz [0, maxZbir] odredjujemo broj nacina da se taj
// broj predstavi kao zbir brojCifara cifara (pri cemu se u obzir
// uzima i redosled cifara)
vector<long long> brojParticija(int brojCifara, int maksZbir) {
// najmanji stepen dvojke veci ili jednak od maksZbir+1
int n = pow2(maksZbir + 1);
// polinom P(x) = 1 + x + ... + x^9 sa vektorom koeficijenata duzine n
ComplexVector P(n, 0);
for (int i = 0; i < 10; i++)
P[i] = 1;
// stepen P(x)^brojCifara
ComplexVector Pbc = power(P, brojCifara);
// konvertujemo kompleksne brojeve (koeficijente polinoma) u cele
vector<long long> rezultat(n);
for (int i = 0; i < n; i++)
rezultat[i] = round(Pn2[i].real());
return rezultat;
}
// izracunava broj 2n-tocifrenih brojeva kod kojih je zbir prvih n i
// zbir drugih n cifara jednak
long long brojBrojeva(int n) {
// za svaki broj od 0 do 9*n nas zanima koliko postoji razlicitih
// n-tocifrenih brojeva ciji je zbir cifara taj broj
vector<long long> bp = brojParticija(n, 9*n);
// ukupan broj brojeva cija leva i desna polovina imaju isti broj cifara
long long ukupnoBrojeva = 0;
// za svaki moguci zbir cifara polovine broja
for (int zbirCifara = 0; zbirCifara <= 9*n; zbirCifara++) {
// postoji bp[zbirCifara] nacina da napravimo levu polovinu i
// bp[zbirCifara] nacina da napravimo desnu polovinu broja
// tj. bp[zbirCifara]*bp[zbirCifara] nacina da odaberemo broj kome
// i leva i desna polovina imaju zbir cifara zbirCifara
ukupnoBrojeva += bp[zbirCifara] * bp[zbirCifara];
}
return ukupnoBrojeva;
}
int main() {
int n;
cin >> n;
cout << brojBrojeva(n) << endl;
return 0;
}