A. Guess the DNA!
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://mirror.codeforces.com/contest/1981/submission/263736407
B. Bit GCD
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://mirror.codeforces.com/contest/1981/submission/263736978
C. Permu Shift
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://mirror.codeforces.com/contest/1981/submission/263738042
D. Biased Coin
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:
The condition for $$$dp[i][j]$$$ is nonzero is $$$\lceil{j/2}\rceil-25\leq i \leq\lfloor{j/2}\rfloor+25$$$.
So by shifting the positions in the dp array
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 $$$\lceil{j/2}\rceil-25$$$ and shift2 to $$$\lceil{(j-1)/2}\rceil-25$$$. Let's modify the dp formula to use them. $$$dp[heads-shift1][n]\equiv(hp(heads-1,n-1)*dp[head-1-shift2][n-1])$$$ $$$+((1-hp(heads,n-1))*dp[heads-shift2][n-1]))$$$ for heads satisfying $$$\lceil{j/2}\rceil-25\leq heads \leq\lfloor{j/2}\rfloor+25$$$.
, we get a $$$O(n)$$$ solution.
Why 828542813? $$$828542813*100\equiv 1\ (mod\ 998244353)$$$.
Code: https://mirror.codeforces.com/contest/1981/submission/263741468