We will solve the problem recursively, reducing the problem by at least half at each step. If $$$k<\frac{n}{2}$$$, we can see that the answer would be $$$2k$$$. Otherwise, we have removed all the even positions. The odd positions can be renamed from $$$1,2,\dots,\frac{n}{2}$$$ and we can recursively find the solution for it. And then we can re-map back to our original $$$n$$$ by multiplying by $$$2$$$ and subtracting $$$1$$$.
Time complexity is $$$O(logn)$$$.

ll f(ll n,ll k)
{
    if(n==1) return 1;
    if(k<=(n+1)/2) 
    {
        if(2*k>n) return (2*k)%n;
        else return 2*k;
    }
    ll temp=f(n/2,k-(n+1)/2);
    if(n%2==1) return 2*temp+1;
    return 2*temp-1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        ll n,k;
        cin>>n>>k;
        cout<<f(n,k)<<"\n";
    }
}

We will solve this recusively. If we want to find $$$a^x$$$, we can do that by splitting into $$$a^{\frac{x}{2}}.a^{\frac{x}{2}}$$$ if $$$x$$$ is even, or $$$a^{\frac{x-1}{2}}*a^{\frac{x-1}{2}}*a$$$ if $$$x$$$ is odd. Complexity is $$$O(n*log(max(b))$$$.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        cout<<POW(a,b)<<"\n";
    }
}

We will use fermat theorem for this. $$$a^{p-1} \equiv 1$$$ mod $$$p$$$. So using the above, we will find $$$b^c$$$ mod $$$(p-1)$$$ and then $$$a^{b^c}$$$ mod $$$p$$$, where $$$p=1e9+7$$$.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b, ll mod)
{
    if(b==0) return 1;
    if(b==1) return a%mod;
    ll temp=POW(a,b/2,mod);
    if(b%2==0) return (temp*temp)%mod;
    else return (((temp*temp)%mod)*a)%mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b,c;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        ll pw=POW(b,c,MOD-1);
        cout<<POW(a,pw,MOD)<<"\n";
    }
}

For each number $$$i$$$ from $$$1$$$ to $$$1000000$$$, we increase the count of divisor of multiple of $$$i$$$. And then answer the queries in $$$O(1)$$$. Time complexity is $$$O(nlogn)$$$.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll d[1000005]={};
    for(int i=1;i<1000005;i++)
    {
        for(int j=i;j<1000005;j+=i)
        {
            d[j]++;
        }
    }
    ll n,x;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        cout<<d[x]<<"\n";
    }
}

We have to basically find the largest divisor such that it divides atleast 2 numbers in the array $$$x$$$. So we iterate from the max possible answer i.e. $$$1e6$$$ to $$$1$$$, and increase the divisor count if the number is present in array. Time complexity is $$$O(nlogn)$$$

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n];
    ll cnt[1000001]={};
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        cnt[x[i]]++;
    }
    for(int i=1000000;i>=1;i--)
    {
        ll d=0;
        for(int j=i;j<=1000000;j+=i) d+=cnt[j];
        if(d>=2)
        {
            cout<<i;
            return 0;
        }
    }
}

For each divisor $$$i$$$, the number of times it occurs from $$$1$$$ to $$$n$$$ is $$$\lfloor \frac{n}{i} \rfloor$$$. Thus the sum to be calculated is equivalent to $$$\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor i$$$.
For this to be computed in $$$O(\sqrt{n})$$$, we observe that there are only $$$\sqrt{n}$$$ order of distinct values of $$$\lfloor \frac{n}{i} \rfloor$$$.
We divide our answers into 2 parts-
For the first part, $$$i \leq \sqrt{n}$$$, we will simply find the sum of terms for $$$1$$$ to $$$\sqrt{n}$$$. This can be done in $$$O(\sqrt{n})$$$.
For the second part, $$$\sqrt{n} < i \leq n$$$. Though this interval is of order of $$$O(n)$$$, here we notice that $$$\lfloor \frac{n}{i} \rfloor$$$ takes values only from $$$1$$$ to $$$\sqrt{n}$$$. So we will find points where value of $$$\lfloor \frac{n}{i} \rfloor$$$ changes by maintaining left and right counters and use the AP sum to compute the answer.
See my code for further clarity. (Inverse of $$$2$$$ denotes division by $$$2$$$ when dealing in modulo)
PS. A mistake I made, remember if you are maintaining intervals l and r, they can be $$$>1e9$$$, so take their modulo too.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll ans=0;
    for(ll i=1;i*i<=n;i++)
    {
        ans+=((n/i)*i)%MOD;
        ans%=MOD;
    }
    ll l=(ll)sqrt(n);
    for(ll i=sqrt(n);i>=1;i--)
    {
        ll r=n/i;
        ll sum=0;
        sum+=((((r%MOD)*((r+1)%MOD))%MOD)*inverse(2))%MOD;
        sum%=MOD;
        sum-=((((l%MOD)*((l+1)%MOD))%MOD)*inverse(2))%MOD;
        sum=(sum+MOD)%MOD;
        sum=(sum*i)%MOD;
        l=r;
        ans=(ans+sum)%MOD;
        //cout<<sum<<" ";
    }
    cout<<ans;
}

