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.me/contest/1981/submission/263736407

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.me/contest/1981/submission/263736978

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.me/contest/1981/submission/263738042

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$$$ (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:

So by shifting the positions in the dp array

, we get a $$$O(n)$$$ solution.

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

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