Can you solve the case $$$n = 1$$$ using maximum $$$6$$$ query

If you can solve $$$n = 1$$$ using maximum $$$6$$$ query, can you solve $$$n \neq 1$$$ using maximum $$$5 * n + 1$$$ query

And we can see that $$$5n+1 \leq 6n$$$, so that this will not get Wrong Answer.

Try to split the entire ADN to $$$n$$$ part, and solve each part.

With $$$n = 1$$$, you can do like that: Ask 4 query "AA", "CC", "TT", "GG". If one of four query, the interactor said "Correct!", then you can immediately stop the program. Else, we need to find two query in four query you ask before such that the answer of this is one. Assume that it is "AA" and "TT". Then you ask "AT". If the answer not "AT", it must be "TA"(You can easily see that).

With $$$n \neq 1$$$, you need to split it to $$$n$$$ pairs and handle each pair seperately. You can do that following thing to get the value of pair $$$k$$$: You can ask four query "AA..AA($$$2k-2$$$ charcater "A")AAAA...AA(number of "A" left to make string length enough $$$2*n$$$)", "AA..AATTAA..AA", "AA..AACCAA..AA", "AA..AAGGAA..AA". After that we have 2 case need to handle:

• In four query, if we can find a query that have an answer equal to the smallest answer among all query plus 2, then the answer in pair $$$k$$$ is equal to the answer at pair $$$k$$$ in this query. Example, if "AA..AACCAA..AA" is equal to the smallest in each other plus 2, then the pair $$$k$$$ is equal to "CC".

• If not, we need to find two query that have an answer equal to smallest answer among all query plus 1. Example, if is AA..AACCAA..AA and "AA..AATTAA..AA", then you need to ask one more query "AA..AACTAA..AA". If the answer of that query equal to the smallest among first four query, then pair $$$k$$$ equal to "TC", else it equal to "CT".

At the end, we just need to merge the result of $$$n$$$ pair to one string with length $$$2*n$$$ and print that string(after that you don't need to handle the input anymore, because interactor will say "Correct!", of course).

Can you prove that this is only need $$$5n + 1$$$ query?

import sys,functools,copy
def query(inp):
    print(inp)
    sys.stdout.flush()
    m = input()
    if m.isdigit():
        return int(m)
    else:
        sys.exit() #Because we're guessed correct :)
n = int(input())
correct_char = ["AA"]*n
for x in range(n):
    a = query("AA"*x+"AA"+"AA"*(n-x-1))
    t = query("AA"*x+"TT"+"AA"*(n-x-1))
    c = query("AA"*x+"CC"+"AA"*(n-x-1))
    g = query("AA"*x+"GG"+"AA"*(n-x-1))
    if max([a,t,c,g])-min([a,t,c,g]) == 2:
        #Case 1 mentioned before
        if max([a,t,c,g]) == a:
            correct_char[x] = "AA"
        elif max([a,t,c,g]) == t:
            correct_char[x] = "TT"
        elif max([a,t,c,g]) == c:
            correct_char[x] = "CC"
        elif max([a,t,c,g]) == g:
            correct_char[x] = "GG"
    else:
        #Case 2
        i = ""
        if a == max([a,t,c,g]):i+="A"
        if t == max([a,t,c,g]):i+="T"
        if c == max([a,t,c,g]):i+="C"
        if g == max([a,t,c,g]):i+="G"
        nor = query("AA"*x+i+"AA"*(n-x-1))
        if nor != min([a,t,c,g]):
            correct_char[x]=copy.deepcopy(i)
        else:
            correct_char[x]=copy.deepcopy(i[::-1])
query("".join(correct_char))

$$$popcount(x) \le \log x +1$$$

$$$\gcd(x, y) \le \min(x, y)$$$

From the two hints above, we can see that if we apply the operation even just once, GCD of the array is gonna drop to about $$$\log \max(a_i)$$$ or less, which is about 20. Meanwhile, in order for a number to reach 1 we need to apply at most 5 operations to that number.

We first calculate GCD of the original array. If that GCD is more than 20, it's the answer. Else, we brute force through every GCD value less than 21. For every index we check if the value can be changed to a number divisible by that GCD value and take the maximum GCD possible.

Time complexity: $$$O(5 n \log max(a_i))$$$

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        long long a[n];
        for (long long i = 0; i < n; i++) cin >> a[i];
        long long g = 0;
        for (long long i = 0; i < n; i++) g =  __gcd(g, a[i]);
        if (g>20) cout << g << endl;
        else
        {
            vector<long long> v[n];
            for (long long i = 0; i < n; i++) 
            {
                long long tmp = a[i];
                while (tmp!=1)
                {
                    v[i].push_back(tmp);
                    tmp = __builtin_popcount(tmp);
                }
                v[i].push_back(1);
            }
            for (long long i = 20; i >= 1; i--)
            {
                long long av = 1;
                for (long long j = 0; j < n; j++)
                {
                    long long check = 0;
                    for (auto k: v[j])
                    {
                        if (k%i==0) 
                        {
                            check = 1;
                            break;
                        }
                    }
                    if (check==0)
                    {
                        av = 0;
                        break;
                    }
                }
                if (av==1) 
                {
                    cout << i << endl;
                    break;
                }
            }
        }
    }
}