Number is given to us of the form $$$x_1^{k_1} \times \dots \times x_n^{k_n}$$$.
Number of divisors is $$$(k_1+1) \times \dots \times (k_n+1)$$$.
Sum of divisors is $$$(\frac{x_1^{k_1+1}-1}{x_1-1}) \times \cdots \times (\frac{x_n^{k_n+1}-1}{x_n-1})$$$.
Product of divisors is $$$num^{\frac{d(num)}{2}}$$$, where num is the number given (in form of primes) and $$$d(num)$$$ is the number of divisors. We have to take care to take the exponent mod $$$(p-1)$$$ and have to carefully divide the exponent by $$$2$$$.

const int MOD=1000000007; 
const int MOD1=1000000006;
long long int inverse(long long int i, long long int mod){
    if(i==1) return 1;
    return (mod - ((mod/i)*inverse(mod%i,mod))%mod+mod)%mod;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n],k[n];
    for(int i=0;i<n;i++)
    {
        cin>>x[i]>>k[i];
    }
    ll num=1;
    for(int i=0;i<n;i++)
    {
        num*=(k[i]+1)%MOD;
        num%=MOD;
    }
    ll sum=1;
    for(int i=0;i<n;i++)
    {
        ll temp=(POW(x[i],k[i]+1)+MOD-1)%MOD;
        temp*=inverse(x[i]-1,MOD);
        temp%=MOD;
        sum*=temp;
        sum%=MOD;
    }
    ll prod,num1=1;
    ll flag=0;
    for(int i=0;i<n;i++)
    {
        if(k[i]%2==1 && flag==0)
        {
            num1*=((k[i]+1)/2);
            num1%=MOD1;
            flag=1;
        }
        else
        {
            num1*=(k[i]+1)%MOD1;
            num1%=MOD1;
        }
    }
    if(flag==0)
    {
        for(int i=0;i<n;i++)
        {
            k[i]/=2;
        }
    }
    ll number=1;
    for(int i=0;i<n;i++)
    {
        number*=POW(x[i],k[i]);
        number%=MOD;
    }
    prod=POW(number,num1);
    cout<<num<<" "<<sum<<" "<<prod;
}

We will be using Inclusion-Exclusion principle, considering all subsets of given prime numbers. The count of numbers divisible by the subset of primes would be $$$\frac{n}{prod}$$$, where $$$prod$$$ is the product of the subset of primes. The sign would be positive if the size of subset is odd, and negative otherwise.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll a[k];
    for(int i=0;i<k;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    for(int i=0;i<(1ll<<k);i++)
    {
        vll v;
        for(int j=0;j<k;j++)
        {
            if((i&(1<<j))!=0)
            {
                v.PB(a[j]);
            }
        }
        ll prod=1;
        for(int j=0;j<v.size();j++)
        {
            if(prod>n/v[j])
            {
                prod=n+1;
                break;
            }
            prod*=v[j];
        }
        if(v.size()%2==0) ans-=n/prod;
        else ans+=n/prod;
    }
    ans+=n;
    cout<<ans;
}

