For odd values of $$$n$$$ we can re-express string $$$s$$$ as

Note that $$$s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$$$ , so we can assume the sum as $$$f$$$.

And let's denote the median digit by $$$h$$$ , thus the sum is $$$2f+h$$$ , it can be shown that $$$h$$$ can be possibly any digit , thus we can construct all sums which lies between minimum and maximum inclusive .

Now Let's do the same for even values of $$$n$$$ we can re-express $$$s$$$ as

Using the symmetric property we can see $$$s_{\lfloor \frac{n}{2} \rfloor}=s_{\lfloor \frac{n}{2} \rfloor+1}$$$ , if we denote one digit by $$$h$$$ thus the sum of medians is $$$2h$$$ and if we denote the left and right segments by $$$f$$$ as we did for odd $$$n$$$ then we have $$$m=2f+2h=2(f+h)$$$ thus for even $$$n$$$ we have an additional condition that sum must be even

Thus Total Complexity for each test case is $$$\mathcal{O}(1)$$$ time .

for _ in range(int(input())): 
  n,m= map(int, input().split())
  if(m >= n and m <= 9 * n and (n % 2 != 0 or m % 2 == 0)):
    print("YES")
  else:
    print("NO")

If $$$x<z$$$, the answer is obviously $$$-1$$$. We only consider the case of $$$x \ge z$$$.

Maximum number of interviews per day can happen is the number of distinct interviews can happen , which is the number of interviewers times the capacity of each interviewer integer divided by the needed interviewers in one interview , Formally

The construction is simple:

consider a sequence of length $$$x \cdot y$$$ — $$$[1,2,\ldots,x,1,2,\ldots,x,\ldots]$$$ , and simply output consecutive segments of length $$$z$$$ in order.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353


int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,z,ans,now;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d%d",&x,&y,&z);
		if (z>x)
		{
			printf("0\n");
			continue;
		}
		ans=x*y/z;
		printf("%d\n",ans);
		now=1;
		for (i=0;i<ans;i++)
		{
			for (j=0;j<z;j++)
			{
				printf("%d ",now);
				now++;
				if (now>x) now=1;
			}
			printf("\n");
		}
	}
}

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$.

The answer is $$$\Sigma_{i=1}^n f_i$$$.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 1000000007

int a[1100000];
_int64 d[1100000];

int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,qq,ll,rr;
	_int64 ans;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d%d",&n,&qq);
		for (i=0;i<n;i++)
			scanf("%d",&a[i]);
		for (o=0;o<qq;o++)
		{
			scanf("%d%d",&ll,&rr);
			ll--;rr--;
			d[ll]=a[ll];
			d[ll]%=mo;
			ans=d[ll];
			for (i=ll+1;i<=rr;i++)
			{
				d[i]=d[i-1]*a[i]+a[i];
				d[i]%=mo;
				ans+=d[i];
				ans%=mo;
			}
			printf("%lld\n",ans);
		}
	}
}

For $$$n,m \ge 4$$$, we have trival construct $$$p_i=i$$$ to make condition $$$1$$$ holds.

Then check all $$$a_i+a_{i+1}=0 (\mod m)$$$, we can just swap $$$a_i$$$ and $$$a_{i-1}$$$ to make condition $$$2$$$ holds.

For $$$n,m < 4$$$, we need to some case work. Be careful of $$$n=4,m=3$$$ case and $$$n=2$$$ case.

For $$$k=3$$$ generate cases separately (Exercise) , for $$$k=2$$$ the permutation $$$[1,2,3,...,n]$$$ always works .

