SRM 684 Div1 Medium

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int const MOD = 1000000007;

class DivFree
{
public:
    int dfcount (int n, int k)
    {
        map <vector <int>, int> v;
        int types = 0;
        int type [k + 1];
        int c [k + 1];
        memset (c, 0, sizeof (c));
        for (int j = 1; j <= k; j++)
        {
            vector <int> sig;
            int a = j;
            for (int e = 2; e * e <= a; e++)
            {
                if (a % e == 0)
                {
                    int num = 0;
                    do
                    {
                        num++;
                        a /= e;
                    }
                    while (a % e == 0);
                    sig.push_back (num);
                }
            }
            if (a > 1)
            {
                sig.push_back (1);
            }

            sort (sig.begin (), sig.end ());
            if (v.find (sig) == v.end ())
            {
                v[sig] = types;
                types++;
            }
            type[j] = v[sig];
            c[type[j]]++;
        }

        map <int, int> g [types];
        bool w [types];
        memset (w, 0, sizeof (w));
        for (int j = 1; j <= k; j++)
        {
            int jt = type[j];
            if (w[jt])
            {
                continue;
            }
            w[jt] = true;
            for (int p = 1; p < j; p++)
            {
                if (j % p == 0)
                {
                    g[jt][type[p]]++;
                }
            }
        }

        pair <int, int> h [types] [types];
        int hLen [types];
        memset (hLen, 0, sizeof (hLen));
        for (int jt = 0; jt < types; jt++)
        {
            for (auto pc : g[jt])
            {
                h[jt][hLen[jt]] = pc;
                hLen[jt]++;
            }
        }

        int64_t f [2] [k + 1];
        int b = 0;
        memset (f[b], 0, sizeof (f[b]));
        for (int jt = 0; jt < types; jt++)
        {
            f[b][jt] = 1;
        }

        for (int i = 1; i < n; i++)
        {
            b ^= 1;
            memset (f[b], 0, sizeof (f[b]));
            int64_t sum = 0;
            for (int jt = 0; jt < types; jt++)
            {
                sum += f[!b][jt] * c[jt];
            }
            sum %= MOD;

            for (int jt = 0; jt < types; jt++)
            {
                f[b][jt] = sum;
            }

            for (int jt = 0; jt < types; jt++)
            {
                for (int r = 0; r < hLen[jt]; r++)
                {
                    int pt = h[jt][r].first;
                    int num = h[jt][r].second;
                    f[b][jt] -= f[!b][pt] * num;
                }
            }

            for (int jt = 0; jt < types; jt++)
            {
                f[b][jt] %= MOD;
                if (f[b][jt] < 0)
                {
                    f[b][jt] += MOD;
                }
            }
        }

        int res = 0;
        for (int jt = 0; jt < types; jt++)
        {
            res = (res + f[b][jt] * 1LL * c[jt]) % MOD;
        }
        return res;
    }
};

<%:testing-code%>
//Powered by [KawigiEdit] 2.0!