Language: C++

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define rer(i, n) for (int i = n; i >= 0; i--)
#define sz(a) (int)a.size()


int MOD = 998244353;
struct mint {
    int x;
    mint() : x(0) {}
    mint(int a) {
        x = a % MOD;
        if (x < 0) x += MOD;
    }
    mint &operator+=(mint that) {
        x = (x + that.x) % MOD;
        return *this;
    }
    mint &operator-=(mint that) {
        x = (x + MOD - that.x) % MOD;
        return *this;
    }
    mint &operator*=(mint that) {
        x = (int) x * that.x % MOD;
        return *this;
    }
    mint &operator/=(mint that) { return *this *= that.inverse(); }
    mint operator-() { return mint(-this->x); }
    friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }
    mint inverse() {
        int a = x, b = MOD, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b;
            u -= t * v;
            swap(a, b);
            swap(u, v);
        }
        return mint(u);
    }
    operator int() const { return x; }
    template<class T> mint &operator+=(T that) { return operator+=((mint) that); }
    template<class T> mint &operator-=(T that) { return operator-=((mint) that); }
    template<class T> mint &operator*=(T that) { return operator*=((mint) that); }
    template<class T> mint &operator/=(T that) { return operator/=(that); }
    mint operator+(mint that) { return mint(*this) += that; }
    mint operator-(mint that) { return mint(*this) -= that; }
    mint operator*(mint that) { return mint(*this) *= that; }
    mint operator/(mint that) { return mint(*this) /= that; }
    template<class T> mint operator+(T that) { return mint(*this) += (mint) that; }
    template<class T> mint operator-(T that) { return mint(*this) -= (mint) that; }
    template<class T> mint operator*(T that) { return mint(*this) *= (mint) that; }
    template<class T> mint operator/(T that) { return mint(*this) /= (mint) that; }
    bool operator==(mint that) const { return x == that.x; }
    bool operator!=(mint that) const { return x != that.x; }
    bool operator<(mint that) const { return x < that.x; }
    bool operator<=(mint that) const { return x <= that.x; }
    bool operator>(mint that) const { return x > that.x; }
    bool operator>=(mint that) const { return x >= that.x; }
};
typedef vector<mint> vm;
template<typename T, typename U> mint mpow(const T a, const U b) {
    assert(b >= 0);
    int x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) (res *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return res;
}
using vm = vector<mint>;



//aをbit列と見なし反転
string operator~(string &a) {
    string res = a;
    for (auto &&c:res) {
        if (c == '0')c = '1';
        else if (c == '1')c = '0';
        else {
            cerr << "cant ~" << a << "must bit" << endl;
            exit(0);
        }
    }
    return res;
}

vi divisors(int v) {
    vi res;
    double lim = std::sqrt(v);
    for (int i = 1; i <= lim; ++i) { if (v % i == 0) { res.push_back(i);/*                if (i != v / i)res.push_back(v / i);*/            }}
    for (int i = sz(res) - 1; i >= 0; i--) { if (res[i] != v / res[i])res.push_back(v / res[i]); }
    return res;
}
constexpr int bsetlen = 202020;
bool operator<(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return false;}
bool operator>(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return false;}
bool operator<=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return true;}
bool operator>=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return true;}


