Algoogle

Algorithm for Programming Contest

PKU 3252 Round Numbers

Category: PKU Tag: dp

Round Numbers

問題概要


与えられた閉区間でビットに直した時に0の個数のほうが1の個数より多い数はいくつあるか.

解法


いわゆる桁DPをする. dp[i][j][k][l] := iビット目がkで, 0の個数がj個になる個数. lは求めたい数より大きくなる可能性があるかどうか
これでdp[i][j][1][0]にiビット目が1のときの0の個数が出るので条件を満たす個数を数えられる.
求めたい数の最上位ビットが立ってる数についてはこれで求まる.
その他はiビット目が1のときの0の個数の組み合わせを数えればいい.

コード


(3252.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>

using namespace std;

int ans, in[2];
int dp[64][64][2][2];
int combi[64][64];

void gen(){
    combi[0][0] = 1;
    for(int i = 1; i < 64; i++){
        combi[i][0] = 1;
        for(int j = 1; j <= i; j++)
            combi[i][j] = combi[i-1][j-1]+combi[i-1][j];
    }
}

int calc(int p){
    int ret = 0;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0] = 1;
    for(int i = 1, t = p; t > 0; i++){
        int b = t % 2; t >>= 1;
        for(int j = 0; j < i; j++)
            for(int k = 0; k < 2; k++)
                if(k < b)
                    for(int x = 0; x < 2; x++)
                        for(int y = 0; y < 2; y++)
                            dp[i][j+1][k][0] += dp[i-1][j][x][y];
                else if(k == b)
                    for(int x = 0; x < 2; x++){
                        dp[i][j+(k==0)][k][0] += dp[i-1][j][x][0];
                        dp[i][j+(k==0)][k][1] += dp[i-1][j][x][1];
                    }
                else
                    for(int x = 0; x < 2; x++)
                        for(int y = 0; y < 2; y++)
                            dp[i][j][k][1] += dp[i-1][j][x][y];
        if(!t){
            for(int j = i; j > (i-1)/2; j--)
                ret += dp[i][j][1][0];
            for(int k = 1; k < i; k++)
                for(int j = k-1; j > (k-1)/2; j--)
                    ret += combi[k-1][j];
        }
    }
    return ret+1;
}

int main(){
    gen();
    /*
    while(1){
        int p; cin >> p;
        cerr << "-> " << calc(p) << endl;
    }
    */
    scanf("%d%d", in, in+1);
    in[0]--;
    printf("%d\n", calc(in[1])-calc(in[0]));
    return 0;
}

Comments