We will be using Mobius function $$$\mu(k)$$$ for it. You can read about it here — https://en.wikipedia.org/wiki/M%C3%B6bius_function.
The answer to the problem is $$$\sum_{k=1}^{max(x[i])} \mu(k) {d(k) \choose 2}$$$. Here $$$d(k)$$$ is the number of integers in given sequence that are divisible by $$$k$$$.
We see that this result comes from the Inclusion-Exclusion principle. The term in the summation corresponds to choosing two numbers which are multiples of $$$k$$$, and $$$\mu(k)$$$ decides whether we add it or not. Note that in inclusion-exclusion, we don’t consider $$$k$$$ which aren’t square free, as it doesn’t add any effect to our answer.
Time complexity is $$$O(10^6log(10^6))$$$. Check the code below for implementation of Mobius function.
A similar problem for reference — https://discuss.codechef.com/t/coprime3-editorial/6051

ll lpf[1000001],mobius[1000001];

void least_prime_factor()
{
    for(int i=2;i<1000001;i++)
    {
        if(!lpf[i])
        {
            for(int j=i;j<1000001;j+=i)
            {
                if(!lpf[j]) lpf[j]=i;
            }
        }
    }
}
 
void Mobius()
{
    for(int i=1;i<1000001;i++) 
    {
        if(i==1) mobius[i]=1;
        else 
        {
            if(lpf[i/lpf[i]]==lpf[i]) mobius[i]=0;
            else mobius[i]=-1*mobius[i/lpf[i]];
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll x[n],cnt[1000001]={};
    for(int i=0;i<n;i++)
    {
        cin>>x[i];
        cnt[x[i]]++;
    }
    least_prime_factor();
    Mobius();
    ll ans=0;
    for(int i=1;i<1000001;i++)
    {
        if(mobius[i]==0) continue;
        ll d=0;
        for(int j=i;j<1000001;j+=i)
        {
            d+=cnt[j];
        }
        ans+=(d*(d-1))/2*mobius[i];
    }
    cout<<ans;
}

First we will pre-build a factorial array. For division with mod, we can do that by multiplying by its modulo inverse. If you don’t have a idea about inverse, see this https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[1000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll n,a,b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        ll ans=(fact[a]*inverse(fact[b]))%MOD;
        ans*=inverse(fact[a-b]);
        ans%=MOD;
        cout<<ans<<"\n";
    }
}

This is basic combinatorics. The number of ways of arranging these characters is $$$\frac{n!}{\prod_{i=1}^{26} (cnt(alphabet_{i}))!}$$$.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[1000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=1000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    string s;
    cin>>s;
    ll n=s.size();
    ll cnt[26]={};
    for(int i=0;i<n;i++)
    {
        cnt[s[i]-'a']++;
    }
    ll tot=fact[n];
    for(int i=0;i<26;i++)
    {
        tot*=inverse(fact[cnt[i]]);
        tot%=MOD;
    }
    cout<<tot;
}

It is equivalent to finding the number of solution to $$$x_1 + x_2 + \cdots + x_n=m$$$, where $$$x_1,x_2,\cdots,x_n$$$ are non negative integers.
You can see that here- https://www.geeksforgeeks.org/number-of-integral-solutions-of-the-equation-x1-x2-xn-k/.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll fact[2000001];
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<=2000000;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll n,m;
    cin>>n>>m;
    ll ans=(fact[m+n-1]*inverse(fact[n-1]))%MOD;
    ans*=inverse(fact[m]);
    ans%=MOD;
    cout<<ans;
}

This is a standard problem of finding derangements in a sequence.
The recursive formula is $$$D(n)=(D(n-1)+D(n-2))(n-1)$$$.
For info regarding derangement, see https://en.wikipedia.org/wiki/Derangement.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll d[n+1];
    d[1]=0;
    d[2]=1;
    for(ll i=3;i<=n;i++)
    {
        d[i]=(((d[i-1]+d[i-2])%MOD)*(i-1))%MOD;
    }
    cout<<d[n];
}

Let $$$dp[n]$$$ denote the number of bracket sequences with $$$n$$$ pairs of bracket. At first index, there is always a opening bracket and somewhere is between there is a closing bracket. So we look at how many sequences of $$$i$$$ pairs of brackets are there between them and how many sequences of $$$n-i-1$$$ pairs of brackets are after them. So we get the recursive formula – $$$dp[n]=\sum_{i=0}^{n-1}dp[i]dp[n-i-1]$$$.
And $$$dp[0]=0$$$. In fact this is nothing but the Catalan number $$$C_n=\frac{1}{n+1} {2n \choose n}$$$.
You can refer to this — https://cp-algorithms.com/combinatorics/bracket_sequences.html

