Cerința

Se dă n un număr natural. Cifrele lui n se permută pentru a forma un număr natural, de aceeași lungime cu n, și care să fie palindrom. Aflați câte asemenea numere se pot obține.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran numărul de palindromuri care se pot obține prin permutarea cifrelor lui n.

Restricții și precizări

• 0 ≤ n ≤ 1038
• PCR este prescurtarea de la Permutări Cu Repetiţie

Exemplu

Intrare

1102022

Ieșire

4

Explicație

Permutând cifrele lui 1102022 se pot obține următoarele palindromuri de aceeași lungime cu 1102022: 1022201, 1202021, 2012102, 2102012.

#include <bits/stdc++.h>
using namespace std;

int C[101] , D[101];

unsigned long long prep(int n , int f[])
{
    unsigned long long c = 1;
    for(int i = 1 ; i <= n ; i++)
        c *= i;
    for(int i = 0 ; i <= 9 ; i++)
        for(int j = 2 ; j <= f[i] ; j++)
            c /= j;
    return c;
}
int main()
{
    int f[10] = {0};
    int n;
    string s;
    cin >> s;
    n = s.length();
    for(int i = 0 ; i < n ; i++)
        f[s[i] - 48]++;

    int fimp = 0;
    for(int i = 0 ; i <= 9 ; i++)
        if(f[i] % 2 == 1) fimp ++;
    if(fimp > 1) cout << 0;
    else
    {
        for(int i = 0 ; i <= 9 ; i++)
            f[i] /= 2;
        if(f[0] == 0)
            cout << prep(n / 2 , f);
        else
        {
            unsigned long long c = prep(n / 2 , f);
            f[0]--;
            unsigned long long c1 = prep(n / 2 - 1 , f);
            cout << c - c1;
        }
    }
}