signed main() {
    int N;
    string X;
    cin >> N >> X;
    //Kを操作回数として扱っている
    vi K;
    {
        auto D = divisors(N * 2);
        for (auto &&k: D) {
            if ((k % 2) == 0)K.push_back(k);//kは偶数でN*2の約数
        }
    }
    int lim = N * 2 + 1;
    vector<mint> cou(lim);//周期が[k]となるような物の数
    mint res = 0;

    bitset<bsetlen> bx(X);
    for (auto &&k:K) {
        mint part = 0;
        //先頭k/2桁を決めれば後は一意に定まる
        //先頭k/2桁の自明に小さい取り方を数える
        rep(i, k / 2) {
            if (X[i] == '1')part += mpow(2, k / 2 - 1 - i);
        }
        {
            string tail = X.substr(0, k / 2);
            string head = ~tail;//mainの上

            string tx = tail;
            string sk = head+tail;
#include <bits/stdc++.h>

            using namespace std;
            using vi = vector<int>;
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define rer(i, n) for (int i = n; i >= 0; i--)
#define sz(a) (int)a.size()


            int MOD = 998244353;
            struct mint {
                int x;
                mint() : x(0) {}
                mint(int a) {
                    x = a % MOD;
                    if (x < 0) x += MOD;
                }
                mint &operator+=(mint that) {
                    x = (x + that.x) % MOD;
                    return *this;
                }
                mint &operator-=(mint that) {
                    x = (x + MOD - that.x) % MOD;
                    return *this;
                }
                mint &operator*=(mint that) {
                    x = (int) x * that.x % MOD;
                    return *this;
                }
                mint &operator/=(mint that) { return *this *= that.inverse(); }
                mint operator-() { return mint(-this->x); }
                friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }
                mint inverse() {
                    int a = x, b = MOD, u = 1, v = 0;
                    while (b) {
                        int t = a / b;
                        a -= t * b;
                        u -= t * v;
                        swap(a, b);
                        swap(u, v);
                    }
                    return mint(u);
                }
                operator int() const { return x; }
                template<class T> mint &operator+=(T that) { return operator+=((mint) that); }
                template<class T> mint &operator-=(T that) { return operator-=((mint) that); }
                template<class T> mint &operator*=(T that) { return operator*=((mint) that); }
                template<class T> mint &operator/=(T that) { return operator/=(that); }
                mint operator+(mint that) { return mint(*this) += that; }
                mint operator-(mint that) { return mint(*this) -= that; }
                mint operator*(mint that) { return mint(*this) *= that; }
                mint operator/(mint that) { return mint(*this) /= that; }
                template<class T> mint operator+(T that) { return mint(*this) += (mint) that; }
                template<class T> mint operator-(T that) { return mint(*this) -= (mint) that; }
                template<class T> mint operator*(T that) { return mint(*this) *= (mint) that; }
                template<class T> mint operator/(T that) { return mint(*this) /= (mint) that; }
                bool operator==(mint that) const { return x == that.x; }
                bool operator!=(mint that) const { return x != that.x; }
                bool operator<(mint that) const { return x < that.x; }
                bool operator<=(mint that) const { return x <= that.x; }
                bool operator>(mint that) const { return x > that.x; }
                bool operator>=(mint that) const { return x >= that.x; }
            };
            typedef vector<mint> vm;
            template<typename T, typename U> mint mpow(const T a, const U b) {
                assert(b >= 0);
                int x = a, res = 1;
                U p = b;
                while (p > 0) {
                    if (p & 1) (res *= x) %= MOD;
                    (x *= x) %= MOD;
                    p >>= 1;
                }
                return res;
            }
            using vm = vector<mint>;



//aをbit列と見なし反転
            string operator~(string &a) {
                string res = a;
                for (auto &&c:res) {
                    if (c == '0')c = '1';
                    else if (c == '1')c = '0';
                    else {
                        cerr << "cant ~" << a << "must bit" << endl;
                        exit(0);
                    }
                }
                return res;
            }

            vi divisors(int v) {
                vi res;
                double lim = std::sqrt(v);
                for (int i = 1; i <= lim; ++i) { if (v % i == 0) { res.push_back(i);/*                if (i != v / i)res.push_back(v / i);*/            }}
                for (int i = sz(res) - 1; i >= 0; i--) { if (res[i] != v / res[i])res.push_back(v / res[i]); }
                return res;
            }
            constexpr int bsetlen = 202020;
            bool operator<(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return false;}
            bool operator>(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return false;}
            bool operator<=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return true;}
            bool operator>=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return true;}


            signed main() {
                int N;
                string X;
                cin >> N >> X;
                //Kを操作回数として扱っている
                vi K;
                {
                    auto D = divisors(N * 2);
                    for (auto &&k: D) {
                        if ((k % 2) == 0)K.push_back(k);//kは偶数でN*2の約数
                    }
                }
                int lim = N * 2 + 1;
                vector<mint> cou(lim);//周期が[k]となるような物の数
                mint res = 0;

                bitset<bsetlen> bx(X);
                for (auto &&k:K) {
                    mint part = 0;
                    //先頭k/2桁を決めれば後は一意に定まる
                    //先頭k/2桁の自明に小さい取り方を数える
                    rep(i, k / 2) {
                        if (X[i] == '1')part += mpow(2, k / 2 - 1 - i);
                    }
                    {
                        string tail = X.substr(0, k / 2);
                        string head = ~tail;//mainの上

                        string tx = tail;
                        string sk = head+tail;
                        //size
                        while (sz(tx) < N) tx += sk;
                        if (sz(tx) != N)continue; //予防だが使われない txのサイズは必ずN
                        bitset<bsetlen> btx(tx);
                        if (bx >= btx) part += 1;
                    }
                    cou[k] += part;
                    res += cou[k] * k;
                    for (int s = k * 2; s < lim; s += k) {
                        cou[s] -= cou[k];//周期kはkの倍数sでも数えられるため引いておく
                    }
                }
                cout << res << endl;
                return 0;
            }//size
            while (sz(tx) < N) tx += sk;
            if (sz(tx) != N)continue; //予防だが使われない txのサイズは必ずN
            bitset<bsetlen> btx(tx);
            if (bx >= btx) part += 1;
        }
        cou[k] += part;
        res += cou[k] * k;
        for (int s = k * 2; s < lim; s += k) {
            cou[s] -= cou[k];//周期kはkの倍数sでも数えられるため引いておく
        }
    }
    cout << res << endl;
    return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:171:33: error: cannot define friend function 'operator<<' in a local class definition
  171 |                 friend ostream &operator<<(ostream &out, mint m) { return out << m.x; }
      |                                 ^~~~~~~~
