anti hash test generator

#include <algorithm>
#include <iostream>
#include <string.h>
#include <sstream>
#include <cassert>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;


/*
 This is an anti hash test generator
 It can find collisions for different polynomial hashes
*/


const int N = 22; //the length of strings generated to make collision



int rnd[1 << 22];

class MyRandom //specific random numbers generator
{
    int count;
public:
    MyRandom()
    {
        for (int i = 0; i < (1 << N); ++i)
            rnd[i] = i;
        random_shuffle(rnd, rnd + (1 << N));
        count = 0;
    }

    void reset()
    {
        count = 0;
    }

    int random()
    {
        count %= (1 << N);
        return rnd[count++];
    }
};

MyRandom random;



string makeString(int mask) //converts bitmask into an 'a'-'b' string
{
    string result;
    for (int i = 0; i < N; ++i)
    {
        if (mask & (1 << i))
            result += 'b';
        else
            result += 'a';
    }
    return result;
}


long long getHash(int mask, long long base, long long mod, long long valueA, long long valueB) //this function calculates hash value
{
    long long currentPow = 1;
    long long HASH = 0;
    for (int i = 0; i < N; ++i)
    {
        if (mask & (1 << i))
            HASH += currentPow * valueB;
        else
            HASH += currentPow * valueA;
        HASH %= mod;
        currentPow *= base;
        currentPow %= mod;
    }
    return HASH;
}

long long getHash(string s, long long base, long long mod, long long valueA, long long valueB)
{
    long long currentPow = 1;
    long long HASH = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == 'b')
            HASH += currentPow * valueB;
        else
            HASH += currentPow * valueA;
        HASH %= mod;
        currentPow *= base;
        currentPow %= mod;
    }
    return HASH;
}

/*
 Hash table
*/

const int CELLS = 1000 * 1000 + 13;
int top[CELLS];
const int MAX_SZ = (1 << N);
long long key[MAX_SZ];
int go[MAX_SZ];
int value[MAX_SZ];

long long ABS(long long a)
{
    return (a > 0 ? a : -a);
}

class HashTable
{
    int sz;
public:
    HashTable()
    {
        sz = 0;
        for (int i = 0; i < CELLS; ++i)
            top[i] = -1;
    }

    void clear()
    {
        sz = 0;
        for (int i = 0; i < CELLS; ++i)
            top[i] = -1;
    }

    void addKey(long long _key, int _value)
    {
        int cell = ABS(_key) % CELLS;
        int id = sz++;
        key[id] = _key;
        value[id] = _value;
        go[id] = top[cell];
        top[cell] = id;
    }

    int getValue(long long _key) //returns -1 if there's no such key
    {
        int cell = ABS(_key) % CELLS;
        int ptr = top[cell];
        while (ptr >= 0)
        {
            if (key[ptr] == _key)
                return value[ptr];
            ptr = go[ptr];
        }
        return -1;
    }
};

HashTable was;




pair<string, string> buildMod(long long base, long long mod, long long valueA, long long valueB)
{
    random.reset();
    was.clear();

    for (;;)
    {
        int mask = random.random();
        long long HASH = getHash(mask, base, mod, valueA, valueB);
        int prevMask = was.getValue(HASH);
        if (prevMask == -1)
        {
            was.addKey(HASH, mask);
        }
        else
        {
            string a = makeString(mask);
            string b = makeString(prevMask);
            return pair<string, string> (a, b);
        }
    }
}



const int LEN = (1 << 12);

pair<string, string> buildPow2()
{
    string current;
    for (int i = 0; i < LEN; ++i)
    {
        if (__builtin_popcount(i) % 2 == 0)
            current += 'a';
        else
            current += 'b';
    }
    string a = current.substr(0, LEN / 2);
    string b = current.substr(LEN / 2, LEN / 2);
    return pair<string, string> (a, b);
}


/*
 This structure describes one hash.
 It contians it's base and modulo.
 If the module is power of 2,
 then there should be zero instead.
 rev should be 0 if hash value is calculated from left to right
 and 1 otherwise
*/

struct HashPair
{
    long long base;
    long long mod;
    int rev;

    void read()
    {
        cin >> base >> mod;
        cin >> rev;
    }
};

bool cmp(HashPair a, HashPair b)
{
    return a.mod > b.mod;
}

pair<string, string> buildTest(vector<HashPair> h)
{
    if (h.size() == 0)
    {
        string a = "a";
        string b = "b";
        return pair<string, string> (a, b);
    }

    HashPair last = h.back();
    h.pop_back();
    pair<string, string> prev = buildTest(h);

    if (last.mod == 0)
    {
        pair<string, string> result;
        pair<string, string> temp = buildPow2();
        for (int i = 0; i < temp.first.length(); ++i)
        {
            if (temp.first[i] == 'a')
                result.first += prev.first;
            else
                result.first += prev.second;
            if (temp.second[i] == 'a')
                result.second += prev.first;
            else
                result.second += prev.second;
        }

        return result;
    }

    long long valueA = getHash(prev.first, last.base, last.mod, 1, 2);
    long long valueB = getHash(prev.second, last.base, last.mod, 1, 2);
    long long initBase = last.base;
    for (int i = 1; i < prev.first.length(); ++i)
        last.base *= initBase, last.base %= last.mod;

    pair<string, string> temp = buildMod(last.base, last.mod, valueA, valueB);
    if (last.rev)
    {
        reverse(temp.first.begin(), temp.first.end());
        reverse(temp.second.begin(), temp.second.end());
    }

    pair<string, string> result;
    for (int i = 0; i < temp.first.length(); ++i)
    {
        if (temp.first[i] == 'a')
            result.first += prev.first;
        else
            result.first += prev.second;
        if (temp.second[i] == 'a')
            result.second += prev.first;
        else
            result.second += prev.second;
    }

    return result;
}


void solve()
{
    int n;
    cin >> n;

    vector<HashPair> h(n); //vector contains all hashes
    for (int i = 0; i < n; ++i)
        h[i].read();

    sort(h.begin(), h.end(), cmp);
    while (h.size() >= 2 && h[(int)h.size() - 1].mod == 0 && h[(int)h.size() - 2].mod == 0)
        h.pop_back();

    pair<string, string> result = buildTest(h);
    assert(result.first != result.second);

    /*
     Be careful!
     If there're many hashes then the result might be very long!
    */

    cerr << "The length is: " << result.first.length() << endl;
    cout << result.first << endl;
    cout << result.second << endl;
}


int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}