we need to see all cases (pairs) for which violates the condition , well let's see how we determine the number of pairs for only (odd numbers) since even $$$k$$$ can be solved with typical standard permutation .\ Using \textbf{Mod Array} this is how we can get the number of invalid pairs, $$$(0,0)$$$ is always invalid pair , then there are another pairs depending on $$$k$$$ , there are $$$\lfloor \frac{n}{2} \rfloor$$$ different pairs to do sum with, for example $$$k=3 \Rightarrow {(1,2),(2,1)}$$$ which can be counted $$$2 \lfloor \frac{n}{2} \rfloor=n-1$$$ for odd numbers and there's also base case yields $$$n$$$ invalid pairs, Now our mission is to construct a permutation without facing any pair of these. Let's analyze the situation , for all numbers in $$$[1,n]$$$ it has a specific value $$$\mod k$$$ , we want to calculate how many values $$$i$$$ such that : $$$1 \le i \le n$$$ satisfy \ $$$ i \mod k=x$$$ , let's construct a \textbf{Mini Mod Array} that will determine the \textbf{Final Mod Array} and depending on it we'll construct the permutation.

Again we separate 3 because it's an edge case and it's a triangular number of the second degree,Let's see how we can arrange the \textbf{Final Mod Array} , we want to count all the mods by $$$k$$$ for the numbers , it can be calculated as follows:- Considering $$$n \mod k=x$$$\ Every mod has at least $$$\lfloor \frac{n}{k} \rfloor$$$ values for mod in the array , and $$$\forall : 1 \le i \le x$$$ it'll increase by 1 , let's denote the number of mod values such $$$i \textbf{ mod } k =z$$$ appears on the \textbf{Final Mod Array} as $$$c_{z}$$$ , so we obtain the following fact:-

Using The Past Fact , we can construct a valid permutation for all odd $$$k$$$ except $$$3$$$ , let the \textbf{Final Mod Array} be expanded like this :-

Now we let's reflect what we made in the expanded mod array , the sum of each pair can be \textbf{even} because 2 numbers has the same mod and of course won't be divisible by $$$k$$$ , or some number $$$b$$$ will collide with the next so the new number making $$$(2b+1) \mod k$$$ , so since $$$2b+1$$$ is always odd we make sure that $$$2b+1$$$ is not equal to $$$k$$$ by \textit{swap}$$$(\lfloor \frac{k}{2} \rfloor , \lfloor \frac{k}{2} \rfloor -1$$$),Finally still to distribute $$$0$$$'s so that no pair is equal to (0,0) , since

then we can distribute pairs : $$$(k-1,0)$$$ so if $$$c_{k-1}=c_0$$$ we can distribute it like this

and if $$$c_{k-1}=c_0+1$$$ then it can be distributed like this:-

so we make sure that no (0,0) pair is in the expanded mod array. Let's work an example to finish the explanation $$$(n,k)=(20,9)$$$:-

$$$20 \mod 9=2 \Rightarrow c_1=c_2=\lfloor \frac{n}{k} \rfloor+1=3$$$ and $$$c_3=c_4=..=c_8=c_0=2$$$ so the final mod array

Finally generate numbers W.R.T mods , one valid permutation is:-

\textbf{Note: In practice we'll put $$$0$$$ as $$$k$$$ for generating correct answers but mathematically it's just $$$0$$$}\ We used $$$\mathtt{map}$$$ Structure ($$$\mathtt{dict}$$$ in $$$\mathtt{python}$$$) to optimize the storing operation in average $$$\mathcal{O}(1)$$$ time, and constructing operation takes $$$\mathcal{O}(n)$$$ time , since time for storing values in $$$\mathtt{map}$$$ structure we consider the worst case of $$$\mathtt{map}$$$ , so complexity (worst case) is $$$\mathcal{O}(n+k)$$$ because the $$$\mathtt{dict}$$$ structure in $$$\mathtt{python}$$$ .

~~~~~

