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/

Posted by xiaodao
Category: SPOJ