const int MOD=1000000007; 
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    if(n%2==1) 
    {
        cout<<0;
        return 0;
    }
    n/=2;
    ll fact[2*n+1];
    fact[0]=1;
    for(ll i=1;i<=2*n;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll ans=(fact[2*n]*inverse(fact[n]))%MOD;
    ans*=(inverse(fact[n])*inverse(n+1))%MOD;
    ans%=MOD;
    cout<<ans;
}

Let $$$k$$$ denote the excess opening brackets which we need to close and $$$n$$$ denote the remaining pairs. This can be easily found out given the length and the prefix portion of the string.
Let us denote the answer by $$$C_n^{(k)}$$$. The generalized formula is -
$$$C_n^{(k)}= \sum_{a+b+\dots+\lambda=n} C_a C_b \dots C_\lambda$$$, $$$C_0=1$$$.
where there are $$$k+1$$$ terms, $$$C_a,C_b,\dots,C_\lambda$$$.
This is basically a convolution on Catalan. Similar to deriving the expression for Catalan number, we get $$$C_n^{(k)}=\frac{k+1}{n+k+1} {2n+k \choose k}$$$.
You can refer to this — https://codeforces.me/blog/entry/87585

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    if(n%2==1)
    {
        cout<<0;
        return 0;
    }
    n/=2;
    string s;
    cin>>s;
    ll k=0,o=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='(') 
        {
            k++;
            o++;
        }
        else k--;
        if(k<0)
        {
            cout<<0;
            return 0;
        }
    }
    n-=o;
    if(k<0 || n<0 || 2*n+k<n)
    {
        cout<<0;
        return 0;
    }
    ll fact[2*n+k+1];
    fact[0]=1;
    for(int i=1;i<=2*n+k;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    ll ans=(fact[2*n+k]*inverse(fact[n]))%MOD;
    ans*=inverse(fact[n+k]);
    ans%=MOD;
    ans*=((k+1)*inverse(n+k+1))%MOD;
    ans%=MOD;
    cout<<ans;
}

This is computed by using Burnside’s Lemma. It states that the total number of distinct objects is $$$\sum_{k=1}^{N} \frac{c(k)}{N}$$$, where $$$c(k)$$$ is number of combination that remain unchanged when $$$k$$$-th rotation is applied. If we rotate the necklace by $$$i$$$, $$$m^{gcd(i,n)}$$$ necklaces will remain the same.
So the answer would be $$$\sum_{i=1}^{n} \frac{m^{gcd(i,n)}}{n}$$$.
You can refer to this — https://www.geeksforgeeks.org/orbit-counting-theorem-or-burnsides-lemma/

const int MOD=1000000007; 
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
        ll temp=POW(m,__gcd(i,n));
        temp*=inverse(n);
        temp%=MOD;
        ans+=temp;
        ans%=MOD;
    }
    cout<<ans;
}

We will be using the following recursion-
If $$$n$$$ is even then $$$k = \frac{n}{2}$$$:
$$$F(n) = [2 \times F(k-1) + F(k)] \times F(k) $$$

If $$$n$$$ is odd then $$$k = \frac{n + 1}{2}$$$:
$$$F(n) = F(k) \times F(k) + F(k-1) \times F(k-1) $$$

This will calculate the fibonacci number in $$$O(logn)$$$. Remember to store the values in a map. For the proof of the recurrence relation- https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}
map<ll,ll> f;

