The answer is 'yes' if and only if there are exactly $$$n$$$ odd numbers.

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--){
		int n,cnt[2]={0};
		cin>>n;
		for(int i=1,x;i<=n*2;i++)cin>>x,cnt[x%2]++;
		if(cnt[0]==n)puts("Yes");
		else puts("No");
	}
	return 0;
}

What kind of element in the set is important?

If $$$x$$$ is in the set, but $$$x-b$$$ is not, $$$x$$$ is important. Why?

How can we find all important elements?

First judge specially if $$$b=1$$$.

Let's consider when $$$n$$$ is in $$$S$$$. The answer is when the smallest number $$$m$$$ in $$$S$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$ is less than $$$n$$$. It's easy to see that a new case of $$$x\ \mathrm{mod}\ b$$$ can only appear when you use $$$\times a$$$ to generate a new element. So the smallest number $$$m$$$ in S that $$$m\ \mathrm{mod}\ b=k$$$ must be a power of $$$a$$$.

Find all powers of a that is smaller than $$$n$$$. If there is one $$$m=a^k$$$ that $$$n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$$$, the answer is yes. Otherwise it's no. Time complexity is $$$O(\log n)$$$.

t=(int)(input())
for i in range(t):
    w=input().split()
    n=(int)(w[0])
    a=(int)(w[1])
    b=(int)(w[2])
    if a==1 :
    	if (n-1)%b==0 :
    		print("Yes")
    	else :
    		print("No")
    	
    else :
    	t=1
    	flag=0
    	while t<=n :
    		if t%b==n%b:
    			flag=1
    			break
    		t=t*a
    	if flag==1:
    		print("Yes")
    	else :
    		print("No")

$$$f(n)$$$ is small.

For a given $$$x$$$, when is $$$f(n)$$$ equal to $$$x$$$?

Enumerate the value of $$$f(i)$$$. Since $$$f(n)=i$$$ means $$$lcm(1,2,...,i-1)\le n$$$, $$$f(n)$$$ will not be too big (less than $$$100$$$). The number of $$$k$$$s such that $$$f(k)=i$$$ is $$$\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor $$$. ($$$k$$$ should be divisible by $$$1\sim i-1$$$ but not $$$i$$$) So the answer is $$$\sum_{i>1} i(\lfloor n/lcm(1,2,...,i-1)\rfloor -\lfloor n/lcm(1,2,...,i)\rfloor )$$$.

We can also write the answer in another form, which is equivalent to the previous form:

#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
int t,n;
const int M=1e9+7;
inline int gcd(re int x,re int y){
	return y?gcd(y,x%y):x;
}
inline int LCM(re int x,re int y){
	return x/gcd(x,y)*y;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		re int G=1,ans=0;
		for(re int i=1;G<=n;++i){
			G=LCM(G,i);
			if(G>n)break;
			ans+=n/G;
		}
		printf("%lld\n",(ans+n)%M);
	}
}

For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.

For each $$$x$$$, count how many $$$B$$$s make the final set contain $$$x$$$.

Let's say we have picked the $$$x$$$ in the $$$I$$$-th operation, call it $$$X$$$. Then, the subsequence we choose must satisfy the following conditions:

