UVA 153 -Permalex ( Permutation, Math, Overflow handling )

UVA 153 -Permalex ( Permutation, Math, Overflow handling )

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     33
#define inf    1000000010
#define MD     100007LL
#define eps    1e-9
///===============================///

char s[MX+2];
int main() {
    int i,j,k,n,tc,cs=1;
    while(true) {
        scanf("%s",s+1);
        n=strlen(s+1);
        if( s[1]=='#' )break;
        ll MP[28]={0};
        for(i=1; i<=n; i++) MP[ s[i]-'a' ]++;
        ll sm=0;
        for(i=1; i<=n; i++) {
            int x=s[i]-'a';
            for(j=0; j<x; j++) {
                if( !MP[j] )continue;
                MP[j]--;
                ll pre[33]={0};
                for(k=0; k<26; k++) {
                    if(MP[k]<=1)continue;
                    ///Counting how many freq of individual
                    pre[ 2 ]++;
                    pre[ MP[k]+1 ]--;
                }
                for(k=1;k<=30;k++)pre[k]+=pre[k-1];
                ///Total => (n-i)!/inv frequen!
                ll tot=1LL;
                for(ll y=1;y<=(n-i);y++){
                    tot=(tot*y);
                    ///Reducing it if possible;
                    for(ll k=2;k<=30;k++){
                        while( tot%k==0 && pre[k] ){
                             tot/=k;
                             pre[k]--;
                        }
                    }
                }
                sm+=tot;
                MP[j]++;
            }
            MP[ x ]--; ///Fix char X on pos i;
        }
        sm++;
        printf("%10lld\n",sm);
    }
    return 0;
}