ANDOR2 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Stars and bars

PROBLEM:

You’re given a binary string A.
In one move you can:

  • Choose an index i (1 \le i \lt N), and
  • Replace both A_i and A_{i+1} by either A_i\ \mid\ A_{i+1} or A_i\ \&\ A_{i+1}.

Count the number of binary strings that can be reached by performing this operation a finite number of times.

EXPLANATION:

From the easier version of the problem, where we had to check if a given string was reachable, we already know that A can reach B if and only if:

  • ct_A \gt ct_B, or
  • ct_A = ct_B and A_1 = B_1.

Here, ct_A denotes the number of maximal blocks of equal characters in A, and ct_B is the same thing but for B instead.

We’ll use this characterization to count reachable strings.

Let’s fix the value of ct_B, i.e. the number of blocks in the target string, and then try to count reachable strings.
Suppose we want ct_B = K.

There are two cases: ct_A \gt K and ct_A = K.

First, we deal with ct_A \gt K.
In this case, we saw that any string is reachable.
So, we simply need to count the number of binary strings with exactly K blocks.

This can be done as follows:

  • First, we form the blocks.
    We require K blocks, and each of them should be non-empty.
  • This is equivalent to choosing K positive integers that sum up to N.
    The i-th integer here is the length of the i-th block.
  • The number of ways of doing this is given by stars-and-bars, and equals \binom{N-1}{K - 1}.
  • Once the block lengths are decided, we need to assign values to the blocks.
    However, note that there are only two ways to assign values: once we assign 0 or 1 to the first block, the values of all other blocks are fixed since values must alternate between blocks.

So, there are exactly 2\cdot \binom{N-1}{K-1} binary strings with K blocks.
For K \lt ct_A, this is the value we add to the answer.

For K = ct_A, the situation is slightly different because we have the additional condition of A_1 = B_1.
However, it’s easy to see that this doesn’t change much: there are still \binom{N-1}{K-1} ways to form the segments, and the only difference is that there’s only one way to assign values instead of 2.
So, in this case we simply add \binom{N-1}{K-1} to the answer.

Thus, the final answer is

\left(\sum_{K=1}^{ct_A - 1} 2\cdot \binom{N-1}{K-1}\right) + \binom{N-1}{ct_A-1}

Binomial coefficients can be computed in constant time after some precomputation, so this is just \mathcal{O}(N) overall.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    const int maxn = 200005;
    const int mod = 998244353;
    auto mod_pow = [&] (int a, int n) {
        int r = 1;
        while (n) {
            if (n & 1) r = (1ll * r * a) % mod;
            a = (1ll * a * a) % mod;
            n /= 2;
        }
        return r;
    };
    vector<int> fac(maxn, 1);
    for (int i = 1; i < maxn; ++i) fac[i] = (1ll * i * fac[i-1]) % mod;
    auto inv = fac;
    for (auto &x : inv) x = mod_pow(x, mod-2);
    auto C = [&] (int n, int r) {
        if (n < r or r < 0) return 0;
        int res = (1ll * fac[n] * inv[r]) % mod;
        return int((1ll * res * inv[n-r]) % mod);
    };

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string a; cin >> a;

        int ablk = 1;
        for (int i = 1; i < n; ++i) {
            ablk += a[i] != a[i-1];
        }

        int ans = 0;
        for (int x = 1; x < ablk; ++x) {
            ans = (ans + C(n-1, x-1) * 2ll) % mod;
        }
        ans += C(n-1, ablk - 1);
        cout << ans%mod << '\n';
    }
}
1 Like