Draw the graph containing edges from $$$i$$$ to $$$p_i$$$ for every $$$(1 \le i \le n)$$$

What does the graph of the sorted permutation looks like? How does a cycle changes after an operation?

Draw the graph containing edges from $$$i$$$ to $$$p_i$$$ for every $$$(1 \le i \le n)$$$. The graph will form cycles.

Doing an operation is just deleting the edge connecting a node $$$i$$$ to $$$p_i$$$ and connecting it to a node two steps after it in a cycle. After an operation, the cycles with even size each breaks into two cycles each with half the original size. The cycles with odd size stay the same, just different order.

Without losing generality, set the label of all nodes in the cycle to numbers from 1 to its size in order. If the size is even, all the odd nodes form a new cycle and all the even nodes form a new cycle. But if the size is odd, the cycle will go through every node before it returns to node 1. (Try to draw and see this for yourself)

In the sorted permutation there exist n cycles of size 1. Therefore we must break all cycles down to size 1. So if all cycles have size in the form of $$$2^i (0 \le i)$$$ then the answer is YES, else the answer is NO.

To find the size of cycles we can use graph algorithms like DFS/BFS.

Time complexity: $$$O(n)$$$

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        long long a[n], vis[n];
        for (long long i = 0; i < n; i++) 
        {
            cin >> a[i];
            a[i]--;
            vis[i] = 0;
        }
        vector<long long> v;
        for (long long i = 0; i < n; i++)
        {
            if (vis[i]==1) continue;
            vis[i] = 1;
            long long cnt = 0, cur = i;
            //cnt keep track of cycle size
            //the while loop goes through the cycle
            while (1)
            {
                cur = a[cur];
                vis[cur] = 1;
                cnt++;
                if (cur==i) break;
            }
            v.push_back(cnt);
        }
        long long flag = 0;
        //check 2^i
        for (auto i: v)
        {
            long long cur = 1;
            while (cur<i) cur *= 2;
            if (cur!=i) flag = 1;
        }
        if (flag==0) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Since the probability of landing on a head can't drop below 0% or above 100%, if $$$k>n$$$ or $$$k$$$ is not in the range $$$[\lceil n/2 \rceil -25, \lfloor n/2 \rfloor +25]$$$, the answer is 0.

$$$dp[i][j]$$$ is the probability when the coin was flipped i times and the current head chance is j%. $$$dp[i][j]$$$ can be updated through either a head or a tail, thus:

$$$dp[i][j] = dp[i-1][j-1] \frac{100-(j-1)}{100} + dp[i-1][j+1] \frac{j+1}{100}$$$

The answer is $$$dp[n][50+(n-k)-k]$$$

To handle modulo with division, $$$a^{-1}$$$ is the same as $$$a^{mod-2}$$$ here. Refer to Fermat's little theorem.

Time complexity: $$$O(100n)$$$