This problem can be solved by classical DDP (https://en.oi-wiki.org/dp/dynamic/) in $$$O(n \log n)$$$. So we ask for $$$O(n)$$$ solution.

Note $$$f_i=\Sigma_{j=1}^i a_j·...·a_i$$$. We can get $$$f_1=a_1$$$ and $$$f_i=a_i + a_i \cdot f_{i-1}$$$ for $$$2 \le i \le n$$$. And $$$g_i=\Sigma_{j=1}^i f_i$$$.

For query $$$l,r$$$, consider $$$ans=g_r-g_l$$$. We have not done. We still need to substract $$$ans$$$ by $$$ \Sigma_{1 \le j \le l, l+1 \le k \le r} a_j·...·a_k$$$.

Nore $$$P_i=a_1·...·a_i$$$, and $$$IP_i=P_i^{-1}$$$

In fact, $$$ \Sigma_{1 \le j \le l, l+1 \le k \le r} a_j·...·a_k$$$ is equal to $$$(IP_0+IP_1+...+IP_{l-1})·(P_{l+1}+P_{l+2}+...+P_r)$$$

All this formula can be calculated in $$$O(n)$$$.

Complexity: $$$O(n+q)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T,n,q;
ll  a[N],dp[N],P[N],SP[N],IP[N],SIP[N];

ll pw(ll x,ll p)
{
	if(!p) return 1;
	ll y=pw(x,p>>1);
	y=(y*y)%TMD;
	if(p&1) y=(y*(x%TMD))%TMD;	
	return y;
}

ll INV(ll x)
{
    return pw(x,TMD-2);
}

void init()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
}

void solve()
{
    dp[1]=a[1];
    for(int i=2;i<=n;i++)
        dp[i]=(dp[i-1]+a[i]+a[i]*(dp[i-1]-dp[i-2]))%TMD;
    P[0]=SP[0]=IP[0]=SIP[0]=1;
    for(int i=1;i<=n;i++)
        P[i]=(P[i-1]*a[i])%TMD;
    IP[n]=INV(P[n]);
    for(int i=n-1;i;i--) IP[i]=IP[i+1]*a[i+1]%TMD;
    for(int i=1;i<=n;i++)
    {
        SP[i]=(SP[i-1]+P[i])%TMD;
        SIP[i]=(SIP[i-1]+IP[i])%TMD;
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        ll  ans;
        cin>>l>>r;
        ans=(dp[r]-dp[l-1]+TMD)%TMD;
        if(l>1) ans=(ans-(SP[r]-SP[l-1])*(SIP[l-2])+TMD*TMD)%TMD;
        cout<<ans<<'\n';
    }
}

int main()
{
    fastio;

	cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

We found that the probability of taking a certain number is only related to its rank. Let $$$P[i][j]$$$ represent the probability that, out of a total of $$$i$$$ numbers, Alice selects the $$$j$$$-th smallest number.

When the coin is on the obverse side, Alice's probability of picking it up is $$$\frac{1}{2} \cdot \frac{j}{1 + \dots + i}$$$. When a coin is reversed, consider two situations:

• The number with rank smaller than $$$j$$$ have been taken. If so Alice's probability of picking it up is $$$\frac{1 + \dots + (j-1)}{1 + \dots + i} P[i-1][j-1]$$$;

• The number with rank greater than $$$j$$$ has been taken. If so Alice's probability of picking it up is $$$\frac{(j+1) + \dots + i}{1 + \dots + i} P[i-1][j]$$$.

So the recurrence relation for $$$P[i][j]$$$ is given by:

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T,n;
int a[N];
ll  P[N][N];

ll pw(ll x,ll p)
{
	if(!p) return 1;
	ll y=pw(x,p>>1);
	y=(y*y)%TMD;
	if(p&1) y=(y*(x%TMD))%TMD;
	return y;
}

ll INV(ll x)
{
    return pw(x,TMD-2);
}

ll SUM(ll x)
{
	return x*(x+1)/2;
}

ll SUM(ll L,ll R)
{
	if(L>R) return 0;
	return SUM(R)-SUM(L-1);
}

void init_P()
{
	P[1][1]=INV(2);
	for(int i=2;i<N;i++)
	{
		for(int j=1;j<=i;j++)
		{
			P[i][j]=INV(2)*j%TMD*INV(SUM(1,i))%TMD;
			P[i][j]=(P[i][j]+INV(2)*SUM(j+1,i)%TMD*INV(SUM(1,i))%TMD*P[i-1][j])%TMD;
			P[i][j]=(P[i][j]+INV(2)*SUM(1,j-1)%TMD*INV(SUM(1,i))%TMD*P[i-1][j-1])%TMD;
		}
	}
}

void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}

