HackerRank/stone_game.cpp at master · fedeoliv/HackerRank · GitHub

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
#include<string.h>

typedef long long LL;
const int MODULO = 1000000007, N = 120;
int dp[N][32][2], vx[N][32], valid[32], mi[N];

int solve(int n,int k) {
    for(int i = 0;i <= 31; i++) vx[0][i] = 0;

        memset(dp,0,sizeof(dp));
        dp[0][0][0] = 1;

        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 31; j++)
                vx[i][j] = (vx[i-1][j] ^ (mi[i]&(1<<j)));

        valid[31] = 1;

        for(int i = 30; i >= 0; i--)
            valid[i] = valid[i+1] && (vx[n][i] == (k & (1<<i)));

        for(int i = 1; i <= n; i++)
            for(int j = 0; j < 31; j++)
                for(int kj = 0; kj < 2; kj++) {
                    if (dp[i-1][j][kj] == 0) continue;

                    for(int k = 0; k < 31; k++)
                        if (mi[i] & (1<<(k))) {
                            int small, tmpj, tmpkj;

                            if (k > j) {
                                small = j;
                                tmpj = k;
                                tmpkj = (vx[i-1][k] ? 1 : 0);
                            } else {
                                small = k;
                                tmpj = j;

                                if (k == j)
                                    tmpkj = kj;
                                else
                                    tmpkj = kj^((mi[i] & (1<<j)) ? 1 : 0);
                            }

                            dp[i][tmpj][tmpkj] = (dp[i][tmpj][tmpkj] + ((LL) dp[i-1][j][kj]) * (1<<small)) % MODULO;
                        }
                }

        int res = 0;

        for(int i = 30; i >= 0; i--)
            if (valid[i+1])
                res = (res + dp[n][i][(k & (1<<i)) ? 1 : 0]) % MODULO;
            else break;

        return res;
}

int main() {
    int n, k = 0, res;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) {
        scanf("%d", &mi[i]);
        mi[i]++;
    }

    res = solve(n,k);

    for(int i = 1; i <= n; i++) mi[i]--;
    res = (res + MODULO - solve(n,k)) % MODULO;
    printf("%d\n", res);

    return 0;
}