#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n;
int a[N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++) printf("%d%c",a[i]*(i&1?1:-1),i==n?'\n':' ');
	}
	
	//fclose(stdin);
	return 0;
}

We just sort the array and set $$$a_i:=-a_i$$$ for all even $$$i$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                string s;
                int k;
                cin >> s >> k;

                int n = (int)s.length();
                int mn = n - k;
                for (int i = n - k - 1; i >= 0; i--) {
                        if (s[i] > s[i + k]) {
                                mn = i;
                        }       
                }

                string ans = s.substr(0, mn) + s.substr(mn + k);

                cout << ans << '\n';
        }
        
        return 0;
}

We will solve this problem by using the sliding window trick. Let's assume $$$s_{i,j}$$$ as the substring inside $$$s$$$ from the $$$i$$$-th character to the $$$j$$$-th character from the left of the string $$$s$$$. First, create a window from the segment $$$[1,k]$$$ denoting the deletion window, which means $$$x=s_{k+1,|s|}$$$ for now. Now, we will slide this window by one index to the right each time and check if the new string formed by concatenating characters not covered by the window after sliding is weaker than current weakest string before sliding.

Notice that when we slide the window from the segment $$$[i,i+k-1]$$$ to $$$[i+1,i+k]$$$, the only difference between the resulting string from both deletion window result is the $$$i$$$-th character. Or more specifically, we override the $$$i$$$-th character in the result from $$$s_{i+k,i+k}$$$ to $$$s_{i,i}$$$. Furthermore, if $$$s_{i+k,i+k}$$$ is lexicographically smaller (or weaker) than $$$s_{i,i}$$$, that means the resulting string from all the deletion window placement after sliding it to the right from the segment $$$[i,i+k-1]$$$ will never be weaker than when the window is at the segment $$$[i,i+k-1]$$$, which means it is enough to keep sliding the deletion window to the right up until the point where $$$s_{i+k,i+k} \lt s_{i,i}$$$. Then, delete the segment $$$[i,i+k-1]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int  T,n,k,ans;
int  p[N],d[N],pre[N];
int  dp[N][2];

int main()
{
	//freopen("test.in","r",stdin);
	
	T=1;
	//scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    	for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    	ans=0;
    	pre[0]=k; 
	    for(int i=1;i<=n;i++)
	    {
    		if((d[i]&&pre[i-1]>=1900)||((!d[i])&&pre[i-1]<=2100)) pre[i]=(p[i]-pre[i-1])/4+pre[i-1];
			else pre[i]=pre[i-1];
    	}
    	ans=max(pre[n-1],pre[n]);
    	for(int i=0;i<=4000;i++) dp[i][(n+1)&1]=i;
    	for(int i=n;i>=2;i--)
    	{
			for(int j=0;j<=4000;j++) 
			{
				if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[j][i&1]=dp[(p[i]-j)/4+j][(i+1)&1];
				else dp[j][i&1]=dp[j][(i+1)&1];
			}
			ans=max(ans,dp[pre[i-2]][i&1]);
	    }
    	/*for(int i=0;i<=4000;i++) dp[n+1][i]=i;
    	for(int i=n;i;i--)
    	{
	    	for(int j=0;j<=4000;j++)
	    	{
	    		if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[i][j]=dp[i+1][(p[i]-j)/4+j];
	    		else dp[i][j]=dp[i+1][j];
	    	}
	    }
	    ans=dp[1][k];kk=k;
	    for(int i=1;i<=n;i++)
	    {
    		ans=max(ans,(int)dp[i+1][k]);
    		if((d[i]&&k>=1900)||((!d[i])&&k<=2100)) k=(p[i]-k)/4+k;
    	}*/
    	printf("%d\n",k-ans);
	}
	
	//fclose(stdin);
	return 0;
}

The key to solving the problem is to notice that $$$k$$$ is small ($$$k \leq 4000$$$).The intended solution is $$$O(nk)$$$.

We note $$$dp_{i,j}$$$ as the final rating when current score is $$$j$$$, participating in the $$$i, i+1,...,n_{th}$$$ contest.

We can enumerate the skipped contest and update the answer with the $$$dp$$$ array.

To avoid exceeding the memory limit, you need to use a scrolling array.

/**
 *  @the_hyp0cr1t3
 *  30.07.2023 20:42
**/
#include <bits/stdc++.h>

template <int P> struct modint {
    static int mod_;
    int v;

    constexpr modint() : v{} {}
    constexpr modint(long long u) {
        if (u < 0) u = u % get_mod() + get_mod();
        if (u >= get_mod()) u %= get_mod();
        v = u;
    }

    constexpr int val() const { return v; }
    constexpr static int get_mod() {
        if constexpr (P > 0)
            return P;
        else
            return mod_;
    }
    constexpr static void set_mod(int m) {
        mod_ = m;
    }
    explicit constexpr operator int() const { return v; }
    friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
        long long u; in >> u;
        m = modint(u);
        return in;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
        return os << m.v;
    }

    static int inv(int a, int m) {
        int g = m, x = 0, y = 1;
        while (a != 0) {
            int q = g / a;
            g %= a;
            std::swap(g, a);
            x -= q * y;
            std::swap(x, y);
        }
        return x < 0 ? x + m : x;
    }

    constexpr static unsigned fast_mod(uint64_t x, unsigned m = get_mod()) {
#if !defined(_WIN32) || defined(_WIN64)
        return unsigned(x % m);
#endif  // x must be less than 2^32 * m
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
        asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
        return rem;
    }

    constexpr modint inv() const { return modint(inv(v, get_mod())); }
    constexpr modint operator-() const { return modint(v ? get_mod() - v : 0); }
    constexpr modint& operator+=(const modint& o) {
        v += o.v;
        if (v >= get_mod()) v -= get_mod();
        return *this;
    }
    constexpr modint& operator-=(const modint& o) {
        v -= o.v;
        if (v < 0) v += get_mod();
        return *this;
    }
    constexpr modint& operator*=(const modint& o) {
        v = fast_mod(uint64_t(v) * o.v);
        return *this;
    }
    constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
    friend constexpr modint operator+(const modint& a, const modint& b) {
        modint res = a; res += b;
        return res;
    }
    friend constexpr modint operator-(const modint& a, const modint& b) {
        modint res = a;
        res -= b;
        return res;
    }
    friend constexpr modint operator*(const modint& a, const modint& b) {
        modint res = a;
        res *= b;
        return res;
    }
    friend constexpr modint operator/(const modint& a, const modint& b) {
        modint res = a;
        res /= b;
        return res;
    }
    friend constexpr bool operator==(const modint& a, const modint& b) {
        return a.val() == b.val();
    }
};

template <typename T>
constexpr T expo(T A, long long B) {
    T res{1};
    while (B) {
        if (B & 1) res *= A;
        B >>= 1;
        A *= A;
    }
    return res;
}

template <>
int modint<0>::mod_ = 1;

constexpr int mod = 1'000'000'007;
using Z = modint<mod>;
// using Z = double;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    std::cin >> tests;
    while (tests--) {
        int n;
        std::array<Z, 3> p;
        std::cin >> n;
        int pmx = -1;
        for (int k : {2, 1, 0}) {
            std::cin >> p[k];
            pmx = std::max(pmx, p[k].val());
            p[k] /= 100;
        }

        if (pmx == 100) {
            std::cout << (n == 1 ? 0 : -1) << '\n';
            continue;
        }

        --n;

        auto P = p;
        std::array<Z, 2> ans{};
        std::array<std::vector<std::array<Z, 2>>, 3> dp;
        for (int k : {0, 1, 2}) {
            dp[k].reserve(n + 1);
            dp[k].push_back({0, p[k]});
        }

        for (int i = 1; i <= n; i++) {
            ans = {};
            for (int k : {0, 1, 2}) {
                for (int j = 0; j < i; j++) {
                    Z mul = p[(k + 1) % 3] * (i + 1) / (i - j);
                    for (int t : {0, 1}) {
                        dp[k][j][t] *= mul;
                        ans[t] += dp[k][j][t];
                    }
                }
            }
            ans = {(1 + ans[0]) / ans[1], 1};
            for (int k : {0, 1, 2}) {
                P[k] *= p[k];
                dp[k].push_back({});
                for (int t : {0, 1})
                    dp[k][i][t] = ans[t] * P[k];
            }
        }

        std::cout << ans[0] << '\n';
    }

}

For convenience, let $$$A=\frac{a}{100}$$$, $$$B=\frac{b}{100}$$$, $$$C=\frac{c}{100}$$$.

First, let's deal with some corner cases. When $$$n=1$$$, the answer is $$$0$$$. When $$$[A=0] + [B=0] + [C=0] = 2$$$, the answer is $$$-1$$$, because no one can leave if only one move is possible. Make sure to deal with these two cases in this particular order, because the answer when $$$n=1$$$ and $$$[A=0] + [B=0] + [C=0] = 2$$$ are both satisfied is $$$0$$$.

Then, let's solve the problem with DP. Let $$$f_i$$$ be the expected number of rounds it takes to result in $$$1$$$ person, starting from $$$i$$$ people. In the base case, we have $$$f_1 = 0$$$. Then, the transition would be:

where $$$P(i, j)$$$ is the probability of transitioning from $$$i$$$ people to $$$j$$$ people in one round. Rearranging, that is,