a.cc:171:33: error: 'std::ostream& main()::mint::operator<<(std::ostream&, main()::mint)' must have exactly one argument
a.cc:184:17: error: invalid declaration of member template in local class
  184 |                 template<class T> mint &operator+=(T that) { return operator+=((mint) that); }
      |                 ^~~~~~~~
a.cc:185:17: error: invalid declaration of member template in local class
  185 |                 template<class T> mint &operator-=(T that) { return operator-=((mint) that); }
      |                 ^~~~~~~~
a.cc:186:17: error: invalid declaration of member template in local class
  186 |                 template<class T> mint &operator*=(T that) { return operator*=((mint) that); }
      |                 ^~~~~~~~
a.cc:187:17: error: invalid declaration of member template in local class
  187 |                 template<class T> mint &operator/=(T that) { return operator/=(that); }
      |                 ^~~~~~~~
a.cc:192:17: error: invalid declaration of member template in local class
  192 |                 template<class T> mint operator+(T that) { return mint(*this) += (mint) that; }
      |                 ^~~~~~~~
a.cc:193:17: error: invalid declaration of member template in local class
  193 |                 template<class T> mint operator-(T that) { return mint(*this) -= (mint) that; }
      |                 ^~~~~~~~
a.cc:194:17: error: invalid declaration of member template in local class
  194 |                 template<class T> mint operator*(T that) { return mint(*this) *= (mint) that; }
      |                 ^~~~~~~~
a.cc:195:17: error: invalid declaration of member template in local class
  195 |                 template<class T> mint operator/(T that) { return mint(*this) /= (mint) that; }
      |                 ^~~~~~~~
a.cc: In constructor 'main()::mint::mint(long long int)':
a.cc:154:29: error: use of local variable with automatic storage from containing function
  154 |                     x = a % MOD;
      |                             ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc:155:37: error: use of local variable with automatic storage from containing function
  155 |                     if (x < 0) x += MOD;
      |                                     ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc: In member function 'main()::mint& main()::mint::operator+=(main()::mint)':
a.cc:158:40: error: use of local variable with automatic storage from containing function
  158 |                     x = (x + that.x) % MOD;
      |                                        ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc: In member function 'main()::mint& main()::mint::operator-=(main()::mint)':
a.cc:162:30: error: use of local variable with automatic storage from containing function
  162 |                     x = (x + MOD - that.x) % MOD;
      |                              ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc:162:46: error: use of local variable with automatic storage from containing function
  162 |                     x = (x + MOD - that.x) % MOD;
      |                                              ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc: In member function 'main()::mint& main()::mint::operator*=(main()::mint)':
a.cc:166:44: error: use of local variable with automatic storage from containing function
  166 |                     x = (int) x * that.x % MOD;
      |                                            ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc: In member function 'main()::mint main()::mint::inverse()':
a.cc:173:36: error: use of local variable with automatic storage from containing function
  173 |                     int a = x, b = MOD, u = 1, v = 0;
      |                                    ^~~
a.cc:149:17: note: 'long long int MOD' declared here
  149 |             int MOD = 998244353;
      |                 ^~~
a.cc:177:25: error: 'u' was not declared in this scope
  177 |                         u -= t * v;
      |                         ^
a.cc:177:34: error: 'v' was not declared in this scope; did you mean 'vi'?
  177 |                         u -= t * v;
      |                                  ^
      |                                  vi
a.cc:181:33: error: 'u' was not declared in this scope
  181 |                     return mint(u);
      |                                 ^
a.cc: In function 'int main()':
a.cc:204:13: error: a template declaration cannot appear at block scope
  204 |             template<typename T, typename U> mint mpow(const T a, const U b) {
      |             ^~~~~~~~
a.cc:220:41: error: a function-definition is not allowed here before '{' token
  220 |             string operator~(string &a) {
      |                                         ^
a.cc:233:32: error: a function-definition is not allowed here before '{' token
  233 |             vi divisors(int v) {
      |                                ^
a.cc:241:68: error: a function-definition is not allowed here before '{' token
  241 |             bool operator<(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return false;}
      |                                                                    ^
a.cc:242:68: error: a function-definition is not allowed here before '{' token
  242 |             bool operator>(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return false;}
      |                                                                    ^
a.cc:243:69: error: a function-definition is not allowed here before '{' token
  243 |             bool operator<=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] < b[i])return true;if (a[i] > b[i])return false;}return true;}
      |                                                                     ^
a.cc:244:69: error: a function-definition is not allowed here before '{' token
  244 |             bool operator>=(bitset<bsetlen> &a, bitset<bsetlen> &b) {rer(i, bsetlen - 1) {if (a[i] > b[i])return true;if (a[i] < b[i])return false;}return true;}
      |                                                                     ^
a.cc:247:24: warning: empty parentheses were disambiguated as a function declaration [-Wvexing-parse]
  247 |             signed main() {
      |                        ^~
a.cc:247:24: note: remove parentheses to default-initialize a variable
  247 |             signed main() {
      |                        ^~
      |                        --
a.cc:247:24: note: or replace parentheses with braces to value-initialize a variable
a.cc:247:27: error: a function-definition is not allowed here before '{' token
  247 |             signed main() {
      |                           ^