pipipipipipipip

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

static unsigned int g_seed;

// Used to seed the generator.
inline void fast_srand(int seed) {
    g_seed = seed;
}

// Compute a pseudorandom integer.
// Output value in range [0, 32767]
inline int fast_rand(void) {
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>16)&0x7FFF;
}

int main() {
    fast_srand(0);

    for( int numHashes = 1 << 15; numHashes <= (1 << 20); numHashes += 1 << 15 ) {
        constexpr int hashSize = 32;
        int blockSize = 20;

        int numBuckets = (1 << blockSize);
        bitset<hashSize> hashMask = bitset<hashSize>(((1 << blockSize) - 1));

        vector<bitset<hashSize>> hashes(numHashes);
        vector<int> buckets(numBuckets, 0);

        for (size_t i = 0; i < numHashes; i++) {
            hashes.at(i) = bitset<hashSize>((fast_rand() << 16) + fast_rand());
        }
        for( int i = 0; i < numHashes; i++ ) {
            int bucket = (hashes[i] & hashMask).to_ulong();
            buckets.at(bucket)++;
        }
        vector<int> cnt(1000);
        for (size_t i = 0; i < cnt.size(); i++) {
            cnt.at(i) = 0;
        }
        for (size_t i = 0; i < numBuckets; i++) {
            cnt.at(buckets.at(i))++;
        }
        int nextNumHashes = 0;
        for (size_t i = 0; i < cnt.size(); i++) {
            nextNumHashes += cnt.at(i) * i * (i-1) / 2;
        }
        cout << "(" << numHashes << ", " << nextNumHashes << ")" << endl;
    }
}