Learning Algorithms

アルゴリズムの勉強メモ

DDCC 2017 D. なめらかな木

DDCC 2017 D. なめらかな木

D: なめらかな木 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder

解法

bitDPをする

実装
#include "bits/stdc++.h"
using namespace std;

const int MOD = 1000000007;

int n;
vector<int> g[55];
map<tuple<long long, int, int>, long long> dp;

long long dfs(long long s, int prev, int pprev) {
        if (__builtin_popcountll(s) == n) return 1;
        for (int x = 0; x < n; x ++) {
                for (auto y : g[x]) {
                        if (x == prev || x == pprev) continue;
                        if (y == prev || y == pprev) continue;
                        bool used1 = (s & (1LL << x)) != 0;
                        bool used2 = (s & (1LL << y)) != 0;
                        if (used1 != used2) return 0;
                }
        }
        auto key = tuple<long long, int, int> (s, prev, pprev);
        if (dp.count(key)) return dp[key];
        long long sum = 0;
        for (int x = 0; x < n; x ++) {
                if (s & (1LL << x)) continue;
                sum += dfs(s | (1LL << x), x, prev);
        }
        return dp[key] = sum % MOD;
}

int main() {
        scanf("%d", &n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        for (int i = 0; i < n; i ++) if (g[i].size() > 4) return !puts("0");
        printf("%lld\n", dfs(0, -1, -1));
        return 0;
}

Atcoder Grand Contest 009 E. Eternal Average

Atcoder Grand Contest 009 E. Eternal Average

E: Eternal Average - AtCoder Grand Contest 009 | AtCoder

感想

実装軽いのに考察が重すぎる...。

解法

最終的に残る数を$\ x\ $とする。$\ x\ $は連分数で書かれるような数になるが、このまま考えるとわかりにくいので、これを完全$\ K\ $分木で考える。各葉には$\ 1, 0\ $が書かれていて、その親ノードにはその平均が書かれている。

この根ノードに書かれた数が$\ x\ $になるが、これはそれぞれの葉の深さを$\ depth_i\ $とし、書かれた数を$\ p_i = \{ 0, 1 \}\ $とすると、$\ x = \sum K^{-depth_i} * p_i\ $となる。

さて、$\ 0\ $と書かれたノードの深さの列を$\ a_1, a_2, ..., a_n\ $、$\ 1\ $と書かれたノードの深さの列を$\ b_1, b_2, ..., b_m\ $とする。このとき次の条件を得る。

$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} + K^{-b_1} + K^{-b_2} + ... + K^{b_m} = 1\ $

これは気づきにくいが、木を書いてみればわかる。逆にこの条件が成り立つとき、その$\ x\ $が残るように木が構成できることも言える。さらに上に書いた$\ x\ $を用いて書きなおすと、

$\ K^{-b_1} + K^{-b_2} + ... + K^{-b_m} = x\ $
$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} = 1 - x\ $

となる。

次に、$\ K\ $進法によって$\ x = 0.d_1d_2...d_l\ $、$\ 1 - x = 0.e_1e_2...e_l\ $と書く。ただし$\ d_l \neq 0, e_l \neq 0\ $とする。これについて満たすべき条件というのは、以下のようになる。

$\ \sum d_i \equiv m\ (mod\ K - 1)\ ...(A)\ $
$\ \sum e_i \equiv n\ (mod\ K - 1)\ ...(B)\ $

なぜかというと、$\ b_i\ $の各項が増えるごとに、ある桁に$\ 1\ $が足されるはずなので、$\ b_i\ $の項数が$\ m\ $であるならば$\ m\ $回$\ 1\ $が加えられているはずだが、繰り上がりを考慮すると、$\ K - 1 + 1 \equiv 1\ $であるため、$\ mod\ K - 1\ $で考えると$\ \sum d_i \equiv m\ $となっているはずだからである。同様に2番目の式も出てくる。