$$$P(i, i)$$$ basically translates to the probability of having one type or three types of moves in the room in one round. Thus,

To calculate $$$P(i, j)$$$ where $$$i \gt j$$$, we can also count cases in which $$$j$$$ winning moves and $$$i - j$$$ losing moves are made. That is,

Then, our answer would just be $$$f_n$$$.

Overall, the complexity is $$$O(n^2\log n)$$$ if techniques like fast-power are used to calculate the powers and combination values. However, the constant can be very big. By precomputing these values, the complexity would be $$$O(n^2)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=63;
const ll  TMD=0;
const ll  INF=2147483647;
int T;
ll  n,k,ans;
int dif[N];
ll  f[LOGN][LOGN][2];
vector<int> v;

void init()
{
	f[0][0][0]=f[1][0][0]=f[1][0][1]=1;
	for(int i=2;i<LOGN;i++)
	{
	    for(int j=0;j<i;j++)
	    {
	        for(int k=0;k<=1;k++) 
	        {
				f[i][j][k]=f[i-1][j][k];
				if(j) f[i][j][k]+=f[i-1][j-1][k^1];
	        }
	    }
	}
		
}

void DP(int bt)
{
	if(bt<0) 
	{
		ans+=(dif[0]==k);
		return ;
	}
	if(v[bt])
	{
		if(bt==(int)v.size()-1) 
		{
			for(int i=bt;i;i--) ans+=f[i][k][1];
		}
		else 
		{
			int diff=dif[bt+1]+v[bt+1];
			if(k-diff>=0)   ans+=f[bt][k-diff][0];
			if(k-diff-1>=0) ans+=f[bt][k-diff-1][1];
		}
	}
	DP(bt-1);
}

int main()
{
	//freopen("test.in","r",stdin);
	
	init();
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%I64d%I64d",&n,&k);
    	v.clear();
    	while(n) v.push_back(n&1),n>>=1;
    	dif[(int)v.size()-1]=0;
    	for(int i=(int)v.size()-2;i>=0;i--) dif[i]=dif[i+1]+(v[i]^v[i+1]);
    	ans=0;
    	DP((int)v.size()-1);
		printf("%I64d\n",ans%1000000007); 
	}
	
	//fclose(stdin);
	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,tt,ans;
int t[N],s[N],dt[N],ds[N];
int dp[N][N];

int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d",&n,&tt);
    	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&t[i],&s[i],&dt[i],&ds[i]);
    	ans=0;
    	for(int i=1;i<=tt;i++)
    	{
    		vector<pair<int,int> > v;
	    	for(int j=1;j<=n;j++) 
			{
				if(i+dt[j]>tt) v.push_back(make_pair(s[j],j));
				else           v.push_back(make_pair(ds[j],j));
			}
			sort(v.begin(),v.end());
			for(int j=1;j<=n;j++)
				for(int k=0;k<=i;k++)
					dp[i][j]=-INF;
			dp[0][0]=0;
			for(int j=1;j<=n;j++)
			{
				int num=v[j-1].second;
				if(i-t[num]>=0) ans=max(ans,dp[j-1][i-t[num]]+s[num]-v[j-1].first);
				for(int k=0;k<=i;k++)
				{
					dp[j][k]=dp[j-1][k];
					if(k-t[num]>=0) dp[j][k]=max(dp[j][k],dp[j-1][k-t[num]]+s[num]);
				}
			}
	    }
    	printf("%d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Consider:for a fixed problem set you choose,which problem will the hacker hack?

For problem $$$i$$$,$$$f_i \leq T-Σt$$$,hack it will decrease you score by $$$p_i$$$.

However,for problem $$$i$$$,$$$f_i \gt T-Σt$$$,hack it will decrease you score by $$$a_i$$$,since you don't have enough time to fix the bug.

Note $$$decrease_i$$$ as the score that actually decreased for the i-th hacked problem.Hacker'll hack the problem with the max $$$decrease$$$ value.

We find $$$decrease$$$ is depend on the value of $$$Σt$$$.

Enumeration $$$Σt$$$ from $$$0$$$ to $$$T$$$,calculate the corresponding $$$decrease$$$,then do classic knapsack DP.It's $$$O(n^2T)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n,k,ls,lt;
ll  ans;
int x[N],a[N],S[N],s[N],t[N],nxt[N];
vector<int> p;

//

void build_nxt(int s[],int l)
{
	for(int i=1;i<l;i++)
	{
		int j=i;
		while(s[nxt[j-1]]!=s[i]&&j!=0) j=nxt[j-1];
		nxt[i]=(s[i]==s[nxt[j-1]])?nxt[j-1]+1:0;
	}
	//for(int i=0;i<l;i++) printf("%d ",nxt[i]);
	//printf("\n");
}

void KMP(int s[],int t[],int ls,int lt,vector<int> &v)
{
	build_nxt(t,lt);
	int ps=0,pt=0;
	while(1)
	{
		if(pt>=lt) 
		{
			v.push_back(ps-lt);
			pt=nxt[pt-1];
		}
		if(ps==ls) break;
		while(s[ps]!=t[pt])
		{
			if(!pt) break;
			else pt=nxt[pt-1];
		}
		if(s[ps]==t[pt]) ps++,pt++;
		else ps++,pt=0;
	}
}

//

//

ll md(ll a,ll b)	//a mod b
{
	if(a>0) return a%b;
	return (-(-a)%b+b)%b;	
}
		
void exgcd(ll &x,ll &y,ll a,ll b){
    if(!b){
        x=1;y=0;
        return ;
    }
    exgcd(x,y,b,a%b);
    ll xx=x,yy=y;
    x=yy;y=xx-(a/b)*yy;
}

ll solve_equation(ll a,ll b,ll k)	//solve ax=b(mod k),x>=0 and x is minimal
{
	ll x,y,g;
	md(a,k);md(b,k);
	exgcd(x,y,a,k); 	//ax+ky=gcd(a,k)
	g=a*x+k*y;
	if(b%g) return -1;
	return md(x*(b/g),k/g);
}

int check()
{
	for(int i=1;i<=n;i++) if(x[i]%k) return 0;
	return 1;
}

//


int main()
{
	//freopen("test.in","r",stdin);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++)  scanf("%d",&x[i]);
    	for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    	if(check())
		{
			printf("0\n");
			continue;
		} 
    	for(int i=1;i<=n;i++)  S[i]=(S[i-1]+a[i])%k;
 		ls=2*n-2;lt=n-1;
 		for(int i=1;i<n;i++)   s[i-1]=a[i+1]%k;
 		for(int i=n;i<2*n;i++) s[i-1]=a[i-n+1]%k;
 		for(int i=1;i<n;i++)   t[i-1]=md(a[i]+x[i]-x[i+1],k);
 		p.clear();
    	KMP(s,t,ls,lt,p);
    	ans=INF*INF;
    	for(int i=0;i<p.size();i++)
    	{
	    	ll y=x[1]+S[1+p[i]],sol=solve_equation(S[n],-y,k);
	    	if(sol==-1) continue;
	    	ans=min(ans,sol*n+p[i]+1);
	    }
	    if(ans==INF*INF) printf("-1\n");
	    else printf("%I64d\n",ans);
	}
	
	//fclose(stdin);
	return 0;
}

Let's say $$$t = nm+p (0 \leq p \lt n)$$$ and $$$S$$$ is sum of all $$$a_i$$$.

We get $$$x_i + a_i + ... + a_{i + p} = x_{i + 1} + a_{i + 1} + ... + a_{i + p + 1}=-Sm (mod k)$$$

Thus $$$x_i + a_i = x_{i + 1} + a_{i + p + 1} (mod k)$$$ for $$$1\leq i \leq n-1$$$.

So we need to find $$$a_i + x_i - x_{i + 1}$$$ shifted in $$$a$$$, this is KMP.

Assume we have known $$$p$$$.Note $$$v=x_i + a_i + ... + a_{i + p}$$$,we also need $$$v+Sm=0(mod k)$$$.Use exgcd to get $$$m$$$.

Complexity:$$$O(n log n)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> a(n);
                vector<int> b(n);

                for (int i = 0; i < n; i++) cin >> a[i];
                for (int i = 0; i < n; i++) cin >> b[i];

                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int x, int y) {
                        if (b[x] == b[y]) return a[x] > a[y];
                        return b[x] == 1;
                });

                int ans = a[0] * b[0];
                int suma = 0, sumb = 0;

                for (int i = 0; i < n; i++) {
                        suma += a[ord[i]];
                        sumb += b[ord[i]];

                        ans = max(ans, suma * sumb);
                        ans = max(ans, a[i] * b[i]);
                }

                cout << ans << '\n';
        }

        return 0;
}

Consider greedy algorithm.

When all $$$b_i(1 \leq i \leq n)=-1$$$,obviously,the answer is $$$-min(a_i)$$$.

Otherwise,we choose all tuples which's $$$b_i=1$$$ firstly.Then choose tuples in descending order of $$$a_i$$$ value which's $$$b_i=-1$$$.The answer is the maximum in this process.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> ca(2 * n);
                vector<int> cb(2 * n);

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        ca[x] += 1;
                }

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        cb[x] += 1;
                }

                bool ok = 1;

                for (int i = 0; i < 2 * n; i++) {
                        if (ca[i] + cb[i] > n) {
                                ok = 0;
                        }
                }

                cout << (ok ? "YES" : "NO") << '\n';
        }
        
        return 0;
}

