SPOJ 707. Triple-Free Sets

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

Brief description:

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

Analysis:

HNOI 2012. 集合選數

需要預處理 + 二分查找。。。。。
首先考察所有。。。
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/