提出 #75902744

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int mod = 998244353;

int fix(int x){
    x%=mod;
    if(x<0)x+=mod;
    return x;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vi x(n+1), y(n+1), z(n+1);
    for(int i = 1; i<=n; i++){
        cin >> x[i] >> y[i] >> z[i];
    }
    vi masks(3);
    vector<vi>cost(n+1,vi(2,1));
    for(int b = 0; b<24; b++){
        vi amt(3);
        for(int i = 1; i<=n; i++){
            int add = (z[i] >> b) & 1;
            int L = (x[i] >> b) & 1;
            int R = (y[i] >> b) & 1;
            if(add)amt[2] += cost[i][0];
            else amt[1] += cost[i][0];
            if(L == 0 && R == 0)amt[2] += cost[i][1];
            if(L == 0 && R == 1)amt[0] += cost[i][1];
            if(L == 1 && R == 1)amt[1] += cost[i][1];
        }
        int mn = min({amt[0],amt[1],amt[2]});
        int idx = 0;
        if(amt[0] == mn)idx = 0;
        else if(amt[1] == mn)idx = 1;
        else idx = 2;
        masks[idx] ^= 1<<b;
        for(int i = 1; i<=n; i++){
            int add = (z[i] >> b) & 1;
            int L = (x[i] >> b) & 1;
            int R = (y[i] >> b) & 1;
            if(add && idx == 2)cost[i][0] *= 2;
            if(!add && idx == 1)cost[i][0] *= 2;
            if(!L && !R && idx == 2)cost[i][1] *= 2;
            if(!L && R && idx == 0)cost[i][1] *= 2;
            if(L && R && idx == 1)cost[i][1] *= 2;
        }
    }
    vector<int>dp(n+1);
    vector<int>res(1<<24);
    const int all = (1<<24) - 1;
    // cout << masks[0] << ' ' << masks[1] << ' ' << masks[2] << '\n';
    for(int i = n; i>=1; i--){
        {
            dp[i] = 1;
            int m00 = (all^x[i]) & (all^y[i]);
            int m01 = (all^x[i]) & y[i];
            int m11 = x[i] & y[i];
            int add = (m11 & masks[0]) ^ (m01 & masks[1]) ^ (m11 & masks[2]);
            int ans = 0;
            for(int mask1 = masks[0] & m01; mask1 >= 0; mask1 = (mask1 - 1) & masks[0] & m01){
                for(int mask2 = masks[1] & m11; mask2 >= 0; mask2 = (mask2 - 1) & masks[1] & m11){
                    for(int mask3 = masks[2] & m00; mask3 >= 0; mask3 = (mask3 - 1) & masks[2] & m00){
                        int mult = 1;
                        int cnt = __builtin_popcount((masks[1] & m11) ^ mask2) + __builtin_popcount(mask3);
                        if(cnt % 2 == 1)mult = -1;
                        ans += res[mask1^mask2^mask3^add] * mult; ans = fix(ans);
                        if(mask3 == 0)break;
                    }
                    if(mask2 == 0)break;
                }
                if(mask1 == 0)break;
            }
            dp[i] += ans; dp[i] = fix(dp[i]);
        }
        {
            int fixed = (masks[0] & z[i]) ^ (masks[1] & z[i]);
            int bigmask = ((z[i] ^ all) & masks[1]) ^ (z[i] & masks[2]);
            for(int mask1 = bigmask; mask1 >= 0; mask1 = (mask1 - 1) & bigmask){
                res[mask1^fixed] += dp[i]; res[mask1^fixed] %= mod;
                if(mask1 == 0)break;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i<=n; i++){
        ans += dp[i] - 1; ans = fix(ans);
    }
    cout << ans << '\n';
    return 0;
}

提出情報

ジャッジ結果