Note $$$k$$$ is the number with the highest sum of occurrences in $$$s$$$ and $$$t$$$.The answer is "YES" iff $$$occurrences(k) \leq n$$$.

If $$$occurrences(k) \gt n$$$,it means the total of numbers that are not $$$k$$$ is less than $$$n$$$.Obviously the answer is "NO".

Otherwise,we can use Mathematical induction to prove that there is a solution:

• 1.For two empty sets $$$s$$$,$$$t$$$,$$$occurrences(k) \leq n$$$ holds;

• 2.Assume for two empty sets $$$s$$$,$$$t$$$ if size $$$n$$$,$$$occurrences(k) \leq n$$$ holds.We do remove a $$$k$$$ from one set and remove a number which is not $$$k$$$ from another set.After that,the size becomes $$$n-1$$$,and $$$occurrences(k) \leq n-1$$$ holds.

#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
using namespace std;
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define PI acos(-1)
#define pii pair<int,int>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define len(s) (int)s.size()
#define F first
#define S second
const int mod=1e9+7;
int dp[20001][101][101];
int a[101];
const int add=10000;
const int L=-10000;
const int R=10000;
int f(int sum,int l,int r)
{
	//count number of non-empty subsequence of subarray [l,r] 
	//with adding=sum
	if( !(sum>=L and sum<=R))
		return 0;
	
	if(l==r)
	{

		if(sum==a[l])
			return 1;
		return 0;
	}
	if(dp[sum+add][l][r]!=-1)
		return dp[sum+add][l][r];
	int ans1=f(sum,l,r-1);
	int ans2=f(sum,l+1,r);
	int rem=0;
	if(l+1<=r-1)
		rem=f(sum,l+1,r-1);
	int ans3=0;
	if(l+1<=r-1)
		ans3=f(sum-a[l]-a[r],l+1,r-1)+(sum==(a[l]+a[r]));
	else
		ans3=(sum==(a[l]+a[r]));
	
	return dp[sum+add][l][r]=(((ans1+ans2)%mod-rem+mod)%mod+ans3)%mod;
}
void solve()
{
	int n,x;
	cin>>n>>x;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n<3)
	{
		cout<<0;
		return ;
	}
	else
	{
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
			a[i]-=x;
		int ans=0;
	
		for(int i=1;i<=n;i++)
		{
			for(int j=i+2;j<=n;j++)
			{
				ans+=f(0,i+1,j-1);
				ans%=mod;
			}
		}
		cout<<ans;
	}
}
signed main()
{
fastio
int TestCases=1;
//cin>>TestCases;
while(TestCases--)
{
solve();
cout<<endl;
}
}

Firstly,we substract all $$$a_i$$$ by $$$x$$$.Then the problem is equivent to count the number of subsequences which's sum is $$$0$$$.

Consider sort the array and do DP.Note $$$dp_{l,r,s}$$$ as the number of subsequences with $$$a_l$$$ as the head, $$$a_r$$$ as the tail, and $$$s$$$ as the sum.

For $$$dp_{l,r,0}(2\leq l \leq r \leq n-1)$$$,it's contribution is $$$dp_{l,r,0}*(l-1)*(n-r)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> fac(2222222);

        fac[0] = 1;
        for (int i = 1; i <= 2000000; i++) {
                fac[i] = (fac[i - 1] * i) % MOD;
        }

        auto binpow = [&](int x, int y) {
                int res = 1;

                while (y > 0) {
                        if (y & 1) (res *= x) %= MOD;

                        (x *= x) %= MOD;
                        y >>= 1;
                }

                return res;
        };

        vector<int> inv(2222222);

        inv[2000000] = binpow(fac[2000000], MOD - 2);
        for (int i = 1999999; i >= 0; i--) {
                inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }

        auto comb = [&](int n, int r) {
                if (n < r) {
                        cout << "hi\n";
                        exit(0);
                }
                return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
        };

        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;
                // general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
                int ans = comb(m - 1, n - 1);

                if (n - 1 <= m - (m + 1) / 2) {
                        ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
                }

                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        
        return 0;
}

As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i) \lt \lceil m/2 \rceil$$$.

What's the number of arrays satisfying the following condition?

• 1.All $$$a_i$$$ are positive integers;

• 2.$$$\Sigma a_i=m$$$.

The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.

$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.

We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.

The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.

The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m, s;
                cin >> n >> m >> s;

                set<pair<int, int>> st;
                st.insert({s, 0});

                for (int i = 0; i < m; i++) {
                        int l, r;
                        cin >> l >> r;

                        vector<pair<int, int>> del;
                        int mnl = INFF, mnr = INFF;
                        for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
                                if (it->fi > r) break;

                                if (l - 1 >= 1) {
                                        mnl = min(mnl, it->se + it->fi - l + 1);
                                }

                                if (r + 1 <= n) {
                                        mnr = min(mnr, it->se + r + 1 - it->fi);
                                }

                                del.push_back(*it);
                        }
                        
                        for (auto p : del) st.erase(p);

                        auto it = st.lower_bound({l - 1, 0});
                        if (it != st.end() && it->fi == l - 1) {
                                mnl = min(mnl, it->se);
                                st.erase(it);
                        }

                        auto it2 = st.lower_bound({r + 1, 0});
                        if (it2 != st.end() && it2->fi == r + 1) {
                                mnr = min(mnr, it2->se);
                                st.erase(it2);
                        }

                        if (l - 1 >= 1) {
                                st.insert({l - 1, mnl});
                        }

                        if (r + 1 <= n) {
                                st.insert({r + 1, mnr});
                        }
                }

                int ans = INFF;

                for (auto [pos, cost] : st) {
                        ans = min(ans, cost);
                }

                cout << ans << '\n';
        }
        
        return 0;
}

The original idea of this problem is using segment tree, hence the $$$n \leq 2\cdot 10^5$$$ constraint. However, this problem can be solved easier by using std::set.

For this problem, we can do DP to solve the problem.

Define $$$dp_i$$$ after the $$$j$$$-th attack as minimum energy needed to avoid the first $$$j$$$ attacks and we ended up at tile $$$i$$$. If we try updating all $$$n$$$ indices for each attack (by doing $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ for all $$$1 \leq j \leq n$$$), that will cost $$$O(n)$$$ transition, which means the complexity will be $$$O(n^2m)$$$ per test case. Since it's too slow, we need some observation.

Observation. For the $$$k$$$-th attack, we only need to update two DP indices each attack and it's optimal to do $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ where $$$i=l_k-1$$$ or $$$i=r_k+1$$$ (if those two indices actually exist inside the range $$$[1,n]$$$) and $$$l_k \leq j \leq r_k$$$

Proof. Assume that everytime the boss attacks, it is sometimes optimal for us to move if we didn't stand inside the incoming lazer previously. So, assume at some point, we went to the right $$$y$$$ tiles as the "optimal" route. Then, there are three cases for the next attack:

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(x \gt y)$$$. In this case, the current optimal is not the same as the previous optimal, since we could've just not move in previous turn and then move to the left by $$$x-y$$$ tiles.

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(0 \lt x \leq y)$$$. In this case, the current optimal is also not the same as the previous optimal, since we could've just not move in previous turn and then move to the right by $$$y-x$$$ tiles.

• The current optimal route involves going to the right by $$$x$$$ tiles $$$(x \geq 0)$$$. In this case, there is an alternative solution, where we could've just not move in previous turn and then move to the right by $$$x+y$$$ tiles. It'll result with the same energy spent.

So, it is optimal to do nothing if we don't stand inside the lazer.

