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;
}

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];
}

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.com/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";
    }
}