SRM 440 div-1 Hard (SquareFreeSets)

Problem Link

The problem in short:

A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.

You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.

Some observations:

1. In the prime factorization of a square-free number, each of it's prime factors occurs exactly once.
2. There are 95 prime numbers smaller than 500. So, the size of a perfect square-free set can't exceed 95.
3. There are only 8 primes {2,3,5,...,19} smaller than the square-root of 500.
4. In the prime factorization of any integer x, there can be at most 1 prime, which is greater than sqrt(x).
5. So, in the prime factorization of a square free number x <= 500, at most one prime p > 19, can exist.

The Dynamic Programming Solution:

Divide the numbers (1 to N) into buckets. Let, LP(x) be the largest prime factor of x. Two numbers x and y will be kept in the same bucket if and only if LP(x) = LP(y). Note that, in a perfect square-free set, no 2 elements will be from the same bucket.

Lets define dp[i][len][mask] to be the the number of perfect square-free sets of size 'len' and the elements are taken from the buckets 0,1,...i. 'mask' is a bit-mask that represents which of the 8 primes are already used. The rest is easy!

Here is the code that I submitted in the practice room:

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

const LL mod = 1000000007;
             
vector<pii> buck[505];
vector<int> primes;

bool is[505];
int smallPrimes[] = {2,3,5,7,11,13,17,19};
int pos[25];

void precalc(int n)
{
for(int i = 0; i < 8; ++i)
pos[smallPrimes[i]] = i;

for(int i = 2; i <= n; ++i)
{
 bool isSqFree = true;
 int temp = i, mask = 0;

 for(int j = 2; j*j <= temp; ++j)
 {
  int cnt = 0;
 
  while(temp%j==0)
  {
   temp /= j;
   ++cnt;
  }
 
  if(cnt)
  {
   mask|=(1<<pos[j]);
  }
 
  if(cnt>1)
  {
   isSqFree = false;
  }
 }

 if(temp > 1 && temp*temp<=n)
 {
  mask |= (1<<pos[temp]);
 }

 if(isSqFree)
 {
  buck[temp].push_back(pii(i,mask));
 }

 if(temp==i)
 {
  primes.push_back(i);
 }
}
}

LL dp[100][100][1<<8];

LL F(int i, int len, int mask)
{
if(len == 0) return 1;

if(i < 0) return 0;

LL& ret = dp[i][len][mask];
int p = primes[i];
if(ret>-1) return ret;

ret = F(i-1,len,mask);

FOR(j,buck[p].size())
{
 if((buck[p][j].second&mask)==0)
 {
  ret = (ret + F(i-1,len-1,mask|buck[p][j].second))%mod;
 }
}

return ret;
}

int calc(int k)
{
if(k > primes.size())
k = primes.size();

CLR(dp,-1);
LL ret = 0;

for(int len = 1; len <= k; ++len)
{
 ret = (ret + F(primes.size()-1,len,0))%mod;
}

return (int)ret;
}

class SquareFreeSets {
public:
int countPerfect(int N, int K) {
 precalc(N);
 return calc(K);
}
};