CF1863C MEX Repetition 题解
Links
Description
给你一个长度为 \(n\) 的序列 \(a\)，满足 \(\forall i \in [1,n]\)，\(0 \leq a_{i} \leq n\) 且序列中的数互不相同。
定义一次操作为：
- 按照 \(i\) 从 \(1\) 到 \(n\) 的顺序，\(a_{i} \gets \operatorname{MEX}(a_{1} \ldots a_{n})\)。
注意：一次操作中的每一步改变 不是 同时进行的，即每一步求 \(\operatorname{MEX}\) 的序列 \(a\) 都在上一步被改变。
你需要求出经过 \(k\) 次操作之后的序列 \(a\)。
本题有多组测试数据，\(1 \leq T,n,\sum n \leq 10^5\)，\(1 \leq k \leq 10^{9}\)。
Solution
看到题目，让我们先来模拟一下。
\[\begin{array}{c} \left \{1,2,3,4,5 \right\} \\ \left \{0,1,2,3,4 \right\} \\ \left \{5,0,1,2,3 \right\} \\ \left \{4,5,0,1,2 \right\} \\ \left \{3,4,5,0,1 \right\} \\ \left \{2,3,4,5,0 \right\} \\ \left \{1,2,3,4,5 \right\} \\ \end{array}\]很容易知道，我们在替换时，第一个数总是在上次没出现的数。然后没出现的数就变成了刚才被替换掉的数。假设经过第 \(i\) 次替换的序列中第 \(j\) 个数是 \(a_{i,j}\)，那么有 \(a_{i,1} = a_{i-2,n}\)，\(\forall j \in [2,n]\)，\(a_{i,j} = a_{i - 1,j - 1}\)。
虽然我们推出了规律，但这玩意是 \(O(nk)\) 的，炸裂 TLE。
但我们可以尝试找一找规律，如果看上面的看不出来就看看下面这个吧。
\[\begin{array}{c} \left \{1,2,3,4,5,(0) \right\} \\ \left \{0,1,2,3,4,(5) \right\} \\ \left \{5,0,1,2,3,(4) \right\} \\ \left \{4,5,0,1,2,(3) \right\} \\ \left \{3,4,5,0,1,(2) \right\} \\ \left \{2,3,4,5,0,(1) \right\} \\ \left \{1,2,3,4,5,(0) \right\} \end{array} \]发现什么了嘛，其实每次的只是相当于上一次平移了一下，因为当前没有的就是刚被替换掉的。
于是我们只需要找到起始的数字就可以了。由于每次移动一个，初始的位置就是 \((1 - k) \bmod (n + 1)\)。负数取模请自行处理。
答案从起始位置输出 \(n\) 个就可以了。
Codes
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 310101
void read(int &p)
{
p = 0;
int k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
{
k = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9')
{
p = p * 10 + c - '0';
c = getchar();
}
p *= k;
return;
}
void write_(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
write_(x / 10);
}
putchar(x % 10 + '0');
}
void writesp(int x)
{
write_(x);
putchar(' ');
}
void writeln(int x)
{
write_(x);
putchar('\n');
}
int T,n,k;
int nums[max_n],vis[max_n];
void solution()
{
read(n),read(k);
for(int i = 1;i <= n;i++)
{
read(nums[i]);
vis[nums[i]] = 1;
}
for(int i = 0;i <= n;i++)
{
if(!vis[i])
{
nums[0] = i;
break;
}
}
int beg = (n + 2 - (k % (n + 1))) % ( n + 1);
// cout<<"@"<<beg<<endl;
for(int i = 1;i <= n;i++,beg++)
{
writesp(nums[beg % (n + 1)]);
}
puts("");
for(int i = 0;i <= n;i++)
{
vis[i] = 0;
}
}
signed main()
{
// freopen("1.in","r",stdin);
read(T);
while(T--)
{
solution();
}
return 0;
}