• It must contain the $$$i$$$-th operation (otherwise $$$X$$$ won't be added).
• Let $$$s$$$ denote the number of numbers less than $$$X$$$ in the current $$$T$$$. Whenever we meet a - element in $$$S$$$ after the $$$i$$$-th operation, $$$s$$$ should be greater than $$$0$$$.

With those conditions, we can come up with the following dp.

Let $$$f(i,j)$$$ denote the number of subsequences of $$$a[1...i]$$$, that if we maintain $$$T$$$ with the subsequence, $$$s$$$ will become $$$j$$$.

Then we have the following transitions:

• $$$f(i-1,j)\to f(i,j)$$$ (when we don't include the $$$i$$$-th element is $$$S$$$, here $$$i\ne I$$$)
• $$$f(i-1,j)\to f(i,\max(j-1,0))$$$ (here, $$$i<I$$$, and the $$$i$$$-th element of $$$A$$$ is -, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one. If there is no such number, $$$s$$$ remains $$$0$$$)
• $$$f(i-1,j)\to f(i,j-1)$$$ (here, $$$i>I$$$, and and the $$$i$$$-th element of $$$A$$$ is -, so the number of numbers in $$$T$$$ less than $$$x$$$ decreases by one.)
• $$$f(i-1,j)\to f(i,j)$$$ (here, the $$$i$$$-th element of $$$A$$$ is + and its $$$x$$$ is greater than $$$X$$$)
• $$$f(i-1,j)\to f(i,j+1)$$$ (here, the $$$i$$$-th element of $$$A$$$ is + and its $$$x$$$ is less than $$$x$$$ or [equal to $$$x$$$ but $i>I$] ) [this is to deal with same elements]

Then we add $$$ans$$$ by $$$X\times \sum_{i\ge 0} f(n,i)$$$.

The time complexity is $$$O(n^3)$$$.

mod=998244353
n=(int)(input())
a=[0 for i in range(n+1)]
for i in range(1,n+1):
	m=input().split()
	if m[0]=="+":
		a[i]=(int)(m[1])
	
ans=0
for t in range(1,n+1):
	if a[t]==0:
		continue
	f=[[0 for i in range(n+2)] for j in range(n+2)]
	f[0][0]=1
	for i in range(1,n+1):
		for j in range(0,i+1):
			if a[i]==0:
				if ((i<=t) or (j>0)):
					f[i][max(j-1,0)]=(f[i][max(j-1,0)]+f[i-1][j])%mod
			else :
				if ((a[i]<a[t]) or ((a[i]==a[t]) and (i<t))):
					f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod
				else :
					f[i][j]=(f[i][j]+f[i-1][j])%mod
			
			if (i!=t) :
				f[i][j]=(f[i][j]+f[i-1][j])%mod
				
			
		
	
	for i in range(0,n+1):
		ans=(ans+f[n][i]*a[t])%mod
	
 
print(ans)

What does lexicographically mean?

Let's first calculate the number of permutation pair $$$(p,q)$$$s (with length $$$i$$$) that $$$p_1<q_1$$$ but $$$inv(p)>inv(q)$$$ ($$$inv(p)$$$ is the number of inversions in $$$p$$$). Call it $$$t_i$$$.

Let's enumerate $$$p_1=j$$$ and $$$q_1=k$$$, then $$$inv(p[2...i])-inv(q[2...i])>k-j$$$. ($$$inv(p)=inv(p[2...i])+j-1,inv(q)=inv(q[2...i])+k-1$$$, with $$$inv(p)>inv(q)$$$ we get the following.)

Precalculate $$$f(i,j)$$$: the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$. Let $$$s(i,j)$$$ be $$$\sum_{k\le j}f(i,k)$$$, then:

$$$f$$$ and $$$s$$$ can be calculated in $$$O(n^4)$$$ or $$$O(n^3)$$$ in the following way: if you insert $$$i$$$ into a permutation of length $$$i-1$$$ after the $$$i-1-p$$$-th element $$$(0\le p\le i-1)$$$, it will bring $$$p$$$ inversions into the permutation. So $$$f(i,j)=\sum_{j-i+1\le k\le j} f(i-1,k)$$$.

After calculating $$$t$$$, calculating the answer it easy. Let $$$ans_i$$$ be the answer for $$$n=i$$$, then

Consider if $$$p_1=q_1$$$. If so, there are $$$i$$$ choices of $$$p_1$$$, and $$$ans_{i-1}$$$ choices of the following $$$n-1$$$ numbers. Otherwise, there are $$$t_i$$$ choices.

Total complexity is $$$O(n^5)$$$, but it can be optimized to $$$O(n^4)$$$ if you consider the difference between $$$j-k$$$ only, and can be optimized to $$$O(n^3\log n)$$$ using FFT with arbitary mod (which we hope can't pass E2!).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,mod,f[55][2005]={1},s[55][2005]={1},ans[55];
int main(){
	cin>>n>>mod;
	for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n*(n-1)/2;j++){
			if(j-i>=0)f[i][j]=(s[i-1][j]-s[i-1][j-i]+mod)%mod;
			else f[i][j]=s[i-1][j];
			s[i][j]=((j?s[i][j-1]:0)+f[i][j])%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int k=j+1;k<=i;k++){
				for(int o=0;o<=(i-1)*(i-2)/2;o++){
					int t=o-(k-j)-1;
					if(t<0)continue;
					ans[i]=(ans[i]+1ll*f[i-1][o]*s[i-1][t]%mod)%mod;
				}
			} 
		}
	}
	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
	cout<<ans[n];
}