If we do stand inside the lazer (assume it's the $$$j$$$-th lazer), it is optimal to go to either $$$l_j-1$$$ or $$$r_j+1$$$, since with the same idea as above, one of these tiles are either the most optimal solution, or one of the most optimal solution (think of it like a waterfall :]).

Now, with this in mind, we can implement this in $$$O(n\sum_{i=1}^n (r_i-li))$$$ per test case. Since it's still too slow, we can optimize it again. Notice that for each attack, we're only interested from the updates that actually give paths, not the one getting blocked by the lazer. So, we will try to implement this using C++ std::set. First, create the set $$$route$$$ which stores all previously updated $$$dp$$$ indices that give paths (since we update the tiles that will get hit by the lazer for each attack to $$$INF$$$ again after updating $$$dp{li-1}$$$ and $$$dp{r_i+1}$$$). Set $$$dp_i=INF$$$ for all $$$1 \leq i \leq n,i \neq s$$$, $$$dp_s=0$$$, and . Then, do the following for the j-th attack:

• Find all the element $$$k$$$ in $$$route$$$ such that $$$l_j \leq k \leq rj$$$.

• For each of the element satisfying the constraint above, update $$$dp{lj-1}$$$ to $$$\min(dp{l_j-1},dp_k+k-lj+1)$$$ and $$$dp{rj+1}$$$ to $$$\min(dp{r_j+1},dp_k+r_j+1-k)$$$

• Set all $$$dp_k$$$ to $$$INF$$$, remove all elements satisfying the constraint above, and then add $$$l_j-1$$$ and $$$r_j+1$$$ to $$$route$$$

The time complexity of this would be $$$O(m\log m)$$$ with $$$O(n)$$$ initializer and $$$O(n)$$$ finding optimal of each $$$dp$$$ index for each test case.

To optimize this even further, notice that after all the $$$m$$$ attacks, every index outside the $$$route$$$ would have the value of $$$INF$$$, so we only need to check the minimum from all $$$dp$$$ with indices inside $$$route$$$ (which is $$$O(m)$$$) and only to reset those indices as well for the next test case (which is also $$$O(m)$$$).

Once again, beware of the fact that $$$l_i-1$$$ or $$$r_i+1$$$ might be out of the arena range.

Time complexity: $$$O(m\log m)$$$

Bonus: Solve the problem if $$$n \leq 10^9$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<bool> ok(22222, 0);

        auto conv = [&](int x) {
                int res = 0;

                while (x > 0) {
                        int y = x % 10;

                        res += y * y;
                        x /= 10;
                }

                return res;
        };

        for (int i = 1; i <= 16200; i++) {
                int x = i;

                set<int> vis;
                
                while (!vis.count(x)) {
                        vis.insert(x);

                        int y = conv(x);
                        if (x == y) {
                                ok[i] = 1;
                        }
                        x = y;
                }
        }
        
        vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
        dp[0][0] = 1;

        for (int i = 1; i <= 200; i++) {
                for (int j = 0; j < 20000; j++) {
                        for (int k = 0; k <= 9; k++) {
                                dp[i][j + k * k] += dp[i - 1][j];
                                dp[i][j + k * k] %= MOD;
                        }
                }
        }

        int t;
        cin >> t;

        while (t --> 0) {
                string l, r;
                cin >> l >> r;

                auto calc = [&](string s, bool on) {
                        int res = 0;
                        int n = (int)s.length();
                        int cur = 0;

                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < s[i] - '0'; j++) {
                                        for (int k = cur + j * j; k <= 16200; k++) {
                                                res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
                                                res %= MOD;
                                        }
                                }
                                cur += (s[i] - '0') * (s[i] - '0');
                        }

                        if (ok[cur] && on) res += 1;

                        return res;
                };
                
                int ans = calc(r, 1) - calc(l, 0);
                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        return 0;
}

Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.

We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.

Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).

It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long
const int bk=500;
namespace sumadd {
   int tag[bk],pb[bk],pre[bk][bk];
   void addib(int l,int r,int id,int v) {
      for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
      tag[id]=0;
   }
   void add(int l,int r,int v) {
      if(l/bk==r/bk) {
         addib(l%bk,r%bk,l/bk,v);
         for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
         return;
      }
      if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
      if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
      while(l<=r) {tag[l/bk]+=v;l+=bk;}
      for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
   }
   int sum(int l,int r) {
      if(l/bk==r/bk) {
         return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
      }
      int sum=0;
      if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
      if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
      sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
      return sum;
   }
   void cln() {
      for(int i=0;i<bk;++i) {
         tag[i]=pb[i]=0;
         for(int j=0;j<bk;++j)
            pre[i][j]=0;
      }
   }
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
   int n,m,q;
   cin >> n >> m >> q;
   for(int i=1,l,r;i<=m;++i) {
      cin >> l >> r;
      ivl[i/bk][i%bk]={l,r};
      lp.push_back(lp.end()[-1]+r-l+1);
   }
   cerr << endl;
   lp.push_back(2147483647);
   for(int i=1,o,l,r,v;i<=q;++i) {
      cin >> o >> l >> r;
      if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
      else {
         auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
         qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
         if(qry[i][1]==qry[i][2]+2) {
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            l-=*prev(il);r-=*prev(il);
            ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
            flag[i]=true;
            continue;
         }
         if(qry[i][1]==qry[i][2]+1) {
            ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
            ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
            flag[i]=true;
            continue;
         }
         if(il!=lp.begin()) {
            int p=qry[i][1]-1;l=*il-l+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.second+1-l,t.second);
         }
         if(next(ir)!=lp.end()) {
            r-=*ir;
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.first,t.first+r-1);
         }
         if(flag[i]) ans[i]=-ans[i];
      }
   }
   sumadd::cln();
   for(int k=0;k<bk;++k) {
      int sum=0;
      for(int i=0;i<bk;++i) {
         auto t=ivl[k][i];
         if(t==pair<int,int>{0,0}) continue;
         cnt[t.first]++;
         cnt[t.second+1]--;
      }
      for(int j=1;j<=2;++j)
         for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
      for(int i=1;i<=q;++i)
         if(qry[i][0]==1) {
            sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
         }
         else
            if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
      for(int i=1;i<=n;++i) cnt[i]=0;
   }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==1)
         sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
      else {
         if(flag[i]) continue;
         int l=qry[i][1],r=qry[i][2];
         if(l>r) continue;
         if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
            for(int j=l;j<=r;++j) {
               auto t=ivl[j/bk][j%bk];
               ans[i]+=sumadd::sum(t.first,t.second);
            }
            continue;
         }
         while(l%bk!=0)    {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
         while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
      }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==2)
         cout << ans[i] << ' ';
   cout << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Consider SQRT decomp for $$$[l_i,r_i]$$$, putting each $$$sqrt(n)$$$ of $$$[l_i,r_i]$$$ into a block, and maintaining the sum of the group, and the number of occurrences in the block in each original array $$$a_i$$$.

Enumerate all blocks, and if a query completely contains an sqrt, then +=sum is added to the result of the query.

If we add, then sum+= the number of times the number * added value. (This can be done with two times perfix sums)

For queries that are not complete blocks, consider direct brute force maintenance of the A-array and query, it has $$$n^{1.5}$$$ query operations and n modification operations, so we can use a partitioned data structure to do $$$O(1)$$$ queries, $$$O(n^{0.5})$$$ modifications.

So, the total complexity is $$$O(n^{1.5})$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long

