Logical Operations [yukicoder No.685]

https://yukicoder.me/problems/no/685

考察

1. mod10^9+7の時点でDPかなという感じ
2. AND,XOR,ORはビット毎に独立して考えられる
3. 大小関係は上位ビットから順番に確定すれば状態をまとめられそう
4. 桁DP

解法

https://yukicoder.me/submissions/257060

dp[dig][state1][state2][state3]
digビット目まで確定
state1はx,y,Nの大小関係
state2はandとxorの大小関係
state3はxorとorの大小関係
の場合の組合せ
　
桁DPはメモ化再帰で書くのがオススメ。
xとyに0か1を割り当てるので、各状態で4通りの遷移があるが、state1とstate3によって割り当てることが出来るかが決まるので、その部分で分岐を書こう。
かなり根性DPなので、桁DPに慣れないままこの問題に取り組むのはおすすめしない。

ll N;
//---------------------------------------------------------------------------------------------------
// state1
// 0:x=y=N
// 1:x<y=N
// 2:x=y<N
// 3:x<y<N

// state2
// 0:and=xor
// 1:and<xor

// state3
// 0:xor=or
// 1:xor<or
mint memo[70][4][2][2];
int vis[70][4][2][2];
mint f(int dig, int state1, int state2, int state3) {
    if (dig < 0) {
        if (state2 == 1 and state3 == 1) return 1;
        else return 0;
    }

    if (vis[dig][state1][state2][state3]) return memo[dig][state1][state2][state3];

    ll b = 1LL << dig;

    int d = ((N & b) != 0);

    mint res = 0;
    if (state1 == 0) {
        if (d == 0) res = f(dig - 1, 0, state2, state3); // 0 0
        else {
            if(state2 == 1) res += f(dig - 1, 0, 1, 1); // 1 1
            res += f(dig - 1, 1, 1, state3); // 0 1
            res += f(dig - 1, 2, state2, state3); // 0 0
        }
    } 
    else if (state1 == 1) { // 1:x<y=N
        if (d == 0) {
            res += f(dig - 1, 1, 1, state3); // 1 0
            res += f(dig - 1, 1, state2, state3); // 0 0
        }
        else {
            if (state2 == 1) res += f(dig - 1, 1, 1, 1); // 1 1
            res += f(dig - 1, 1, 1, state3); // 0 1
            res += f(dig - 1, 3, 1, state3); // 1 0
            res += f(dig - 1, 3, state2, state3); // 0 0
        }
    }
    else if (state1 == 2){ // 2:x=y<N
        if (state2 == 1) res += f(dig - 1, 2, 1, 1); // 1 1
        res += f(dig - 1, 3, 1, state3); // 0 1
        res += f(dig - 1, 2, state2, state3); // 0 0
    }
    else {
        if (state2 == 1) res += f(dig - 1, 3, 1, 1); // 1 1
        res += f(dig - 1, 3, 1, state3); // 0 1
        res += f(dig - 1, 3, 1, state3); // 1 0
        res += f(dig - 1, 3, state2, state3); // 0 0
    }

    vis[dig][state1][state2][state3] = 1;
    return memo[dig][state1][state2][state3] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cout << f(60, 0, 0, 0) << endl;
}