In E1 we calculated the number of permutation pairs from the number of permutations. Can we calculate the number of permutation pairs directly?

We recommend you to read E1's editorial first.

Let's directly count the number of permutation pairs $$$(p,q)$$$ of length $$$n$$$ with $$$inv(p)-inv(q)=k$$$, instead of counting it indirectly from "the number of permutation $$$p$$$s of length $$$i$$$ such that $$$inv(p)=j$$$.". Call this number $$$f(n,k)$$$.

We have an $$$n^4$$$ transition: $$$f(n,k)=\sum_{|i|<n} f(n-1,k-i)\times n-|i|$$$ (Consider where to insert $$$n$$$ in the first and second permutation. If the two places are indices $$$(I,J)$$$, then the delta of $$$inv(p)$$$ is $$$n-I$$$, the other is $$$n-J$$$, so the delta of difference is $$$J-I$$$. In $$$[1,n]$$$ there are $$$n-|J-I|$$$ pairs of integers with difference $$$J-I$$$.)

Let's speed it up. When $$$f(n,k)$$$ moves to $$$f(n,k+1)$$$, it looks like this: ($$$n=4$$$, as an example)

• $$$f(n-1,k-3)\times 1+f(n-1,k-2)\times 2+f(n-1,k-1)\times 3+f(n-1,k)\times 4+f(n-1,k+1)\times 3+f(n-1,k+2)\times 2+f(n-1,k+3)\times 1$$$
• $$$f(n-1,k-2)\times 1+f(n-1,k-1)\times 2+f(n-1,k)\times 3+f(n-1,k+1)\times 4+f(n-1,k+2)\times 3+f(n-1,k+3)\times 2+f(n-1,k+4)\times 1$$$

So with prefix sums $$$s$$$ ($$$s(i,j)=\sum_{k\le j} f(i,k)$$$) we can write $$$f(n,k+1)=f(n,k)-(s(n-1,k)-s(n-1,k-n))+(s(n-1,k+n)-s(n-1,k))$$$.

Note that the second indice of the array might be negative, so we should shift it by $$$130000$$$.

The memory complexity is $$$O(n^3)$$$, so we should only keep two layers of transition to optimize it to $$$O(n^2)$$$ (If implemented well, $$$O(n^3)$$$ memory solutions can also pass.)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B=130000;
int n,mod,w[2][2*B+5],s[2][2*B+5],ans[505];
int main(){
	cin>>n>>mod;
	w[0][B]=s[0][B]=1;
	for(int i=B;i<=2*B;i++)s[0][i]=1;
	for(int i=1;i<=n;i++){
		int curs=1,I=i&1,J=I^1;
		memset(w[I],0,sizeof(w[I])),memset(s[I],0,sizeof(s[I]));
		for(int u=i*(i-1)/2,j=-u+B;j<=u+B;j++){
			w[I][j]=curs;
			curs=(0ll+curs-s[J][j]+s[J][j-i]+s[J][j+i]-s[J][j]+2ll*mod)%mod;
		}
		for(int j=B-i*(i-1)/2,v=(i+2)*(i+1)/2+B;j<=v;j++)s[I][j]=(s[I][j-1]+w[I][j])%mod;
		for(int j=1;j<i;j++)ans[i]=(ans[i]+1ll*(s[J][(i+1)*i/2+B]-s[J][j+B]+mod)%mod*(i-j))%mod;
	}
	for(int i=2;i<=n;i++)ans[i]=(ans[i]+1ll*i*ans[i-1])%mod;
	cout<<ans[n];
}