const int MOD=998244353;
void Delta() {
   int a,b,c,d;
   cin >> a >> b >> c >> d;
   cout << (a+b>c+d?"YES":"NO") << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The probability of Alice's winning is strictly higher than Bob's iff $$$l_1+r_1 \gt l_2+r_2$$$.

Submitting this code directly will get ILE, please delete cerr and submit.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
namespace Fact {
   vector<char> isPrime;
   vector<int> Prime,OneFac;
   void GetPrime(int n){for(int i=0;i<n;++i)isPrime[i]=1;isPrime[1]=1;for(int i=2;i<=n;i++){if(isPrime[i])Prime.push_back(i);for(int j:Prime){if(i*j>n) break;isPrime[i*j]=0;OneFac[i*j]=j;if(i%j==0)break;}}}
   void Fac_dfs(int x,int y,vector<int>& ans,vector<pair<int,int>>& FacList){if(x==(long long)(FacList.size())){ans.push_back(y);return;}int k=1;for(int i=0;i<=FacList[x].second;++i){Fac_dfs(x+1,y*k,ans,FacList);k*=FacList[x].first;}}
   vector<pair<int,int>>GetPrimeFac(int a){vector<pair<int,int>>answer;if(isPrime[a])return(vector<pair<int,int>>{pair<int,int>{a,1}});answer.push_back({OneFac[a],1});a/=OneFac[a];while(!isPrime[a]){if(OneFac[a]==answer.back().first)answer.back().second++;else answer.push_back({OneFac[a],1});a/=OneFac[a];}if(a==answer.back().first)answer.back().second++;else answer.push_back({a,1});return(answer);}
   vector<int>GetFacList(int a){vector<int> ans;vector<pair<int,int>>FacList=GetPrimeFac(a);Fac_dfs(0,1,ans,FacList);return(ans);}
   void init(int n){isPrime.resize(n+2);OneFac.resize(n+2);GetPrime(n);}
   void init(){init(10000005);}
};
#define int long long

const int MOD=998244353;
void Delta() {
   int a,b;
   cin >> a >> b;
   if(Fact::isPrime[a]||(a/Fact::OneFac[a]<b)) cout << "NO" << endl;
   // in code "OneFac" is The smallest non-1 factor.
   else {
      cout << "YES" << endl;
      for(int i=1;i<b;++i) cerr << Fact::OneFac[a] << ' ';
      cerr << a-(b-1)*Fact::OneFac[a] << endl;
   }
}
signed main() {
   Fact::init(100001);
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Let's say we finally get the gcd $$$x$$$, so all $$$a_i$$$ are multiples of $$$x$$$.

We want all $$$a_i$$$to be positive, so every $$$a_i$$$ is at least $$$x$$$, and all sums are at least $$$kx$$$ and sum is divisible by $$$x$$$ (You have some $$$a_i$$$ that is divisible by $$$x$$$, add it up, and it's still divisible by $$$x$$$).

Since we already know sum (is $$$n$$$), $$$x$$$ can only be a factor of $$$n$$$, Since $$$x \gt 1$$$, just to take the smallest non-1 factor of $$$n$$$ and check. If $$$kx$$$ is less than $$$n$$$, then just put all the rest on $$$a_k$$$, which still guarantees that gcd=x.

(The constructional output is given in cerr of code for help understand)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
int n,m,sum;
map<int,int> a,b,c;
vector<pair<int,int>> Q;
void dfs(int idx,int A,int B,int C) {
   if(idx==(int)Q.size()) {
      sum+=a[A]*b[B]*c[C];
      return;
   }
   for(int i=0,t1=1;i<=Q[idx].second;++i,t1*=Q[idx].first)
      for(int j=i,t2=1;j<=Q[idx].second;++j,t2*=Q[idx].first)
         for(int k=j,t3=1;k<=Q[idx].second;++k,t3*=Q[idx].first)
            if(k==Q[idx].second)
               dfs(idx+1,A*t1,B*t2,C*t3);
}
void Delta() {
   cin >> n >> m;
   for(auto i:{&a,&b,&c})
      for(int j=1,x;j<=n;++j) {
         cin >> x;
         ++(*i)[x];
      }
   for(int i=2;i*i<=m;++i)
      while(m%i==0) {
         if(Q.empty()||Q.end()[-1].first!=i) Q.push_back({i,1});
         else Q.end()[-1].second++;
         m/=i;
      }
   if(m!=1)
      if(Q.empty()||Q.end()[-1].first!=m) Q.push_back({m,1});
      else Q.end()[-1].second++;
   else;
   dfs(0,1,1,1);
   cout << sum << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

If a number is less than $$$10^9$$$, it has a maximum possible factor of $$$1344$$$, enumerate two factors of $$$m$$$, then divide the third factor, and then use map to do count to pass.

In this table you can find all the values of $$$\text{d}(n)$$$ and $$$ω(n)$$$ for your future use :)

upd:

$$$\text{d}(n)$$$ = the number of different factors, and $$$ω(n)$$$ = the number of different prime factors

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[500001];
void Delta() {
   int n,x; cin >> n >> x;
   if(x<n-1||x>(n/2)*(n-n/2)) {
      cout << -1 << endl;
      return;
   }
   for(int i=2;i<=n/2+1;++i) cout << i-1 << ' ' << i << endl;
   x-=n-1;
   for(int i=n/2+2;i<=n;++i) {
      cout << min(x,n/2-1)+1 << ' ' << i << endl;
      x-=min(x,n/2-1);
   }
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

The key to solving the problem is — consider constructing a tree with the highest score first.

It's obvious all leaf have the same LCA (othwise,link leaves with smaller depths next to leaves with larger depths, and the score will not decrease) .Note $$$x$$$ as the number of leaf nodes,then the score is $$$x(n-x)$$$,when $$$x=\lfloor\frac{n}{2}\rfloor$$$,it reaches the maximum.

From the tree with the highest score, we can easily construct a tree with any score (by moving each leaf node up).

For convenience,note $$$A={a_1,a_2,...,a_n}$$$ and $$$B={a_{n+1},a_{n+2},...,a_{2n}}$$$($$$A,B$$$ are circular).

Calculate $$$preA$$$ and $$$sufB$$$:

• $$$\text{preA}_i:\max(a_j+...+a{i-1}+a_{i})$$$;

• $$$\text{sufB}_i:\max(b_i+b_{i+1}+...+b_{j})$$$;

This can be solved using monotonic stacks in $$$\Theta(n)$$$.

Then reverse $$$A,B$$$ and do it again.

The answer is the maximum of the following values:

• $$$\max(\text{preA}_i);$$$

• $$$\max(\text{sufB}_i);$$$

• $$$\max(\text{preA}_i+\text{sufB}_{i+1}).$$$

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=3000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n;
ll  ans;
int a[N],b[N],Q[N];
ll  Sa[N],Sb[N],prea[N],sufb[N];

void solve()
{
	for(int i=1;i<=n;i++)   a[i+n]=a[i],b[i+n]=b[i];
	for(int i=1;i<=n*2;i++) Sa[i]=Sa[i-1]+a[i],Sb[i]=Sb[i-1]+b[i];
	int head=1,tail=0;
	for(int i=1;i<=n*2;i++)
	{
		if(i>n)
		{
			while(i-Q[head]>n) head++;
			prea[i-n]=Sa[i]-Sa[Q[head]];
		}	
		while(head<=tail&&Sa[Q[tail]]>Sa[i]) tail--;
		Q[++tail]=i;
	}
	head=1;tail=0;
	for(int i=n*2;i;i--)
	{	
		while(head<=tail&&Sb[Q[tail]]<Sb[i]) tail--;
		Q[++tail]=i;
		if(i<=n)
		{
			while(Q[head]-i+1>n) head++;
			sufb[i]=Sb[Q[head]]-Sb[i-1];
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,prea[i]);
	for(int i=1;i<=n;i++) ans=max(ans,sufb[i]);
	for(int i=1;i<n;i++)  ans=max(ans,prea[i]+sufb[i+1]);
	ans=max(ans,prea[n]+sufb[1]);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		ans=-INF;
		solve();
		for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]),swap(b[i],b[j]);
		solve();
		cout<<ans<<'\n';
	}
	
	return 0;
}

We can see how to merge the largest subsegment of two intervals and by GSS1 in $$$\Theta(1)$$$ time, so using a seg tree and just enumerates all possible k and computs it in $$$O(\log n)$$$ time. This is $$$O(n\log n)$$$.

As you can see, each query is a prefix or suffix of a single array, so we can use the prefix sum and the suffix sum, this is $$$\Theta(n)$$$.

I mentioned a minimum-memory solution in the announcement comment, so now explain how to do $$$\text{12,000 KB}$$$.

For this $$$\Theta(n)$$$ level's memory we can only save int32 a[].

For the prefix sum, just save the value of the previous one, and then add it up, you can do $$$\Theta(1)$$$ memory.

For suffix sum, do the normal suffix sum first, and save the suffix sum values on all $$$k·\sqrt{n}$$$ locations. Then compute each sqrt block separately, $$$\Theta(\sqrt{n})$$$ saves its suffix, computes its perfix recursively, and releases the memory after the calculation is complete.

This allows us to achieve memory complexity $$$\Theta(\text{sqrt})$$$ and time complexity $$$\Theta(n)$$$ in addition to "int32 a[]".

It's $$$\text{12,000 KB}$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
int a[3000010];
#define int long long
#define B 1000
class node{public:int sum,lm,rm,ans;}temp;
inline void merge1(node&a,node&l,node&r){a={l.sum+r.sum,max(l.lm,l.sum+r.lm),max(r.rm,r.sum+l.rm),max({l.ans,r.ans,l.rm+r.lm})};}
inline void merge2(node&a,node&l,node&r){a={l.sum+r.sum,min(l.lm,l.sum+r.lm),min(r.rm,r.sum+l.rm),min({l.ans,r.ans,l.rm+r.lm})};}
inline node i2node(int x){return {x,x,x,x};}
node sufb[1500010/B+10],sufnb[1500010/B+10],tsuff[B+10],tsufnf[B+10];
void Delta() {
   int n,s=-2147483648,sum=0,flag=true,mx=-2147483648;cin >> n;
   for(int i=1;i<=n*2;++i) {
      cin >> a[i];sum+=(int)a[i];
      flag&=a[i]<0;mx=max(mx,(int)a[i]);
   } 
   node pre=i2node(0),pren=i2node(0),suf=i2node(0),sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge1(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge1(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge1(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge1(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge1(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge1(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge1(temp,pren,tsuff[i%B+1]);
      merge1(temp,temp,pre);
      merge1(temp,temp,tsufnf[i%B+1]);
      s=max(s,temp.ans);
   }
   pre=pren=suf=sufn=i2node(0);
   for(int i=n;i>=1;--i) {
      temp=i2node(a[i]);
      merge2(suf,temp,suf);
      temp=i2node(a[i+n]);
      merge2(sufn,temp,sufn);
      if(i%B==0) {
         sufb[i/B]=suf;
         sufnb[i/B]=sufn;
      }
   }
   for(int i=1;i<=n;++i) {
      temp=i2node(a[i]);
      merge2(pre,pre,temp);
      temp=i2node(a[i+n]);
      merge2(pren,pren,temp);
      if(i%B==0||i==1) {
         tsuff[B]=sufb[i/B+1];
         tsufnf[B]=sufnb[i/B+1];
         for(int j=(B-1);j>=1;--j) {
            temp=i2node(i-(i==1)+j>n?0:a[i-(i==1)+j]);
            merge2(tsuff[j],temp,tsuff[j+1]);
            temp=i2node(i-(i==1)+j+n>2*n?0:a[i-(i==1)+j+n]);
            merge2(tsufnf[j],temp,tsufnf[j+1]);
         }
      }
      merge2(temp,pren,tsuff[i%B+1]);
      merge2(temp,temp,pre);
      merge2(temp,temp,tsufnf[i%B+1]);
      s=max(s,sum-temp.ans);
   }
   cout << (flag?mx:s) << '\n';
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
 
#define int long long
 
const int MOD=998244353;
int a[200001],b[200001],vis[200001];
vector<int> Q[200001];
void dfs(int x) {
   if(vis[x]) return;
   vis[x]=true;
   for(int i:Q[x]) dfs(i);
}
void Delta() {
   int cnt=0,blk=0,n; // count,block number
   cin >> n;
   for(int i=1;i<=n;++i) {
      cin >> a[i];
      b[i]=a[i];
      Q[i].clear();
      vis[i]=0;
   }
   sort(b+1,b+1+n);
   for(int i=1;i<=n;++i) 
      if(a[i]!=b[i]) {
         Q[a[i]].push_back(b[i]);
         Q[b[i]].push_back(a[i]);
      } else cnt++;
   for(int i=1;i<=n;++i)
      if(!vis[a[i]]&&a[i]!=b[i]) {
         blk++;
         dfs(a[i]);
      }
   if(n==2) {
      if(cnt==2) cout << 0 << endl;
      else cout << -1 << endl;
      return;
   }
   if(cnt!=0) cout << blk+(n-cnt) << endl;
   else if(blk==1) cout << n+2 << endl;
   else cout << n+blk << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   int T;cin >> T;
   while(T--) Delta();
}

Compare the original array (say $$$a$$$) to the sorted one (say $$$b$$$). Since we can move only one token at once, in one move we can place at max one token to its correct place. So let's try to minimise the number of moves that don't do this.

To make optimal moves, model a directed multi-edged graph. Start with only vertices ($$$1$$$ to $$$n$$$), no edges, and add a directed edge from $$$a[i]$$$ to $$$b[i]$$$ when $$$a[i]!=b[i]$$$, for each $$$i$$$ (meaning that $$$b[i]$$$ should be placed in place of $$$a[i]$$$).

We can follow an optimal scheme like this: For now let us assume there is at least one position where correct token is placed (let it be $$$p$$$). Choose an incorrectly placed token, place it on top of $$$p$$$. This creates a gap. Place the correct token for this place. This moves the gap somewhere else. Again choose a corect token for the gap and so on. In the end, place the token stacked on top of $$$p$$$ into the gap, close the gap, and all the tokens we touched are placed correctly.

In the graph, placing a token from $$$b[i]$$$ to gap at $$$a[i]$$$ would mean moving from $$$a[i]$$$ to $$$b[i]$$$ in the graph along an edge and removing the edge. Thus the problem reduces to removing all edges of the graph in minimum number of moves.

The graph is split into disjoint connected componnts. We can thus independently resolve each component optimally for minimum number of moves.

Next, we prove that a connected component is always an euler circuit.

Claim $$$1$$$: The component would have a cycle. If it doesn't, then following some path $$$a \rightarrow b \rightarrow ...$$$, we will reach a dead end, which means that the last element has no place to go, which is not true since it belongs to the array and must have a correct position to be placed at. By induction, we can keep removing cycles (by moving along them and removing edges), and so the component is basically a set of directed cycles intersecting at vertices.

Claim $$$2$$$: It will hence form an euler circuit. Let us go along a cycle. It starts at $$$v$$$, ends at $$$v$$$. Now if there is a cyce intersecting at some vertex $$$v'$$$ in the cycle, on reaching $$$v'$$$ resolve that cycle, return at $$$v'$$$, continue on the older cycle. By this inductive argument, we can cover all edges exactly once and return to $$$v$$$, making an euler circuit.

To find the precise number of moves to resolve a component involving $$$s$$$ tokens, we need to create a gap in $$$1$$$ move, place $$$s-1$$$ tokens correctly, and place the last token we moved initially. Total $$$s+1$$$ moves. To create a gap, we need to place a token from our position to some position not in the component.

Now, proper casework:

Let the number of tokens not placed correctly be $$$co$$$. Let the number of disjoint connected components be $$$x$$$.

If $$$co \lt n$$$: There is always a correctly placed position to stack our token on and create a gap. So, each component of size s will be resolved in $$$s+1$$$. So total $$$co+x$$$ moves.

If $$$x \gt 1$$$: Since there are $$$ \gt 1$$$ components, we can use a position from the other component to create gap for one component. Again $$$co+x$$$.

$$$co==n$$$ and $$$x==1$$$: It may be a single cycle, or $$$ \gt 1$$$ joint cycles. If there are $$$ \gt 1$$$ joint cycles, resolve one of the cycles, then it reduces to the cases above. Totals to $$$n+2$$$ moves. For exactly one cycle, graph is $$$1 \rightarrow 2 \rightarrow ...n \rightarrow 1$$$. So stack $$$1$$$ on $$$2$$$, resolve rest $$$n-2$$$, total $$$n-1$$$. Then resolve $$$1$$$ and $$$2$$$ which takes $$$3$$$ moves. So total again is $$$n+2$$$. Since $$$n+1$$$ is not possible in this case, and we construct a solution in $$$n+2$$$, it is optimal.

Final solution:

1. $$$(co \lt n)$$$ or $$$(x \gt 1)$$$ : $$$co+x$$$

2. $$$(co==n)$$$ and $$$(x==1)$$$ : $$$n+2$$$

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

#define int long long

void test_case() {
	int n; cin >> n;
	int a = floor(sqrt(n));
	int b = (n + a - 1) / a;
	cout << a * 2 + b * 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

If $$$n$$$ is a perfect square number, we find that the square dyeing scheme is always optimal.The answer is $$$4\sqrt{n}$$$.

Otherwise,if $$$n-\lfloor \sqrt{n} \rfloor ^2 \leq \lfloor \sqrt{n} \rfloor$$$,the answer is $$$4\lfloor \sqrt{n} \rfloor+2$$$.Otherwise the answer is $$$4\lfloor \sqrt{n} \rfloor+4$$$.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		std::vector<vector<int>> v(2);
		std::vector<int> cnt(2*n + 10);
		for(int i = 0; i < 2; i++) {
			v[i].resize(n);
			for(int &u:v[i]) {
				cin >> u;
				cnt[u]++;
			}	
		}
		int mex = 0;
		while(cnt[mex]) mex++;
		int ans = mex * (n&1);
		for(int i = 0; i < n; i++) {
			int val = v[1 ^ (i%2)][i];
			if(!(n&1)) {
				int cur_mex;
				if(val > mex || cnt[val] > 1) cur_mex = mex;
				else cur_mex = val;
				ans = max(ans, cur_mex); 
			}
		}
		cout << ans << "\n";
	}
}

If $$$n$$$ is odd,we can traverse all cells, which is a simple situation.

If $$$n$$$ is even,we can skip one of $$$(1,2) (1,4) (1,6)...(1,n),(2,1),(2,3),(2,5)...(2,n-1)$$$.If there is a duplicate number, skip it. Otherwise, skip the maximum number.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int  T,n,k;
int  a[N],pre1[N],tot1[N];
char s[N];

void init()
{
	pre1[n+1]=tot1[n+1]=0;
	for(int i=n;i;i--)
	{
		if(a[i])
		{
			pre1[i]=pre1[i+1]+1;
			tot1[i]=tot1[i+1]+1;
		}
		else
		{
			pre1[i]=0;
			tot1[i]=tot1[i+1];
		}
	}
}

int check(int idx,int c1)
{
	return (pre1[idx]<c1)||(pre1[idx]==c1&&tot1[idx]==c1);
}

void solve1()
{
	int c0=(n+k)/2,c1=c0-k;
	for(int i=1;i<=n;i++)
	{
		if(a[i])
		{
			c1--;
			printf("1");	
		}
		else
		{
			if(c0&&check(i+1,c1))
			{
				c0--;
				printf("0");	
			}
			else
			{
				c1--;
				printf("1");
				for(int i=1;i<=c0;i++) printf("0");
				for(int i=1;i<=c1;i++) printf("1");
				break;
			}
		}
	}
	printf("\n");
}

void solve2()
{
	int c0=0,c1=0;
	if(k>0)
	{
		c0=k;
		c0++,c1++;	
		while(c0+c1<=n) c0++,c1++;	
	}
	else
	{
		c1=-k;
		while(c0+c1<=n) c0++,c1++;	
	}
	printf("1");
	c1--;
	for(int i=1;i<=c0;i++) printf("0");
	for(int i=1;i<=c1;i++) printf("1");
	printf("\n");
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%s",&n,&k,s);
    	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    	init();
    	if(n==1&&a[1]==0&&k==1)
    	{
	    	printf("0\n");
	    	continue;
	    }
    	if((n+k)&1) solve2();
    	else
		{
	    	int c0=(n+k)/2,c1=c0-k;
			if(c0<0||c1<0) solve2();
			else
			{
				if(check(1,c1)) solve1();
				else solve2();
			}
	    }
	}
	
	return 0;
}

First,be careful when $$$y=0$$$ and $$$k=1$$$ :)

Consider the answer with a length greater than $$$n$$$, which is always $$$10...01...1$$$.The construction is not hard.

What about the answer with length $$$n$$$?

Consider setting numbers from the highest bit to the lowest bit and current bit is $$$i$$$.If $$$y_i=1$$$,we must set $$$x_i=1$$$.Otherwise($$$y_i=0$$$),we either do set $$$x_i=0$$$ and go to the lower bit,or do set $$$x_i=1$$$, $$$x_{i+1}x_{i+2}...x_n=0...01...1$$$ and break.

For $$$y_i=0$$$,when can we do set $$$x_i=0$$$ and go to the lower bit?The condition is $$$re1 \gt pre1_{i+1}$$$ or $$$re1==pre1_{i+1}$$$ and $$$pre1_{i+1}==tot1_{i+1}$$$.$$$re1$$$ is the current remaining number of $$$1's$$$,$$$pre1_{i+1}$$$ is the length of the continuous $$$1$$$ prefix of $$$y_{i+1}y_{i+2}...y_n$$$,and $$$tot1_{i+1}$$$ is the total of $$$1$$$ of $$$y_{i+1}y_{i+2}...y_n$$$.

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\n"; } }

Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.

It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.

Based on the above conclusion, we can make the optimal construction.

Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
ll  T,n,m,c;
ll  a[N][N];
ll  dp[N][N];

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

void DP()
{
	for(int i=1;i<=n;i++)
	{
		ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
		for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
		for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
		for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
		for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
		for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
	}
	ll ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dp[i][j]);
	printf("%I64d\n",ans);
}

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

Consider DP.

Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.

Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.

Now consider which cell we go from to $$$(i,j)$$$.There are four situations.

$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;

$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.

$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.

$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n;

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n%6==1)
		{
			for(int i=1;i<n/6;i++) printf("0");
			printf("8\n");
			continue;
		}
		for(int i=1;i<=n/6;i++) printf("0");
		if(n%6==2) printf("1\n");
		else if(n%6==3) printf("7\n");
		else if(n%6==4) printf("4\n");
		else if(n%6==5) printf("2\n");
		else printf("\n");
	}
	
	return 0;
}

If $$$n=6k$$$,print $$$0...0$$$;

If $$$n=6k+1$$$,print $$$0...08$$$;

If $$$n=6k+2$$$,print $$$0...01$$$;

If $$$n=6k+3$$$,print $$$0...07$$$;

If $$$n=6k+4$$$,print $$$0...04$$$;

If $$$n=6k+5$$$,print $$$0...05$$$;

If $$$n=6k+6$$$,print $$$0...09$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n,k;
int a[N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++) a[i]=0;
		for(int i=1;i<=k;i++)
		{
			if(n<2) break;
			a[i]=1;
			n-=2; 
		} 
		for(int i=k;i;i--)
		{
			if(a[i])
			{
				if(n>=4) a[i]=9,n-=4;
				else if(n>=1) a[i]=7,n--;
				else break;
			}
		}
		for(int i=k;i;i--) if(a[i]) printf("%d",a[i]);
		printf("\n");
	}
	
	return 0;
}