ll fib(ll n)
{
    if(f.count(n)) return f[n];
    if(n==0) return 0;
    if(n==1 || n==2) return 1;
    if(n%2==0)
    {
        ll k=n/2;
        ll ret1=fib(k-1),ret2=fib(k);
        return f[n]=((((2ll*ret1)%MOD+ret2)%MOD)*ret2)%MOD;
    }
    else
    {
        ll k=(n+1)/2;
        ll ret1=fib(k-1),ret2=fib(k);
        return f[n]=( (ret1*ret1)%MOD + (ret2*ret2)%MOD)%MOD;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    cout<<fib(n);
}

It can be solved in $$$O(n)$$$ using the recurrence relation-
$$$F(n)=F(n-1)+F(n-2)+F(n-3)+F(n-4)+F(n-5)+F(n-6)$$$.
But this would give a TLE. So we will be using a technique called matrix exponentiation that involve calculating the $$$n^{th}$$$ term of a linear recurrence relation in time of the order of $$$O(logn)$$$.

See the following for more on it-
https://codeforces.cc/blog/entry/67776
https://www.geeksforgeeks.org/find-nth-term-a-matrix-exponentiation-example/

Check my code below for further clarification.

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(6, vll(6));
    for (int j = 0; j < 6; j++)
    {
        for (int k = 0; k < 6; k++) 
        {
            for (int l = 0; l < 6; l++)
            {
                r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll n) 
{
    if (n == 0)
    {
        vector<vll> r(6, vll(6));
        for (int i = 0; i < 6; i++) r[i][i] = 1;
        return r;
    }
    vector<vll> u = modpow(x, n/2);
    u = mul(u, u);
    if (n%2==1) u = mul(u, x);
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    vector<vll> a(6,vll(6));
    for(int i=0;i<5;i++)
    {
        a[i][i+1]=1;
    }
    for(int i=0;i<6;i++)
    {
        a[5][i]=1;
    }
    vector<vll> ans=modpow(a,n);
    cout<<ans[5][5];
}

Let’s first create an Adjacency matrix. We can see for the case of $$$k=1$$$, the answer is the constructed Adjacency Matrix, for any 2 pair of nodes.
Next let the matrix $$$M_k$$$ denote the answer matrix for $$$k$$$.
Then $$$M_{k+1}[i][j]=\sum_{l=1}^{n} M_{k}[i][l].AdjMat[l][j]$$$.
Thus the solution of the problem is $$$AdjMat^{k}$$$.
For more info refer- https://cp-algorithms.com/graph/fixed_length_paths.html

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

ll n;

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(n, vll(n));
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++) 
        {
            for (int l = 0; l < n; l++)
            {
                r[j][k] = (r[j][k]+(x[j][l]*y[l][k])%MOD)%MOD;
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll pw) 
{
    if (pw == 0)
    {
        vector<vll> r(n, vll(n));
        for (int i = 0; i < n; i++) r[i][i] = 1;
        return r;
    }
    vector<vll> u = modpow(x, pw/2);
    u = mul(u, u);
    if (pw%2==1) u = mul(u, x);
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll m,k,a,b;
    cin>>n>>m>>k;
    vector<vll> v(n,vll (n,0));
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        a--; b--;
        v[a][b]++;
    }
    cout<<modpow(v,k)[0][n-1];
}

It’s a really nice problem. The procedure is almost the same as above question. We will create an Adjacency matrix where each entry stores the minimum weight edge, or $$$INF$$$ if no edge.
Next let the matrix $$$M_k$$$ denote the answer matrix for $$$k$$$.
Then $$$M_{k+1}[i][j]=min_{l=(1 \cdots n)} (M_{k}[i][l]+AdjMat[l][j])$$$.
Here we can make an analogy with the multiplication operation. Instead we take the minimum rather than sum.
This can be tackled by matrix exponentiation, just have to modify the $$$mul()$$$ function.
See my code for further clarification.
For more info refer- https://cp-algorithms.com/graph/fixed_length_paths.html#toc-tgt-1

const int MOD=1000000007;
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}

ll INF=4e18;
ll n;

vector<vll> mul(vector<vll> x, vector<vll> y) {
    vector<vll> r(n, vll(n,INF));
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++) 
        {
            for (int l = 0; l < n; l++)
            {
                r[j][k] = min(r[j][k],x[j][l]+y[l][k]);
            }
        }
    }
    return r;
}

vector<vll> modpow(vector<vll> x, ll pw) 
{
    if (pw == 1)
    {
        return x;
    }
    vector<vll> u = modpow(x, pw/2);
    u = mul(u, u);
    if (pw%2==1) u = mul(u, x);
    return u;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll m,k,a,b,c;
    cin>>n>>m>>k;
    vector<vll> v(n,vll(n,INF));
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        a--; b--;
        v[a][b]=min(v[a][b],c);
    }
    ll ans=modpow(v,k)[0][n-1];
    if(ans==INF) cout<<"-1";
    else cout<<ans;
}