さらにこれらの和は$\ 1\ $になることから、次が言える。

$\ d_i + e_i = K - 1\ (i = l)\ $
$\ d_i + e_i = K\ (i \neq l)\ $

これを用いると、上の$\ (B)\ $を変形することができて、

$\ \sum_{i = 1}^{l - 1} (K - d_i - 1) + (K - d_l) \equiv n\ (mod\ K - 1)\ $

$\ lK - \sum_{i = 1}^{l} d_i - (l - 1) \equiv n\ (mod\ K - 1)\ $

よって以下を得る。

$\ l = \cfrac{n + \sum_{i = 1}^{l} d_i - 1}{k - 1}\ ...(C)\ $

さて、次の$\ dp\ $を考える。

$\ dp[i][j] := \ $ ($\ i\ $番目までの$\ d\ $を定めて$\ x\ $を構成したときに、その各桁の総和が$\ j\ $であるような場合の数)

この$\ dp\ $を計算し、上の条件$\ (A), (C)\ $を満たすようなものについての総和をとれば答えになる。

実装
#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

signed main() {
        int n, m, k;
        scanf(&quot;%d%d%d&quot;, &n, &m, &k);
        int c = (n + m - 1) / (k - 1);
        vector<vector<long long>> dp(c + 1, vector<long long> (m + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= c; i ++) {
                for (int j = 0; j <= m; j ++) {
                        for (int l = 0; l < k && j + l <= m; l ++) {
                                (dp[i][j + l] += dp[i - 1][j]) %= MOD;
                        }
                }
        }
        long long ans = 0;
        while (m > 0) {
                int nc = (n + m - 1) / (k - 1);
                (ans += dp[nc][m]) %= MOD;
                m -= k - 1;
        }
        printf(&quot;%lld\n&quot;, ans);
        return 0;
}

Atcoder Grand Contest 008 D. K-th K

Atcoder Grand Contest 008 D. K-th K

D: K-th K - AtCoder Grand Contest 008 | AtCoder

解法

位置が確定しているものを左から順に確定させ、その数の左側に置かなければいけない個数を空いている場所に左詰めで書いていく。これができない場合は不可能。

位置が確定しているものをすべて書くことができたら、次にそれらの数の右側に置かなければいけない個数を左詰めで書いていく。これができない場合も不可能。

これらはどこまで書き込んだを示すポインタを一つ持つことで実装できる。$\ O(n^2)\ $。

#include &quot;bits/stdc++.h&quot;
using namespace std;

#define all(x) x.begin(), x.end()

int main() {
        int n;
        scanf(&quot;%d&quot;, &n);
        vector<pair<int, int>> x(n);
        for (int i = 0; i < n; i ++) { 
                scanf(&quot;%d&quot;, &x[i].first);
                x[i].first --;
                x[i].second = i + 1;
        }
        sort(all(x));
        int sp = 0;
        vector<int> ans(n * n, -1);
        for (int i = 0; i < n; i ++) {
                ans[x[i].first] = x[i].second;
                int add = x[i].second - 1;
                while (add --) {
                        if (ans[sp] != -1) add ++;
                        else ans[sp] = x[i].second;
                        sp ++;
                        if (sp > x[i].first) return !puts(&quot;No&quot;);
                }
        }
        for (int i = 0; i < n; i ++) {
                if (ans[sp] == -1 && sp < x[i].first) return !puts(&quot;No&quot;);
                int add = n - x[i].second;
                while (add --) {
                        if (ans[sp] != -1) add ++;
                        else ans[sp] = x[i].second;
                        sp ++;
                }
        }
        puts(&quot;Yes&quot;);
        for (int i = 0; i < n * n; i ++) cout << ans[i] << (i == n * n - 1 ? '\n' : ' ');
        return 0;   
}

Atcoder Grand Contest 013 E. Placing Squares(追記)

Atcoder Grand Contest 013 E. Placing Squares(追記)

E: Placing Squares - AtCoder Grand Contest 013 | AtCoder

感想

愚直$\ DP\ $の高速化に失敗したので、解説放送を見て想定解を実装した。

解法

$\ 0\ $から$\ n\ $までの任意の位置に柵をおいて、その柵で囲まれたところそれぞれに2色のボールを置く(同じ位置でも良い)ときの場合の数を求めればそれが答えである。

解説放送ではこれに気づけばあとは自明な$\ DP\ $で解けると言っていたが、この遷移で少し悩んだので丁寧に書く。

まず$\ dp[i][j] := \ $(区間$\ [0, i)\ $の配置が完了していて、完了している区間の中で一番右の柵より右側に置いてあるボールの個数が$\ j\ $個となっている場合の数)とする。

ここで注意することは、区間$\ i\ $の柵の状態は無視することである。位置$\ i - 1\ $と$\ i\ $の間の位置$\ P_i\ $に置くボールの個数と、位置$\ i - 1\ $に柵を置くかどうかで場合分けをして遷移を考える。

まず位置$\ i - 1\ $に印がない場合を考える(すなわち柵を置いてもよいし置かなくても良い)。例えば$\ dp[i][0]\ $の値は次のようになる。

$\ i - 1\ $に柵を置く場合、$\ dp[i][0]\ += dp[i - 1][2]\ $($\ P_i\ $にボールを置かない)
$\ i - 1\ $に柵を置かない場合、$\ dp[i][0]\ += dp[i - 1][0]\ $($\ P_i\ $にボールを置かない)

つまり、常に上の$\ dp[i][j]\ $の条件に矛盾しないように、ボールを置いて考えればよい。同様にすると、次のようになる。

$\ i - 1\ $に柵を置く場合、$\ dp[i][1]\ += 2 * dp[i - 1][2]\ $($\ P_i\ $にどちらかのボールを選んで置く)
$\ i - 1\ $に柵を置かない場合、$\ dp[i][1]\ += 2 * dp[i - 1][0]\ $($\ P_i\ $にどちらかのボールを選んで置く)$+ dp[i - 1][1]\ $($\ P_i\ $にボールを置かない)

$\ i - 1\ $に柵を置く場合、$\ dp[i][2]\ += dp[i - 1][2]\ $($\ P_i\ $に両方のボールを置く)
$\ i - 1\ $に柵を置かない場合、$\ dp[i][2]\ += dp[i - 1][0]\ $($\ P_i\ $に両方のボールを置く)$+ dp[i - 1][1]\ $(すでに置いてあるボールとは異なる色のボールを$\ P_i\ $に置く)$+ dp[i - 1][2]\ $($\ P_i\ $に置かない)

以上から、次が従う。

$dp[i][0] = 1 * dp[i - 1][0] + 0 * dp[i - 1][1] + 1 * dp[i - 1][2]\ $
$dp[i][1] = 2 * dp[i - 1][0] + 1 * dp[i - 1][1] + 2 * dp[i - 1][2]\ $
$dp[i][2] = 1 * dp[i - 1][0] + 1 * dp[i - 1][1] + 2 * dp[i - 1][2]\ $

これは明らかに次のように書ける。

$
\left(
\begin{array}{rrr}
dp[i][0] \\
dp[i][1] \\
dp[i][2] \\
\end{array}
\right) = \left(
\begin{array}{rrr}
1 & 0 & 1 \\
2 & 1 & 2 \\
1 & 1 & 2 \\
\end{array}
\right) \left(
\begin{array}{rrr}
dp[i - 1][0] \\
dp[i - 1][1] \\
dp[i - 1][2] \\
\end{array}
\right)
$

次に位置$\ i - 1\ $に印がついている場合を考えると、その位置では柵が置けないため、上の場合分けにおける柵を置かない場合のみを考えることで

$dp[i][0] = 1 * dp[i - 1][0] + 0 * dp[i - 1][1] + 0 * dp[i - 1][2]\ $
$dp[i][1] = 2 * dp[i - 1][0] + 1 * dp[i - 1][1] + 0 * dp[i - 1][2]\ $
$dp[i][2] = 1 * dp[i - 1][0] + 1 * dp[i - 1][1] + 1 * dp[i - 1][2]\ $

であることがわかるため、以下のようになる。

$
\left(
\begin{array}{rrr}
dp[i][0] \\
dp[i][1] \\
dp[i][2] \\
\end{array}
\right) = \left(
\begin{array}{rrr}
1 & 0 & 0 \\
2 & 1 & 0 \\
1 & 1 & 1 \\
\end{array}
\right) \left(
\begin{array}{rrr}
dp[i - 1][0] \\
dp[i - 1][1] \\
dp[i - 1][2] \\
\end{array}
\right)
$

よって、各印の間は上の行列の累乗を用いて計算し、印の位置で下の行列を1回かけるということを繰り返せば高速に答えを求めることができる。

実装
#include "bits/stdc++.h"
using namespace std;

const int MOD = 1000000007;

typedef long long Type;
typedef vector<vector<Type>> Matrix;
Matrix Mul(const Matrix &a, const Matrix &b) {
        assert(a[0].size() == b.size());
        Matrix c(a.size(), vector<Type> (b[0].size()));
        for (int i = 0; i < a.size(); i ++) {
                for (int k = 0; k < b.size(); k ++) {
                        for (int j = 0; j < b[0].size(); j ++) {
                                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
                        }
                }
        }
        return c;
}
Matrix Pow(Matrix a, long long n) {
        assert(a.size() == a[0].size());
        Matrix b(a.size(), vector<Type> (a.size()));
        for (int i = 0; i < a.size(); i ++) {
                b[i][i] = 1;
        }
        while (n > 0) {
                if (n & 1) b = Mul(b, a);
                a = Mul(a, a);
                n >>= 1;
        }
        return b;
}

int main() {
        int n, m, x;
        scanf("%d%d", &n, &m);
        Matrix a = {{1, 0, 0}, 
                    {2, 1, 0}, 
                    {1, 1, 1}};
        Matrix b = {{1, 0, 1},
                    {2, 1, 2},
                    {1, 1, 2}};
        Matrix ans = a;
        int prev = 1;
        while (m --) {
                scanf("%d", &x);
                ans = Mul(Pow(b, x - prev), ans);
                ans = Mul(a, ans);
                prev = x + 1;
        }
        ans = Mul(Pow(b, n - prev), ans);
        printf("%lld\n", ans[2][0]);
        return 0;
}

DDCC C. グラフいじり

DDCC 2017 本戦 C. グラフいじり

C: グラフいじり - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder

感想

dfsの計算量を間違えていた。$\ O(m(n + m))\ $。これは$\ O(n^4)\ $なので、$\ TLE\ $する。仕方がないので無理やり通した。

解法

まずはある有向グラフが与えられたときに、それが条件(どのサイクルの距離の総和も$\ 0\ $であること)を満たしているかどうかを判定することを考える。条件を満たしているグラフの任意の異なる2点$\ S, T\ $を見ると、$\ S\ $から$\ T\ $に向かう任意のパスの距離はすべて一定になっているはずである。なぜなら、もし2つのパスが存在してその距離がそれぞれ$\ d_1, d_2\ (d_1 \neq d_2)\ $となっているならば、条件より存在する$\ T\ $から$\ S\ $へのある共通のパスを用いてサイクルを2つ作ると、これらの少なくとも一方の総和は$\ 0\ $でないので矛盾する。また、この距離を$\ d\ $とすると、$\ T\ $から$\ S\ $へのパスの距離は$\ -d\ $となっているはずである。そして逆に任意の2点についてこの距離の条件が成り立てば、条件を満たすことがわかる。これは簡単なdfsで求めることができる。計算量は$\ O(n)\ $である(これは嘘で、本当は$\ O(n + m) = O(m) = O(n^2)\ $)。

さて、次に長さを変える辺を一つ固定し、この繋いでいる頂点を$\ S \ $ -> $\ T\ $、その長さを$\ x\ $と仮定する。すると、まず必要条件として、上の条件と同じようなことを考えることができるはずであり、あるサイクルに関して総和が$\ 0\ $になるようにするための$\ x\ $が一意に定まるはずである。これを決めてしまえば、上で述べた判定によって、全体が条件を満たすかを判定すればよい。

従って、これをすべての辺についてチェックすればよい。この操作は$\ O(m)\ $でできるので、全体の計算量は$\ O(nm)\ $となるので十分高速である(これは嘘で、本当は$\ O(n^4)\ $なので、間に合わない)。

よって間に合わないことがわかるが、せっかく書いたので通したい。辺を順番に見ている場合でもほとんど通っているので、辺をランダムにシャッフルし、前半の$\ X\ $%だけ試す方針をとることにする。これはstd::shuffleを使うなどして実装する。辺が少ないときはすべて見てよいとし、辺数が$\ 50000\ $を超えるときは$\ 60\ $%、辺数が$\ 75000\ $を超えるときは$\ 35\ $%をみて、条件を満たすものが見つかるまで探索し、なければ即終了するという実装にすると、5回投げたら3回通るくらいの精度(?)になった。

実装
#include &quot;bits/stdc++.h&quot;
using namespace std;

#define mp make_pair

static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

long long dist[303];
vector<pair<int, long long>> g[303];

struct edge {
        int a, b;
        long long cost;
};


void init() { for (int i = 0; i < 303; i ++) dist[i] = -INFL; }

bool check(int v, int from, int to, long long x, long long d) {
        dist[v] = d;
        for (auto e : g[v]) {
                int u = e.first, cost = e.second;
                if (from == v && to == u) {
                        assert(d == 0);
                        if (!check(u, from, to, x, d + x)) return false;
                } else if (dist[u] == -INFL) {
                        if (!check(u, from, to, x, d + cost)) return false;
                } else if (dist[u] != d + cost) { 
                        return false;
                }
        }
        return true;
}

long long get_x(int v, long long d) {
        dist[v] = d;
        for (auto e : g[v]) {
                int u =e.first, cost = e.second;
                if (dist[u] == -INFL) {
                        long long x = get_x(u, d + cost);
                        if (x != INFL) return x;
                } else if (dist[u] != d + cost) {
                        return d + cost - dist[u];
                }
        }
        return INFL;
}

int main() {
        int n, m;
        scanf(&quot;%d%d&quot;, &n, &m);
        vector<edge> es;
        for (int i = 0; i < m; i ++) {
                int a, b;
                long long c;
                scanf(&quot;%d%d%lld&quot;, &a, &b, &c);
                a --, b --;
                g[a].push_back(mp(b, c));
                es.push_back((edge) {a, b, c} );
        }

        //Randomly choose the edges
        random_device seed_gen;
        mt19937 engine(seed_gen());
        shuffle(es.begin(), es.end(), engine);

        for (int i = 0; i < m; i ++) {
                if (m > 50000) if (i > (m * 60) / 100) break;
                if (m > 75000) if (i > (m * 35) / 100) break;
                edge e = es[i];
                int v = e.a, u = e.b;
                long long cost = e.cost;
                init();
                dist[v] = 0;
                long long x = get_x(u, 0); 
                if (x == INFL) x = 0;
                init();
                bool ans = check(v, v, u, -x, 0);
                if (ans) return !puts(&quot;Yes&quot;);
        }
        return !puts(&quot;No&quot;);
}

Atcoder Grand Contest 013 E. Placing Squares

Atcoder Grand Contest 013 E. Placing Squares

E: Placing Squares - AtCoder Grand Contest 013 | AtCoder

感想

$\ O(n)\ $を高速化したかったけどできてない.....
想定解はまた今度考える。

解法

まず愚直に$\ DP\ $を書くと$\ O(n^2)\ $になる。この記事ではうまく高速化しないと通せない$\ O(n)\ $解法を説明する。印の処理は容易なので、省略する。

まず$\ dp_i = \sum_{k=0}^{i-1} dp_k * (i - k) ^ 2\ $という式を立てることができるのでこれを変形していく。

$\ dp_i = i^2 * \sum_{k=0}^{i-1} dp_k - 2i * \sum_{k=0}^{i-1} k * dp_k + \sum_{k=0}^{i-1} k^2 * dp_k\ $

$\ dp_i = i^2 * sum_{i-1} - 2 * i * sum2_{i-1} + sum3_{i-1}\ $とおくと

$\ sum_{i} = sum_{i-1} + dp_{i-1}\ $
$\ sum2_{i} = sum2_{i-1} + (i-1)*dp_{i-1}\ $
$\ sum3_{i} = sum3_{i-1} + (i-1)^2 * dp_{i-1}\ $

を用いて順番に計算していける。

ごちゃごちゃ書いたが、要するに総和を知りたいときに一つ前に使った総和そのものが使える典型パターンである。

よってこれは$\ O(n)\ $で計算できる。

さらにこれらは一つ前の情報しか必要としないので、すべて一つの変数を使いまわすことで空間計算量はマークの分の$\ O(n)\ $になる。

実装(5倍くらいTLE(>_<))
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() {
        int n, m, x;
        scanf(&quot;%d%d&quot;, &n, &m);
        vector<bool> marked(n + 1, false);
        for (int i = 0; i < m; i ++) { scanf(&quot;%d&quot;, &x); marked[x] = true; }
        long long ans = 1;
        long long sum = 1, sum2 = 0, sum3 = 0;
        long long j = 0;
        for (long long i = 1; i <= n; i ++) {
                j += i * 2 - 1; //j = i * i
                j %= MOD;
                if (marked[i]) ans = 0;
                else { 
                        ans = j * sum - 2 * i * sum2 + sum3;
                        ans %= MOD;
                        sum  +=     ans;
                        sum2 += i * ans;
                        sum3 += j * ans;
                        sum  %= MOD;
                        sum2 %= MOD;
                        sum3 %= MOD;
                }
        }
        printf(&quot;%lld\n&quot;, ((ans % MOD) + MOD) % MOD);
        return 0;
}

Atcoder Regular Contest 084 F. XorShift

Atcoder Regular Contest 084 F. XorShift

F: XorShift - AtCoder Regular Contest 084 | AtCoder

解法

基底とする数は与えられる$\ n\ $個の数だけとして考えて良い。これらを任意の個数使って、シフトさせたり$\ xor\ $をとったりして数を作る。

ここで$\ xor\ $をとるという操作は、$\ mod\ 2\ $で各桁の差(あるいは和)をとるという操作に読み替えることができる。さらにシフトの操作を加えると、除算の筆算のような操作を繰り返していけることがわかる。

結局これらの操作によって作ることができる数というのは、これらの$\ gcd\ $の倍数全体であり、逆にそれ以外の数は作れないことが言える。これは整数で考えるとわかりやすくて、例えば$\ \{18, 42, 66\}\ $という数から適当な加減を繰り返すことによって$\ gcd(18, 42, 66) = 6\ $の倍数はすべて作ることができるし、逆にそれ以外はどうやっても作れない。

よって$\ n\ $個の数の$\ gcd\ $を求め、$\ X\ $以下の$\ gcd\ $の倍数の個数を求めればそれが答えである。 これはなんか頑張るとできる。

bitsetvectorによる実装をどちらもした。bitsetの方が、$\ xor\ $の操作がわかりやすかったり、stringを経由しなくても数を扱えるという点で優れていると思うが、実質の長さを知りたいときや、大小比較をしたいときに少し不便だったり、慣れの問題だが先頭(左端)のインデックスが$\ size - 1\ $であるためバグる確率が高い感じがあった。

実装1(vectorによる)
#include "bits/stdc++.h"
using namespace std;

static const int MOD = 998244353;

vector<int> BitsetGcd(vector<int> s, vector<int> t) {
        int n = s.size(), m = t.size();
        if (n < m) return BitsetGcd(t, s);
        if (!m) return s;
        for (int i = 0; i < m; i ++) s[i] ^= t[i];
        int p = n;
        for (int i = 0; i < n; i ++) {
                if (s[i]) {
                        p = min(p, i);
                        break;
                }
        }
        vector<int> a(n - p);
        for (int i = 0; i < n - p; i ++) a[i] = s[p + i];
        return BitsetGcd(t, a);
}

long long ModPow(long long x, long long n, long long m) {
        long long res = 1;
        while (n > 0) {
                if (n & 1) res = res * x % m;
                x = x * x % m;
                n >>= 1;
        }
        return res;
}

int main() {
        int n;
        scanf("%d", &n);
        string x;
        cin >> x;
        vector<int> g;
        for (int i = 0; i < n; i ++) {
                string s;
                cin >> s;
                int k = s.size();
                vector<int> b(k);
                for (int i = 0; i < k; i ++) b[i] = s[i] - '0';
                g = BitsetGcd(g, b);
        }
        n = x.size();
        vector<int> c(n), d(n);
        for (int i = 0; i < n; i ++) c[i] = x[i] - '0';
        int m = g.size();
        int ans = 0;
        for (int i = 0; i + m <= n; i ++) {
                if (c[i]) ans = (ans + ModPow(2, n - m - i, MOD)) % MOD;
                if (c[i] == d[i]) continue;
                for (int j = 0; j < m; j ++) d[i + j] ^= g[j];
        }
        printf("%d\n", (ans + (d > c ? 0 : 1)) % MOD);
        return 0;
}
実装2(bitsetによる)
#include "bits/stdc++.h"
using namespace std;

static const int MOD = 998244353;

#define N 4040

int Len(const bitset<N> &a) {
        for (int res = N - 1; res >= 0; res --) {
                if (a[res]) return res + 1;
        }
        return 0;
}

bitset<N> gcd(bitset<N> s, bitset<N> t) {
        int n = Len(s), m = Len(t);
        if (n < m) return gcd(t, s);
        if (t.none()) return s;
        int d = n - m;
        bitset<N> u = t;
        u <<= d;
        s ^= u;
        return gcd(t, s);
}

long long ModPow(long long x, long long n, long long m) {
        long long res = 1;
        while (n > 0) {
                if (n & 1) res = res * x % m;
                x = x * x % m;
                n >>= 1;
        }
        return res;
}

int main() {
        int q;
        scanf("%d", &q);
        bitset<N> x;
        cin >> x;
        bitset<N> g;
        for (int i = 0; i < q; i ++) {
                bitset<N> s;
                cin >> s;
                g = gcd(g, s);
        }
        int n = Len(x);
        bitset<N> d(0);
        int m = Len(g);
        int ans = 0;
        for (int i = n - 1; i >= m - 1; i --) {
                if (x[i]) ans = (ans + ModPow(2, i - m + 1, MOD)) % MOD;
                if (x[i] == d[i]) continue;
                d ^= (g << i - m + 1);
        }
        bool ok = true;
        for (int i = n - 1; i >= 0; i --) {
                if (d[i] < x[i]) break;
                if (d[i] > x[i]) ok = false;
        }
        printf("%d\n", (ans + ok) % MOD);
        return 0;
}