提出 #75560141

---

ソースコード 拡げる

#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;
    string s;
    cin >> s;
    vi a(1<<n);
    vi pw(n+1);
    pw[0] = 1;
    pw[1] = 10;
    for(int i = 2; i<=n; i++){
        pw[i] = pw[i-1] * pw[i-1] % mod;
    }
    for(int i = 0; i<(1<<n); i++){
        a[i] = s[i] - '0';
    }
    vi arr(1<<n);
    vi cnt(1<<n);
    auto self = [&](auto &&self, int l, int r) -> void {
        if(r - l == 1){
            arr[l] = a[l];
            cnt[l] = 1;
            return;
        }
        int m = (l+r)/2;
        self(self,l,m);
        self(self,m,r);
        for(int i = m; i<r; i++){
            arr[i] = arr[i - (r-m)] * pw[cnt[i]] + arr[i]; arr[i] = fix(arr[i]);
            cnt[i]++;
        }
    };
    self(self,0,1<<n);
    int ans = 0;
    for(int i = 0; i<(1<<n); i++){
        ans += (arr[i] ^ i);
    }
    cout << ans << '\n';
    return 0;
}

提出情報

ジャッジ結果