This can be solved using dp, where $$$dp[i][j]$$$ denotes the probability of getting sum $$$j$$$ when the dice has been rolled $$$i$$$ times.
The transition would be-
$$$dp[i][j]=\frac{\sum_{k=1}^{min(6,j)} dp[i-1][j-k]}{6}$$$.
Then the answer will be $$$\sum_{i=a}^{b} dp[n][i]$$$.
Taking care of rounding off. See my code for that.
Time complexity is $$$O(n^2)$$$.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,a,b;
    cin>>n>>a>>b;
    vector<vector<ld> > dp(n+1,vector<ld> (6*n+1,0));
    dp[0][0]=1.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=6*n;j++)
        {
            for(int k=1;k<=6;k++)
            {
                if(j-k>=0)
                {
                    dp[i][j]+=dp[i-1][j-k];
                }
            }
            dp[i][j]=dp[i][j]/6;
        }
    }
    ld ans=0;
    for(int i=a;i<=b;i++)
    {
        ans+=dp[n][i];
    }
    ans*=1e6;
    ans=llround(ans);
    ans/=1e6;
    cout<<fixed<<setprecision(6)<<ans;
}

We do something like brute force here. Consider a robot on a single cell only, assuming all others don’t have robot present.
Here $$$dp[k][i][j]$$$ represents the expected probability of a robot to be present in cell $$$(i,j)$$$ after $$$k$$$ steps.
The state transition would be $$$dp[k+1][i+dr[f]][j+dc[f]]+=\frac{dp[k][i][j]}{totaldirections} $$$, where $$$dr[4]$$$ and $$$dc[4]$$$ iterates over the $$$4$$$ possible directions.
The expected answer for each individual cell $$$(i,j)$$$ would be the product of $$$(1-dp[n][i][j])$$$.
Adding all the expected values for a single cell gives us our final answer.
Time complexity is $$$O(8^4n)$$$.

ll dr[4]={1,-1,0,0};
ll dc[4]={0,0,1,-1};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ld dp[n+1][8][8]={};
    ld ans[8][8];
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            ans[i][j]=1;
        }
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            for(int k=0;k<=n;k++)
            {
                for(int i1=0;i1<8;i1++)
                {
                    for(int j1=0;j1<8;j1++)
                    {
                        dp[k][i1][j1]=0;
                    }
                }
            }
            dp[0][i][j]=1;
            for(int k=0;k<n;k++)
            {
                for(int i1=0;i1<8;i1++)
                {
                    for(int j1=0;j1<8;j1++)
                    {
                        ld dir=0;
                        for(int f=0;f<4;f++)
                        {
                            ll u=i1+dr[f],v=j1+dc[f];
                            if(u>=0 && u<8 && v>=0 && v<8)
                            {
                                dir++;
                            }
                        }
                        for(int f=0;f<4;f++)
                        {
                            ll u=i1+dr[f],v=j1+dc[f];
                            if(u>=0 && u<8 && v>=0 && v<8)
                            {
                                dp[k+1][u][v]+=dp[k][i1][j1]/dir;
                            }
                        }
                    }
                }
            }
            for(int i1=0;i1<8;i1++)
            {
                for(int j1=0;j1<8;j1++)
                {
                    ans[i1][j1]*=(1-dp[n][i1][j1]);
                }
            }
        }
    }
    ld expc=0;
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            expc+=ans[i][j];
        }
    }
    cout<<fixed<<setprecision(6)<<expc;
}

For each $$$i$$$ from $$$1$$$ to $$$k$$$, we first find the probability such that the maximum is $$$i$$$. That would be equal to $$$(\frac{i}{k})^n -(\frac{i-1}{k})^n$$$. This is because we first uniformly choose $$$n$$$ numbers from $$$1$$$ to $$$i$$$ and subtract those cases in which $$$i$$$ doesn’t occur. Next we multiply it by $$$i$$$ to find the expected maximum, and add all those.
Taking care of rounding off. See my code for that.
Time complexity is $$$O(nk)$$$.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ld ans=0;
    for(int i=1;i<=k;i++)
    {
        ld add=1,sub=1;
        for(int j=1;j<=n;j++)
        {
            add*=(ld)i/(ld)k;
            sub*=(ld)(i-1)/(ld)k;
        }
        ans+=(ld)(i)*(ld)(add-sub);
    }
    ans*=1e6;
    ans=llround(ans);
    ans/=1e6;
    cout<<fixed<<setprecision(6)<<ans;
}

