gistfile1.cpp

#include <cstdio>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <numeric>
#include <bitset>

using namespace std;

typedef list<int> EdgeList;
typedef set<EdgeList> AdjList;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

const int sz = 10000000;
bitset<sz/2> pbits;
vector<int> primes[1 << 9];
int prime_cnts[1<<9];
void setup();
void read_primes();
void write_primes();
void write_prime_cnts();
void read_prime_cnts();

vector<int> chosen;
int memo[1 << 9];
int solve(int mask) {
  if (mask == 0) {
    return 1;
  }
  //if (memo[mask] != -1) return memo[mask];
  int cnt = 0;
  for (int mask2 = mask; mask2; mask2 = (mask2 - 1) & mask) {
    for (vector<int>::iterator it = primes[mask2].begin();
        it != primes[mask2].end(); ++it) {
      int p = *it;
      // ensure uniqueness!
      if (chosen.size() > 0 && p < chosen.back()) break;
      chosen.push_back(p);
      cnt += solve(mask ^ mask2);
      chosen.pop_back();
    }
  }
  return cnt; //(memo[mask] = cnt);
}

int main() {
  //setup();
  //write_primes();
  read_primes();
  //write_prime_cnts();
  //read_prime_cnts();

  fill(memo, memo + (1 << 9), -1);
  printf("%d\n", solve(0x1ff));

  return 0;
}

void setup() {
  const int cap = sqrt(sz) + 1;
  pbits.set();
  for (int i = 3; i < cap; i += 2) {
    if (pbits[i/2]) {
      for (int j = i*i/2; j < sz/2; j += i) {
        pbits.reset(j);
      }
    }
  }

  primes[2].push_back(2);
  for (int i = 1; i < sz/2; ++i) {
    if (pbits[i]) {
      bool good = true;
      int p = 2*i+1;
      int mask = 0;
      while (p > 0) {
        int d = p % 10;
        p /= 10;
        if (d == 0) {
          good = false;
          break;
        }
        if ((mask >> (d-1)) & 1) {
          good = false;
          break;
        }
        mask ^= 1 << (d-1);
      }
      if (good) {
        primes[mask].push_back(2*i+1);
      }
    }
  }
}


void read_prime_cnts() {
  FILE *f = fopen("primes_cnt.lst", "r");
  for (int i = 0; i < (1 << 9); ++i) {
    fscanf(f, "%d", &prime_cnts[i]);
  }
  fclose(f);
}

void write_prime_cnts() {
  FILE *f = fopen("primes_cnt.lst", "w");
  for (int i = 0; i < (1 << 9); ++i) {
    fprintf(f, "%d ",primes[i].size());
  }
  fclose(f);
}

void read_primes() {
  FILE *f = fopen("primes.lst", "r");
  for (int i = 0; i < (1 << 9); ++i) {
    int sz;
    fscanf(f, "%d", &sz);
    for (int j = 0; j < sz; ++j) {
      int x;
      fscanf(f, "%d", &x);
      primes[i].push_back(x);
    }
  }
  fclose(f);
}

void write_primes() {
  FILE *f= fopen("primes.lst", "w");
  for (int j = 0; j < (1 << 9); ++j) {
    fprintf(f, "%d ", primes[j].size());
    for (int i = 0; i < primes[j].size(); ++i) {
      fprintf(f, " %d", primes[j][i]);
    }
    fprintf(f, "\n");
  }
  fclose(f);
}