First,maximize number of digits — fill each digit with $$$'1'$$$.

Then starting from the highest bit,consider maximizing the current digit — consider changing the current bit to $$$'9'$$$. If no enough matchsticks, consider $$$'7'$$$.

Luckily,you find $$$[1,2n,2,2n-1,...,n,n+1]$$$ works :)

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n,x;

int check(vector<int> v)
{
	sort(v.begin(),v.end());
	for(int i=1;i<=n*2;i++) if(v[i]!=i) return 0;
	return 1;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&x);
		ll S=(ll)n*(2*n+1),a=2*n+1,b,flg=0;
		for(int i=x;i<=x;i++)
		{
			for(int j=1;j<=2*n;j++)
			{
				if((S-i-j)%(n-1)) continue;
				b=(S-i-j)/(n-1); 
				vector<int> v;
				v.push_back(0);
				v.push_back(i);
				for(int i=2;i<n*2;i++)
				{
					if(i&1) v.push_back(b-v.back());
					else    v.push_back(a-v.back());
				} 
				v.push_back(j);
				if(check(v))
				{
					for(int k=1;k<=n*2;k++) printf("%d%c",v[k],k==n*2?'\n':' ');
					flg=1;
					break;
				}
			} 
		} 
		if(!flg) printf("-1\n");
	}
	
	return 0;
}