void solve()
{
	ll ans=0;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) ans=(ans+P[n][i]*a[i])%TMD;
	printf("%I64d\n",ans);
}

int main()
{
	init_P();
	scanf("%d",&T);
	while(T--)
	{
		init();
		solve();
	}
	
	return 0;
}

Note $$$X$$$ as set of $$$a_i$$$.

Note that $$$f(N)$$$ is defined only when $$$N < \text{lcm}(X)$$$.

How do we find $$$f(N)$$$ greedily? In each step, it's sufficient to keep track of the smallest achievable element in that step.

Let's build $$$f$$$ manually, where for every $$$0 \leq i \leq m$$$, $$$f[i] = \min(f[i - i \% y]) + 1$$$ for all $$$y \in X$$$. This is doable in $$$O(m \times |X|)$$$, which is too slow to pass the time limit.

Firstly, let's prove that $$$f$$$ is a non-decreasing function. For all $$$i$$$, it can be shown that $$$f(i) \leq f(i+1)$$$, because for any integer $$$y$$$, $$$(i + 1) - (i + 1) \% y \geq i - i \% y$$$.

It can also be proven that for any $$$i$$$, one of the following is true: $$$f(i) = f(i+1)$$$ or $$$f(i) + 1 = f(i + 1)$$$.

Now, we can use binary search to find the lengths of each value's occurrences. Let the current index be $$$i$$$. We can find the rightmost index (let it be $$$j$$$), for which $$$f(j) = f(i) + 1$$$. In each iteration, we add $$$(j - i) \times f(j)$$$.

This works in $$$O(|X| \times f(m) \times \log(m))$$$ time. This is sufficient because it can be proven that $$$|X| \times f(m) \leq 2 \times m$$$.

Let $$$mx = \max(X)$$$. In each step, we choose $$$mx$$$ if the number is not divisible by $$$mx$$$ ($$$m \to m - m \% mx$$$), otherwise we choose any other element, which decreases $$$m$$$ by at least $$$1$$$. Then, it's clear that for every $$$2$$$ steps, the current value decreases by at least $$$mx$$$, where $$$mx \geq |X|$$$. Thus, $$$|X| \times f(m) \leq mx \times 2 \times (m / mx) \leq 2 \times m$$$.

Overall time complexity is $$$O(|X| \times f(m) \times \log(m))$$$ or $$$O(|X| \times f(m))$$$, depending on the implementation.

Bonus: Try to prove that $$$|X| \times f(m) \leq m + 1$$$, for any given input values.

Conclusion:

• $$$f$$$ is sorted

• $$$f(n)$$$ is defined only when $$$n < \text{lcm}(X)$$$

• $$$f(m) \times |X| = O(m)$$$

• $$$f(i) = f(i-1) + 1$$$ or $$$f(i) = f(i-1)$$$ for any $$$i$$$

For greedy computation of $$$f(m)$$$, we can choose the smallest value achievable from one operation in each step.

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<int> X(n);
        for (auto &i : X)
            cin >> i;
        int ans = 0;
        int cur = 0;
        int i = 0;
        while (i < m)
        {
            int mx = i + 1;
            for (auto &j : X)
                mx = max(mx, (i) / j * j + j - 1);
            mx = min(mx, m);
            cur++;
            ans += cur * (mx - i);
            i = mx;
        }
        cout << ans << '\n';
    }
    return 0;
}