## A. Guess the DNA!

**Solution**

We will describe an approach that solves this problem in at most $$$3*n+3$$$ queries. The first 3 queries are for getting the counts of A,T,G,C.

We can search for 2 characters at once:

Assume that the queried string is "yyyyyyyy...yyyyxyyyyyyy...yy" (x and y are 2 different characters)

If the similarity count has increased by 1 from "yyyyyyyyyyyyyyyy...y" then the character is x, else, if it has decreased by 1, then it is y.

We search for the first 2 characters with the most count, which will take $$$2*n$$$ queries.

Then we search for the last 2 characters, which will take $$$n$$$ queries at most (since at least $$$n$$$ characters have been searched in the string before).

Complexity: $$$O(n^2)$$$.

Code: https://codeforces.com/contest/1981/submission/263736407

## B. Bit GCD

**Solution**

It is easy to observe that the gcd is <= min, and one popcount operation reduces the min to <= $$$log(a)$$$.

So we can just brute force all gcds from 2 to log(a), note that each element takes $$$O(log^{*}(a))$$$ iterations to be reduced to 1.

Complexity: $$$O(n*log(a)*log^{*}(a))$$$.

Code: https://codeforces.com/contest/1981/submission/263736978

## C. Permu Shift

**Solution**

One can see that pressing the button $$$k$$$ times applies $$$2^k$$$ times the original permutation on $$$[1,2,3,...,n]$$$.

To find how many times the permutation need to be applied on to go back to $$$[1,2,3,...,n]$$$, one can just use any solution of 1249B2 - Books Exchange (hard version) with the note that it is the LCM of the cycles.

To check for the power of $$$2$$$ fast one should use GCC builtins (that can do it in $$$O(1)$$$ instead of $$$O(log(n))$$$).

Complexity: $$$O(n)$$$.

Code: https://codeforces.com/contest/1981/submission/263738042

## D. Biased Coin

**Solution**

The probability of rolling a head after rolling $$$k$$$ heads and $$$n$$$ coins is $$$(50+n-2*k)\%$$$.

Let's use this fact to build a dp solution.

Let $$$hp(k,n)$$$ being $$$(50+n-2*k)*828542813$$$ if $$$0\leq k \leq n$$$, else 0. (you will see why later).

$$$dp[heads][n]\equiv(hp(heads-1,n-1)*dp[heads-1][n-1])+((1-hp(heads,n-1))*dp[heads][n-1]))$$$ $$$(mod\ 998244353)$$$.

with $$$dp[0][0]=1$$$.

But: this solution is $$$O(n^2)$$$!

There is an observation that is needed to solve the problem.

It is:

**Observation (unproven)**

The condition for $$$dp[i][j]$$$ to be nonzero is $$$max(0,\lceil{n/2}\rceil-25)\leq i \leq min(n,\lfloor{n/2}\rfloor+25)$$$.

So by shifting the positions in the dp array,

**How?**

Let's create two new variables $$$shift1,\ shift2$$$ with $$$shift1$$$ being the shift on $$$dp[n]$$$ ($$$dp[heads][n]$$$ now turns to $$$dp[heads-shift1][n]$$$) and $$$shift2$$$ is the same for $$$dp[n-1]$$$.

Set $$$shift1$$$ to $$$max(0,\lceil{n/2}\rceil-25)$$$ and $$$shift2$$$ to $$$max(0,\lceil{(n-1)/2}\rceil-25)$$$. Let's modify the dp formula to use them. Now the dp formula is:

$$$dp[heads-shift1][n]\equiv(hp(heads-1,n-1)*dp[heads-1-shift2][n-1])$$$ $$$+((1-hp(heads,n-1))*dp[heads-shift2][n-1]))\ (mod\ 998244353)$$$ for $$$heads$$$ satisfying $$$shift1 \leq heads \leq min(n,\lfloor{n/2}\rfloor+25)$$$.

Since there are only a maximum of 51 values of $$$dp[heads][n]$$$ that is nonzero, we get a $$$O(n)$$$ solution.

Why 828542813? $$$828542813*100\equiv 1\ (mod\ 998244353)$$$.

Code: https://codeforces.com/contest/1981/submission/263741468