Note $$$s_1=p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n},s_2=p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$.

We can easily get $$$s_1=2n+1$$$.

Consider fix $$$s_2$$$,we can get:$$$p_{2n}=n*s_1-p_1-(n-1)s_2$$$.Since $$$1\leq p_{2n} \leq 2n$$$, we found that there are no more than $$$3$$$ suitable $$$s_2$$$.

For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int T,n,m;
int t[N];
int a[N][N],b[N][N],c[N][N];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				scanf("%d",&b[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				c[i][j]=(a[i][j]^b[i][j]);		
		t[0]=t[1]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				t[(i+j)&1]^=c[i][j];
		if(n==3&&m==3&&(c[1][2]||c[2][1]||c[2][3]||c[3][2])) printf("NO\n");
		else if(n==3&&m==4&&(c[2][1]||c[2][4])) printf("NO\n");
		else if(n==4&&m==3&&(c[1][2]||c[4][2])) printf("NO\n");
		else printf("%s\n",(t[0]||t[1])?"NO":"YES");		
	}
	
	return 0;
}

Consider a $$$3*3$$$ matrix,we can do something like:

$$$000$$$

$$$000$$$

$$$000$$$

$$$- \gt $$$

$$$100$$$

$$$010$$$

$$$101$$$

$$$- \gt $$$

$$$101$$$

$$$000$$$

$$$000$$$

Consider we can only flip $$$a_{x,y},a_{x,y+2}$$$ and $$$a_{x,y},a_{x+2,y}$$$,what about the answer?

Note $$$x_0=a_{1,1}⊕a_{1,3}⊕...,x_1=a_{1,2}⊕a_{1,4}⊕...$$$,the answer is $$$YES$$$ if and only if the $$$x_0=x_1=0$$$.

Let's go back to the original problem.The only difference is there are some unaccessable elements.Just do special judgment.

If $$$n=3,m=3$$$,unaccessable elements are $$$a_{1,2},a_{2,1},a_{2,3},a_{3,2}$$$;

If $$$n=3,m=4$$$,unaccessable elements are $$$a_{2,1},a_{2,4}$$$;

If $$$n=4,m=3$$$,unaccessable elements are $$$a_{1,2},a_{4,2}$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
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=0;
const ll  INF=2147483647;
int T,n,flg;
int a[N],fre[N];
vector<int> G[N],ch[N];

void DFS(int x,int pr)
{
    for(int i=0;i<G[x].size();i++)
    {
	    int y=G[x][i];
            if(y==pr) continue;
	    ch[x].push_back(y);
            DFS(y,x);
    }
    if(x==1) return ;
    if(ch[x].size()==0) fre[x]=0;
    else if(ch[x].size()==1)
    {
    	fre[x]=0;
    	if(a[ch[x][0]]&&fre[ch[x][0]]) a[x]^=1;
    	else if(a[ch[x][0]]&&(!fre[ch[x][0]])) flg=0;
    }
    else if(ch[x].size()==2)
    {
    	if(fre[ch[x][0]]||fre[ch[x][1]])
    	{
    		a[x]^=(a[ch[x][0]]^a[ch[x][1]]);
	    	if(fre[ch[x][0]]&&fre[ch[x][1]]) fre[x]=1;
	    	else
	    	{
	    		fre[x]=0;
	    		if(a[ch[x][0]]&&a[ch[x][1]]) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][0]]&&(!fre[ch[x][0]])) a[x]^=1,a[pr]^=1;
	    		else if(a[ch[x][1]]&&(!fre[ch[x][1]])) a[x]^=1,a[pr]^=1;
	    	}
	    }
	    else
	    {
	    	fre[x]=0;
    		if(a[ch[x][0]]^a[ch[x][1]]) flg=0;
	    	else a[x]^=a[ch[x][0]],a[pr]^=a[ch[x][0]];
    	}
    }
    else
    {
    	int tagf=0,taga=0;
    	for(int i=0;i<ch[x].size();i++) tagf|=fre[ch[x][i]],taga^=a[ch[x][i]];
    	if((!tagf)&&taga) flg=0;
    	else fre[x]=1,a[x]^=taga;
    }
}

void check1()
{
	int taga=0;
	for(int i=0;i<ch[1].size();i++) if((!fre[ch[1][i]])&&a[ch[1][i]]) flg=0;
	for(int i=0;i<ch[1].size();i++) taga^=a[ch[1][i]];
	if(taga^a[1]) flg=0;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
	    scanf("%d",&n);
	    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	    for(int i=1;i<=n;i++) G[i].clear(),ch[i].clear(); 
	    for(int i=1;i<n;i++)
	    {
    		int u,v;
    		scanf("%d%d",&u,&v);
    		G[u].push_back(v);
    		G[v].push_back(u);
    	   }
    	   flg=1;
    	   DFS(1,0);
           check1();
	   printf("%s\n",flg?"YES":"NO");
	}
	
	return 0;
}

Define free nodes $$$x$$$ — $$$free[x]=1$$$ means we can freely flip $$$x,fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0;

Define $$$col[x]$$$ — the value when node $$$x$$$ does not affect $$$fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0.Later on, we can see that this value is unique.

We update the values of $$$free[x],col[x]$$$ from bottom to top.

Case $$$1$$$:$$$x$$$ has $$$0$$$ son nodes.It's easy to get $$$free[x]=0,col[x]=a[x]$$$.

Case $$$2$$$:$$$x$$$ has $$$1$$$ son nodes.

We get $$$free[x]=0$$$.

If $$$col[son[x][0]]=0$$$,we don't need to flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]$$$;

If $$$col[son[x][0]]=1$$$ and $$$free[son[x][0]]=0$$$,no solution.Otherwise we must flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]⊕1$$$;

Case $$$3$$$:$$$x$$$ has $$$ \gt 2$$$ son nodes.

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$x$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[x][i]$$$,no solution.

If we can change all the descendant nodes(exclude itself) of $$$x$$$ to 0,$$$x$$$ is always a free node.

Let's calculate $$$col[x]$$$.If $$$tagc=1$$$,we must flip $$$x$$$ and a free node,so $$$col[x]=a[x]⊕1$$$.If $$$tagc=0$$$,$$$col[x]=a[x]⊕0$$$.

