# 某岛

… : "…アッカリ～ン . .. . " .. .
October 8, 2014

## SPOJ 707. Triple-Free Sets

http://www.spoj.com/problems/TFSETS/

### Analysis:

2^a 3^b

1
2 3
4 6 9
8 …

1 3 9 27 …
2 6 18 ..

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2828033


const int N = (1e5) + 9, M = 12;

vector<PII> I;

int f(int n){

static bool Map[N][M]; static Int F[2][1<<M];

RST(Map); int r = 0, c = 0, x, xx;

for(r=0,x=1;x<=n;++r,x*=2){
int j; for (j=0,xx=x;xx<=n;++j,xx*=3) Map[r][j] = 1;
if (!c) c = j;
}

int p = 0, q = 1; RST(F[p]); F[p][0]=1;

REP_2(i, j, r, c){
swap(p, q); RST(F[p]);
#define u F[q][s]
#define v0 F[p][s<<1&_U(c)]
#define v1 F[p][s<<1|1&_U(c)]
REP(s, _1(c)) if (u){
v0 += u;
if (Map[i][j] && (!j || !_1(s, 0))) v1 += u;
}
}
Int z = 0; REP(s, _1(c)) z += F[p][s];
return z;
}

int ff(int n){
Int z = 1; REP_1(i, n) if(i % 2 && i % 3){
z *= (upper_bound(ALL(I), MP(n/i, INF))-1)->se;
}
return z;
}

void Init(){
for (int x=1;x<=N;x*=2){
for (int xx=x;xx<=N;xx*=3) I.PB(MP(xx, f(xx)));
}
SRT(I);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

Init(); Rush OT(ff(RD()));
}



### References:

http://ydcydcy1.blog.163.com/blog/static/2160890402013195167512/