Due to lower constraint on $$$n$$$, brute force will work. We find expected inversions for every pair of $$$(i,j)$$$ where $$$i<j$$$.
If $$$a[j] \le a[i]$$$, then the number of inversions will be $$$a[j] \choose 2$$$, because $$$i$$$-th element should have values till $$$a[j]$$$.
Otherwise if $$$a[j]>a[i]$$$, then the number of inversions will be $$$a[i] \choose 2$$$ $$$+ ((a[j]-a[i]) \times a[i])$$$, which is the sum of cases when $$$j$$$-th element is less than $$$a[i]$$$ or greater.
Time complexity is $$$O(n^2)$$$.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    ld ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            ll k;
            if(a[j]<=a[i])
            {
                k=(a[j]*(a[j]-1))/2;
            }
            else
            {
                k=(a[i]*(a[i]-1))/2 + (a[j]-a[i])*a[i];
            }
            ans+=(ld)k/(ld)(a[j]*a[i]);
        }
    }
    cout<<fixed<<setprecision(6)<<ans;
}

Let $$$dp[i]$$$ denote the result of game if there are total $$$i$$$ sticks. Here $$$dp[i]$$$ is true is first player wins, otherwise false.
We know $$$dp[0]$$$ is false. The transition would be that if $$$dp[i-p[j]]$$$ is false where $$$j={1, \cdots ,k}$$$, then $$$dp[i]$$$ would be true.
Time complexity is $$$O(nk)$$$.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll p[k];
    for(int i=0;i<k;i++)
    {
        cin>>p[i];
    }
    ll dp[n+1]={};
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            if(i-p[j]>=0 && dp[i-p[j]]==0)
            {
                dp[i]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dp[i]==1) cout<<"W";
        else cout<<"L";
    }
}

This is a straight nim game questions where the second player wins when the xor of the elements of array is 0, and otherwise first player wins.
For more info regarding nim- https://en.wikipedia.org/wiki/Nim

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll x[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            xr^=x[i];
        }
        if(xr!=0) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

It’s a variation of nim game called the subtraction game where an upper bound of stones that can be removed, let say $$$k$$$ be given. All we have to do is to consider the pile mod $$$(k+1)$$$, and then follow the usual nim.
For more info- https://en.wikipedia.org/wiki/Nim#The_subtraction_game

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll x[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>x[i];
            x[i]%=4;
            xr^=x[i];
        }
        if(xr!=0) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

We consider elements at even position and proceed as Nim. I don’t have a proof as to why it works. There is some intuition- to empty a pile a position $$$k$$$, we will have to empty it all the way to position $$$1$$$, which means there are $$$(k-1)$$$ copies of that pile which we have to empty.
So if $$$k$$$ is odd, xor of $$$k$$$ even number of times is $$$0$$$, so the odd positions don't create an effect, and hence we consider the even positions only.
If some one has a formal proof of this, please mention it in the comments.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t,n;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>n;
        ll a[n];
        ll xr=0;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(i%2)
            {
                xr^=a[i];
            }
        }
        if(xr) cout<<"first";
        else cout<<"second";
        cout<<"\n";
    }
}

We find the Sprague-Grundy values corresponding to the Grundy’s game. This can be easily done by dynamic programming, as we find the mex of all the state reachable from that state. Also we note that for larger values of $$$n$$$ ($$$n \ge 2000$$$), its Sprague-Grundy value is never $$$0$$$. (I don’t have a proof for this, maybe someone can let me know in the comments.)
You can read about Sprague-Grundy theorem here — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html

ll mex(vll v)
{
    set<ll> s;
    for(int i=0;i<v.size();i++)
    {
        s.insert(v[i]);
    }
    for(int i=0;i<1000001;i++)
    {
        if(s.count(i)==0) return i;
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll limit=2000;
    ll dp[limit];
    dp[0]=dp[1]=dp[2]=0;
    for(int i=3;i<limit;i++)
    {
        vll v;
        for(int j=1;2*j<i;j++)
        {
            v.PB(dp[j]^dp[i-j]);
        }
        dp[i]=mex(v);
    }
    ll t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        ll n;
        cin>>n;
        if(n>=limit) cout<<"first";
        else if(dp[n]==0) cout<<"second";
        else cout<<"first";
        cout<<"\n";
    }
}