Case $$$4$$$:$$$x$$$ has $$$2$$$ son nodes.

If $$$son[x][1],son[x][2]$$$ are both not free nod:

• if $$$col[son[x][1]]⊕col[son[x][2]]=1$$$,no solution;

• if $$$col[son[x][1]]=col[son[x][2]]=0$$$,$$$free[x]=0,col[x]=a[x]$$$;

• if $$$col[son[x][1]]=col[son[x][2]]=1$$$,$$$free[x]=0,col[x]=a[x]⊕1$$$,and flip $$$a[fa[x]]$$$;

If $$$son[x][1],son[x][2]$$$ are both free node,$$$free[x]=1,col[x]=a[x]⊕col[son[x][1]]⊕col[son[x][2]]$$$.

Otherwise,do similar casework :)

Finally(I promise),let's check the answer,for all son nodes of node $$$1$$$:

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$1$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[1][i]$$$,no solution.

Otherwise,we should check $$$a[1]⊕tagc$$$.The answer is $$$YES$$$ if and only if $$$a[1]⊕tagc=0$$$.

Obviously,the length of a continuous segment with a negative contribution is $$$1$$$.

We can write a $$$O(n^2)$$$ DP:

$$$dp[i]=max(dp[j]-a[j+1]+a[j+2]|...|a[i])$$$

Then we notice there're at most $$$O(log maxa)$$$ different values in $$$a[j]|...|a[i]$$$ $$$(j \lt i)$$$.It's a classic conclution.

For a fix $$$a[j]|...|a[i]$$$ $$$=t$$$,we get $$$dp[i]=max(dp[j]-a[j+1])+t$$$.Since the value range of $$$j$$$ is continuous,we can use a segment tree to maintain it.It's $$$O(n log^2 n)$$$.

In fact,use prefix maximum value is enough.Note $$$premax[i]=max(dp[1]-a[2],...,dp[i]-a[i+1])$$$,$$$dp[i]=premax[j]+t$$$.It's $$$O(n log n)$$$.

This has prepared us for solving F2(solution2).

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

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i<N;i++) dp[i]=pre[i]=0;
		for(int i=1;i<=n;i++)
		{
			int cur=0;
			scanf("%d",&a[i%N]);
			pre[i%N]=(pre[(i-1+N)%N]|a[i%N]);
			dp[i%N]=pre[i%N];
			for(int j=i;j>=max(3,i-60);j--) 
			{
				cur|=a[j%N];
				dp[i%N]=max(dp[i%N],dp[(j-2+N)%N]-a[(j-1+N)%N]+cur);
			}
		}
		printf("%I64d\n",dp[n%N]);
	}

	return 0;
}

You need to observation that the length of consecutive segments will not exceed $$$60$$$.

Then we can use a scrolling array for DP.

Note $$$maxp$$$ as the maximum index of the maximum value in $$$a$$$.

For $$$1 \leq k \leq maxp-1$$$,they do not meet the condition.

For $$$maxp+1 \leq k \leq n$$$,they all meet the condition.

You need to be careful of $$$k==maxp$$$,it meet the condition if and only if there is only one maximum value in $$$a$$$.

Note $$$a_1$$$ as the first $$$\lceil{n/2}\rceil$$$ numbers of $$$a$$$,and $$$a_2$$$ as the last $$$n-\lceil{n/2}\rceil$$$ numbers of $$$a$$$.

Through observation,we found that the following processes will be repeated cyclically:

• erase the leftmost number of $$$a_1$$$

• erase the leftmost number of $$$a_2$$$

• erase the rightmost number of $$$a_1$$$

• erase the rightmost number of $$$a_2$$$

In conclusion:

• If $$$|a_1| \gt |a_2|$$$(i.e. $$$n$$$ is odd),the answer is the number in the middle of $$$a_1$$$

• If $$$|a_1|=|a_2|$$$(i.e. $$$n$$$ is even),the answer is the number in the middle of $$$a_2$$$

We notice we can convert condition $$$3$$$ to $$$c0(a,l_1,r_1)-c1(a,l_1,r_1)=c1(b,l_2,r_2)-c0(b,l_2,r_2)$$$.

This provides us with convenience: we can independently calculate the left and right value ranges.

If two ranges intersect, the answer is $$$YES$$$,otherwise the answer is $$$NO$$$.

Let's calculate the left value ranges.Make all $$$a_i=0$$$ to $$$1$$$ and $$$a_i=1$$$ to $$$-1$$$,it is the value range of all subarrays of appropriate length.

In fact,we only need to find max subsegment sum and min subsegment sum.It's a classic problem.

You may have already guessed:if $$$x_1 \lt y_1$$$,and you get $$$minsum,maxsum$$$,the range of values is continuous — $$$[minsum,maxsum]$$$.Why?

You also need to be careful of the edge cases that $$$x_i=y_i(1 \leq i \leq 2)$$$.

We notice we can calculate each bit independently.

In other words,note $$$f(a_i,j)$$$ as the $$$j^{th}$$$ bit under the binary representation of $$$a_i$$$,the answer is $$$\Sigma_{i=0}^{i=30} 2^{i}*(\Sigma f(a_l,i)⊕...⊕f(a_r,i))$$$.

Let's calculate the sum of the $$$0^{th}$$$ bit.

$$$a_{i,0}=0,1,0,1,...$$$

Note $$$pre_{i,0}=a_{1,0}⊕...⊕a_{i,0}$$$,then

$$$pre_{i,0}=0,1,1,0,0,1,1,0,...$$$

We noticed that the loop section of this sequence is $$$4$$$ and can calculate the total number of $$$'1'$$$(note it as $$$c_1$$$).The total number of subarrays with xor-value $$$1$$$ is $$$c_1*(n+1-c_1)$$$.

For the $$$1,2,...30^{th}$$$ bit,use the similar method to calculate it.

Consider an easier problem:for a fixed score $$$x_1*x_2*...*x_k$$$($$$x_i$$$ is one of the prefix minimum value and note the set of them as $$$X$$$),how to calculate the number of schemes?

Consider such a sequence construction process: put all $$$0$$$'s, all $$$1$$$'s, and all $$$2$$$'s,...

If you want the prefix minimum value of $$$i$$$ to appear in $$$a$$$, what should you do?We can get:at least one $$$i$$$ must be placed at the head of the current sequence.

This is actually equivalent to the classical problem: $$$m_i$$$ balls are put into $$$(m_1+...+m_{i-1}+1)$$$ boxes, the first box must have at least one ball,count the number of schemes.

The answer is:

$$$U_i=C(m_i-1+(m_1+...+m_{i-1}),(m_1+...+m_{i-1}))$$$.

If you want the prefix minimum value of i not to appear in $$$a$$$, what should you do?We can get:no $$$i$$$ must be placed at the head of the sequence.Solve it in a similar way as above.

The answer is:

$$$V_i=C(m_i+(m_1+...+m_{i-1})-1,(m_1+...+m_{i-1})-1)$$$.

Let's go back to the easier problem.The number of schemes is $$$\Pi_{i∈X}U_i * \Pi_{i∉X}V_i$$$.

Finally, how to calculate the total score?We can convert the formula into:$$$(1*U_1+V_1)(2*U_2+V_2)...(n*U_n+V_n)$$$.

There's another dp solution:$$$dp_i=(i-1)*U_{i-1}*dp_{i-1}+V_{i-1}*dp_{i-1}$$$.It's actually do the same thing.

Note $$$c_{i,j}=a_{i,j}⊕b_{i,j}$$$.The problem is equivalent to turning $$$c$$$ into a zero matrix.

Consider $$$l=2$$$.What about the solution?

We can easily get:the answer is $$$YES$$$ if and only if the xor-sum of all numbers is $$$0$$$.

Now let’s consider $$$l=3$$$.The method can be extended to $$$l=k$$$.

We notice we can do:

$$$0000- \gt 1110- \gt 1001$$$

If we can only filp $$${a_{x,y},a_{x,y+3}}$$$ and $$${a_{x,y},a_{x+3,y}}$$$,what about the answer?

We group the elements in the matrix $$$c$$$ like:

$$$1231231... $$$

$$$4564564... $$$

$$$7897897... $$$

$$$1231231... $$$

$$$... $$$

Note $$$XOR(i)$$$ as xor-sum of all numbers in group $$$i$$$.We can get:if all $$$XOR(i)$$$ are $$$0$$$,the answer is $$$YES$$$.

Now let’s consider the origin flip. In essence,there are only $$$6$$$ different operations:

• Flip $$$XOR(1),XOR(2),XOR(3)$$$;

• Flip $$$XOR(4),XOR(5),XOR(6)$$$;

• Flip $$$XOR(7),XOR(8),XOR(9)$$$;

• Flip $$$XOR(1),XOR(4),XOR(7)$$$;

• Flip $$$XOR(2),XOR(5),XOR(8)$$$;

• Flip $$$XOR(3),XOR(6),XOR(9)$$$.

Construct a $$$l*l$$$ matrix $$$d$$$,$$$d_{i,j}=XOR((i-1)*l+j)$$$.We find that we can turn it into a classical problem:

https://mirror.codeforces.com/problemset/problem/1475/F.

What about $$$x*y$$$ span?