AGC063C Add Mod Operations

感觉是非常纯的思维题。

题意

给两个长度为 \(n\) 的序列 \(A, B\)。你可以对 \(A\) 做不超过 \(n\) 次操作，形如对于所有元素，先加上 \(x\) 再对 \(y\) 取模。其中 \(0\le x < y\le 10^{18}\) 是由你决定的任意整数。给出一种方案将 \(A\) 变成 \(B\)，或声明无解。

\(1\le n \le 2000, 0\le A_i, B_i \le 10^9\)。

题解

发现取模这个操作可以只作用于比较大的数，那么考虑能不能每次只操作最大的数。发现对于最大的数的操作其实也有一些限制，那么直接考虑一个比较极端的情况：每次都把最大的数变成 \(0\)。那么再结合加 \(x\) 这个操作，其实相当于把整个序列向右移动一些距离，然后把最后一个数放到原点上。那么通过 \(n - 1\) 次操作，我们可以控制任意两个数之间的距离，但是不能改变它们的相对位置。考虑通过最后一次操作，把所有数赋予正确的值。这要求原先的数值大小关系丧失掉，所以考虑利用取模。具体地，设一个极大数 \(R\)，然后令第一个数的目标是 \(0\)，第二个数的目标是 \(B_2 - B_1 + R\)，第三个数是 \(B_3 - B_1 + 2R\)，以此类推，这样可以让原序列的顺序得以保持，而只需要在最后进行加 \(B_1\)，模 \(R\) 的操作即可一次性处理所有数。

代码

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 1005;
constexpr LL R = 2000000000;

int n;
LL a[N], b[N];
int ord[N];

LL calc_val(int i)
{
	return b[ord[i]] + R * ((i - 2 + n) % n);
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n;
	F(i, 1, n) cin >> a[i];
	F(i, 1, n) cin >> b[i];

	iota(ord + 1, ord + n + 1, 1);
	sort(ord + 1, ord + n + 1, [] (int x, int y)
		{ return a[x] < a[y]; });
	bool ok = false;
	F(i, 2, n)
	{
		if (a[ord[i]] == a[ord[i - 1]] && b[ord[i]] != b[ord[i - 1]])
		{
			cout << "No\n";
			return 0;
		}
		if (a[ord[i]] != a[ord[i - 1]]) ok = true;
	}

	if (!ok)
	{
		cout << "Yes\n";
		cout << "1\n";
		if (a[1] > b[1]) cout << R - a[1] << ' ' << R - b[1] << '\n';
		else cout << b[1] - a[1] << ' ' << R << '\n';
		return 0;
	}

	vector<pair<LL, LL>> ans;
	LL sum = 0;
	FF(i, n, 2)
	{
		if (i != n && a[ord[i]] == a[ord[i + 1]]) continue;
		LL x = calc_val(i % n + 1) - calc_val(i);
		if (i == n) x -= a[ord[1]];
		sum += x;
		ans.push_back({x, a[ord[i]] + sum});
	}
	ans.push_back({calc_val(2), R});
	
	cout << "Yes\n";
	cout << ans.size() << '\n';
	for (auto xy : ans) cout << xy.first << ' ' << xy.second << '\n';
	
	return 0;
}