#include <bits/stdc++.h>
using namespace std;
long long dp[300005][105];
long long p[105];
const long long mod = 998244353;
long long pw (long long a, long long b) 
{
    a %= mod;
    long long res = 1;
    while (b > 0) 
    {
        if (b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
//precalculating inverse modulo of 100
const long long div100 = pw(100, mod-2)%mod;

int main()
{
    //precalculating every percent's inverse modulo
    for (long long i = 0; i <= 100; i++) p[i] = i*div100%mod;
    //dp
    dp[0][50] = 1;
    for (long long i = 1; i <= 300000; i++)
    {
        for (long long j = 0; j <= 100; j++)
        {
            long long upd = 0;
            if (j<100) upd = (upd+dp[i-1][j+1]*p[j+1])%mod;
            if (j>0) upd = (upd+dp[i-1][j-1]*p[101-j])%mod;
            dp[i][j] = upd;
        }
    }
    
    long long t, n, k;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        if (abs(n-2*k)>50) cout << 0 << endl;
        else cout << dp[n][50+n-2*k] << endl;
    }
}

How to make them don't have any commmon subsenquence? Just make them don't have any common letter

How to make it don't have any common letter? Just swap all common letter to one of two string, $$$a$$$ or $$$b$$$

Try a Dynamic Programming solution.

First, you need to prepare two array $$$n$$$ and $$$m$$$, each have length of 52, mean number of letter of type $$$i$$$(in our solution, $$$i$$$ get value from 1 to 26 when letter get value from "a" to "z", and 27 to 52 when letter get value from "A" to "Z")

You can thing about swap operator in diffrent side: If we swap letter at position $$$a_i$$$ and $$$b_j$$$, we just insert $$$b_j$$$ between $$$a_i$$$ and $$$a_{i+1}$$$, then delete $$$a_i$$$. We do the same thing in other string

Now, we just need to DP(or Memoization). We say that $$$f(n,m)$$$ is minimum number of operator to string $$$a$$$ in one of two type(delete/insert) which letter type from $$$1$$$ to $$$n - 1$$$, when diffrent between length of string $$$a$$$ and current length is is $$$n$$$. (Intially, $$$f(0,0) = 0$$$ and $$$f(0,i)=- \infty$$$). We can see that $$$f(i,j) = \min( f(i - 1, j + m[i]) + m[i], f(i - 1, j - n[i]) + n[i])$$$(delete all letter in same type or insert all letter of same type). The number of operator is equal to $$$\frac{f(53,0)}{2}$$$.

After that, you just need to trace to find which letter will be inserted to $$$a$$$ and to $$$b$$$. Then you gat a list $$$g$$$ and $$$h$$$, position of letter that will be insert to $$$a$$$ from $$$b$$$ and position of letter that will be insert to $$$b$$$ from $$$a$$$. The last thing is easy: Just swap $$$a_{h_i}$$$ and $$$b_{g_i}$$$ for $$$i$$$ from 1 to $$$|A|$$$.

import functools,sys,io,os
#Fast-IO for python
print=sys.stdout.write
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():
    a = input().decode().rstrip("\r\n")
    b = input().decode().rstrip("\r\n")
    $f have equal mission with n, and s have equal mission with m
    f = [0]*52
    s = [0]*52
    
    for x in a:
        if x.islower():
            f[ord(x)-ord('a')+26]+=1
        else:
            f[ord(x)-ord('A')]+=1

    for x in b:
        if x.islower():
            s[ord(x)-ord('a')+26]+=1
        else:
            s[ord(x)-ord('A')]+=1

    #We use memoization instead of DP
    @functools.lru_cache(maxsize=None)
    def mini(pos,val):
        if pos==-1:
            if val==0:
                return 0
            else:
                return float('inf')
        else:
            if mini(pos-1,val+f[pos])+f[pos] < mini(pos-1,val-s[pos])+s[pos]:
                return mini(pos-1,val+f[pos])+f[pos]
            else:
                return mini(pos-1,val-s[pos])+s[pos]

    #Trace part. We just need to use one array, since letter was inserted to a can't be insert to b
    def qrtt():
        pos,val=51,0
        mvement=[]
        while pos>=0:
            if mini(pos-1,val+f[pos])+f[pos]<mini(pos-1,val-s[pos])+s[pos]:
                val+=f[pos]
                mvement.append(-pos-1)
            else:
                val-=s[pos]
                mvement.append(pos+1)
            pos-=1
        return mvement

    t=mini(51,0)
    print(str(t//2)+'\n')
    #ad have same mission with h, and bd with g
    ad = []
    bd = []
    for x in qrtt():
        if abs(x)!=x:
            if abs(x)>26:
                for y in range(len(a)):
                    if a[y]==chr(ord('a')+(abs(x)-26)-1):
                         ad.append(y)
            else:
                for y in range(len(a)):
                    if a[y]==chr(ord('A')+abs(x)-1):
                        ad.append(y)
        else:
            if abs(x)>26:
                for y in range(len(b)):
                    if b[y]==chr(ord('a')+(abs(x)-26)-1):
                        bd.append(y)
            else:
                for y in range(len(b)):
                    if b[y]==chr(ord('A')+abs(x)-1):
                        bd.append(y)

    #No sort still OK :) but we like to sort
    ad.sort()
    bd.sort()

    for x in range(t//2):
        print(str(ad[x]+1)+" "+str(bd[x]+1)+'\n')
main()

Try to generalize $$$(x) \oplus (x+1)$$$.

The value of $$$(x) \oplus (x+1)$$$ is: let $$$pos$$$ the index of the first '0' bit of x counting 1-indexed from the right. The value is $$$2^{pos} - 1$$$

For example: let a number's binary representation be $$$X0111_2$$$, after add 1 it will become $$$X1000_2$$$, xor = $$$1111_2$$$ = $$$2^4 -1$$$.

We go through every index from n to 1 and let it be the index of the first '0', then counts how many ways we can set the prefix:

• if there is no '0' after $$$pos$$$: $$$ans = ans + (2^{pos} -1)*((n \ggg pos)+1)$$$
• else: $$$ans = ans + (2^{pos} -1)*(n \ggg pos)$$$

Like problem D, inverse modulo is needed in this problem to divide by 2.

Time complexity: $$$O(n)$$$

#include<bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long pw (long long a, long long b) 
{
    a %= mod;
    long long res = 1;
    while (b > 0) 
    {
        if (b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
//precalculating inverse modulo of 2
const long long inv2 = pw(2ll, mod-2)%mod;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long t, n;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        n = s.length()+1;
        s = '0'+s;
        long long check = 0, cur = 0, p = 1, ans = 0;
        for (long long i = n-1; i >= 0; i--)
        {
            if (s[i]=='1') cur = (cur+p)%mod;
            p = p*2%mod;
        }
        p = 1;
        //p is 2^pos
        //cur is the value of the prefix
        //check is checking if after pos are all '1's
        //ans is the answer
        for (long long i = n-1; i >= 0; i--)
        {
            p = p*2%mod;
            if (s[i]=='0') cur = cur*inv2%mod;
            else cur = (cur+mod-1)*inv2%mod;
            if (s[i]=='1'||check==0) ans = (ans+(cur+1)*(p+mod-1))%mod;
            else ans = (ans+cur*(p+mod-1))%mod;
            if (s[i]=='0') check = 1;
        }
        cout << ans << endl;
    }
}

Set the three sides be $$$n, x, y$$$. Try to count the number of right triangles in the two cases: $$$n^2 = x^2 + y^2$$$ and $$$n^2 = x^2 - y^2$$$.

First factor n^2, put the factors and their count into something like $$$map$$$ C++ or $$$dict$$$ in py.

Case 1: $$$n^2 = x^2 - y^2$$$

$$$\Rightarrow n^2 = (x-y)(x+y)$$$

Let $$$a = x-y$$$ and $$$b = x+y$$$, we find the number of ways to split $$$n^2$$$ into two positive integers $$$a, b$$$ such that:

• $$$a * b = n^2$$$
• $$$a < b$$$
• $$$a \equiv b (\mod 2)$$$

Basically, it's the number of divisors $$$d$$$ of $$$n^2$$$ such that $$$d < n$$$ and $$$n^2/d$$$ and $$$d$$$ have the same parity. With the factors calculated, we can go through every factor and update our answer (Read more here), except for the factor 2 which is special and needed to be calculated alone.

Case 2: $$$n^2 = x^2 + y^2$$$

We have Jacobi's two square theorem.

Applying the formula, the number of ways to represent $$$n^2$$$ as sum of two squares is $$$4*(d_1(n^2) - d_3(n^2))$$$. However this theorem also include cases of zero and negative integers. There are 4 cases of zeroes: {0, n}, {n, 0}, {-n, 0}, {0, -n}, each normal cases created 8 copies: {a, b}, {a, -b}, {-a, b}, {-a, -b}, {b, a}, {b, -a}, {-b, a}, {-b, -a}.

So the answer in this case is $$$(4*d_1(n^2) - 4*d_3(n^2) - 4)/8$$$

The number of divisors congruent to 1 modulo 4 and 3 modulo 4 can be calculated like Case 1.

Time complexity: $$$O(\sqrt{n})$$$, because the calculation step take $$$~\log n$$$ which is not much time.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    long long t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        map<long long, long long> fact;
        long long cur = 2, tmp = n;
        //factorizing n^2
        while (tmp!=1 && cur <= (long long) sqrtl(n))
        {
            while (tmp%cur==0)
            {
                fact[cur]+=2;
                tmp /= cur;
            }
            cur++;
        }
        //Case 1
        if (tmp!=1) fact[tmp]+=2;
        if (fact[2]>0) cur = fact[2]-1;
        else cur = 1;
        for (auto i: fact)
        {
            if (i.first==2) continue;
            cur *= i.second+1;
        }
        cur /= 2;
        //Case 2
        long long cnt[4];
        cnt[1] = 1;
        cnt[3] = 0;
        for (auto i: fact)
        {
            if (i.first==2) continue;
            long long a[4];
            a[1] = a[3] = 0;
            for (long long j = 1; j <= i.second; j++)
            {
                if (j%2==1) a[1*i.first%4] += cnt[1];
                else a[1ll*i.first%4*i.first%4] += cnt[1];
                if (j%2==1) a[3*i.first%4] += cnt[3];
                else a[3ll*i.first%4*i.first%4] += cnt[3];
            }
            cnt[1] += a[1];
            cnt[3] += a[3];
        }
        cout << cur+max(0ll, (4*(cnt[1]-cnt[3])-4)/8ll) << endl;
    }
}