cafelier@SRM

SRM440 1000 (2009/05/13)

あとで | 12:49 |

だいたいあってた

static const int MODVAL = 1000000007;

bool is_square_free(int n)
{
  for(int p=2; p*p<=n; ++p)
    if( n%(p*p) == 0 )
      return false;
  return true;
}

static const int SP[] = {2,3,5,7,11,13,17,19}; // <= sqrt(N)
static const int SPN  = sizeof(SP)/sizeof(*SP);

int small_prime_mask(int n)
{
  int m = 0;
  for(int i=0; i<SPN; ++i)
    if( n%SP[i] == 0 )
      m |= 1<<i;
  return m;
}

int big_prime_factor(int n)
{
  for(int i=0; i<SPN; ++i)
    while( n%SP[i] == 0 )
      n /= SP[i];
  return n;
}

class SquareFreeSets {
public:
  int countPerfect(int N, int K) 
  {
    // way[k][m] = # of ways to make a k-elem psf-set with small prime factors m
    int way[501][1<<SPN] = {};
    way[0][0] = 1;

    for(int n=2; n<=N; ++n)
      if( is_square_free(n) )
        if( big_prime_factor(n) == 1 )
        {
          int mask = small_prime_mask(n);
          for(int k=K; k>=1; --k)
            for(int m=0; m<(1<<SPN); ++m)
              if( (m|mask) == m )
                way[k][m] = (way[k][m] + way[k-1][m&~mask]) % MODVAL;
        }
        else if( big_prime_factor(n) == n )
        {
          vector<int> mask;
          for(int p=1; n*p<=N; ++p)
            if( is_square_free(p) )
              mask.push_back( small_prime_mask(p) );

          for(int k=K; k>=1; --k)
            for(int m=0; m<(1<<SPN); ++m)
              for(int j=0; j<mask.size(); ++j)
                if( (m|mask[j]) == m )
                  way[k][m] = (way[k][m] + way[k-1][m&~mask[j]]) % MODVAL;
        }

    // summing up
    int sum = 0;
    for(int k=1; k<=K; ++k)
      for(int m=0; m<(1<<SPN); ++m)
        sum = (sum + way[k][m]) % MODVAL;
    return sum;
  }
};

ただし19＜sqrt(500)までの使用済みフラグを持っているだけではそのままではダメで（たとえば23と46が同時に入れられないという条件が抜けてしまう）、23を入れるときに同時に46,69,...を入れるパターンも試してみることで19より大きい共通素因数は省く方針で。もう少し整理すると綺麗になるかも…。