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

### Brief description:

求有多少 {1..n} 的子集，滿足若 x 在該子集中，則 2x 和 3x 不在該子集中。（n ≤ 100000）

### Analysis:

需要預處理 + 二分查找。。。。。

首先考察所有。。。

2^a 3^b

1

2 3

4 6 9

8 ...

那麼 f(x) 的結果三角形填數。。要求相鄰格子不能同時為 1.。的方案數。。。。

對於所有非 2^a 3^b 的數 p。。。它和所有的。。p 2^a 3^b 又可以形成一組三角形。。彼此獨立。。乘法原理。。

且所有的三角形中最大的數都是 2^a 3^b 的形式。。預處理所有這些解。。方便起見我們旋轉一下

1 3 9 27 ...

2 6 18 ..

這樣 m 最大值只有 lg3(n)。。

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/