SRM428-D2-1000 TheDictionary

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

const int OO = 1e9;
const double EPS = 1e-9;


class TheDictionary {
public:
    void decompose(ll x, map<ll,ll> &mp, bool p) {
        for(ll f = 2; f <= x; f++) {
            int o = f;
            for(ll i = 2; i*i <= o; i++) {
                while(!(o%i)) {
                    if(p)
                        mp[i]++;
                    else
                        mp[i]--;
                    o /= i;
                }
            }
            if(o != 1) {
                if(p)
                    mp[o]++;
                else
                    mp[o]--;
            }
        }
    }

    ll fast_exp(ll base, ll p) {
        if(!p)
            return 1;
        if(p&1)
            return base * fast_exp(base,p-1);
        ll ret = fast_exp(base,p/2);
        return ret * ret;
    }

    ll comb(ll n, ll m) {
        ll total = n+m;
        map<ll,ll> mp;
        decompose(total,mp,1);
        decompose(n,mp,0);
        decompose(m,mp,0);
        ll ret = 1;
        for(pair<ll,ll> p : mp) {
            //cout << "p.first is " << p.first << " p.second is " << p.second << "\n";
            ret *= fast_exp(p.first,p.second);
        }
        return ret;
    }

    string find(int n, int m, int k) {
        if(k == 0) {
            return string(n,'a') + string(m,'z');
        }
        if(m == 0) {
            return string(n,'a');
        }
        if(n == 0) {
            return string(m,'z');
        }
        ll _prev = 1;
        for(int i = 0; i <= n; i++) {
            ll curr = comb(i,m-1)+_prev-1;
            //cout << "prev is " << _prev << " curr is " << curr << "\n";
            if(k >= _prev && k <= curr) {
                return string(n-i,'a') + 'z' + find(i,m-1,k-_prev+1);
            }
            _prev = curr+1;
        }
        return "";
    }
};

int main()
{
    /*ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);*/
    TheDictionary d;
    ll limit = d.comb(3,3);
    for(int i = 1; i <= limit; i++) {
        cout << d.find(3,3,i) << "\n";
    }
    return 0;
}