本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-16 16:04:50

做法

做法很显然，就是贪心的使低位尽量小。

对于每一位，都尽量选择在它后面的，且最小的元素与之交换。

如果后面有多个最小的，那怎么做呢？

因为要使字典序尽可能小，而交换的时候必然有一位变大，所以使变大的这一位尽量靠后。

所以，做法就是，对于每一位，将其与在它后面的，最小且最远的元素交换。

另外要注意，由题目性质可以得出，两个元素交换之后，它们之间的元素（包括自己）就不能进行交换操作了，要进行判断。

Code

#include <bits\/stdc++.h> \/\/ scanf
using namespace std;
const int MAXN = 1e7+5; \/\/ Set a right value according to your solution.
int n, a[MAXN];

namespace Generator {

	unsigned long long k1, k2;
	int thres;

	inline unsigned long long xorShift128Plus() {
		unsigned long long k3 = k1, k4 = k2;
		k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
		return k2 + k4;
	}

	inline void generate() {
		for (int i = 1; i <= n; ++i) {
			a[i] = xorShift128Plus() % thres;
		}
	}

} \/\/ namespace Generator.
int imin[MAXN];
int pos[MAXN];
int main() {
	scanf("%d", &n);
	scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
	Generator::generate();
	\/\/ Now array a[1..n] represents the sequence A in the statement.
	imin[n]=a[n];
	pos[n]=n;
	for(register int i=n-1;i>=1;i--)
	{
		if(a[i]<imin[i+1])
		{
			imin[i]=a[i];
			pos[i]=i;
		}
		else
		{
			imin[i]=imin[i+1];
			pos[i]=pos[i+1];
		}
	}
	register int _pos;
	for(register int i=1;i<=n;i++)
	{
		if(imin[i]==a[i])continue;
		_pos=pos[i];
		swap(a[i],a[pos[i]]);
		i=_pos;
	}
	unsigned long long ans=0;
	for(register int i=1;i<=n;i++)
	{
		ans=(ans+(unsigned long long)i*(unsigned long long)a[i]);
	}
	printf("%llu",ans);
	return 0;
}