# E. Mexification [문제 링크](https://codeforces.com/contest/2137/problem/E) ## Problem Statement You are given an array $a$ of size $n$ and an integer $k$. You do the following procedure $k$ times: - For each element $a_i$, you set $a_i$ to $\operatorname{mex}(a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n)$. In other words, you set $a_i$ to the $\operatorname{mex}$ of all other elements in the array. **This is done for all elements in the array at the same time.** Please find the sum of elements in the array after all $k$ operations. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line contains two integers $n$ and $k$ ($2 \leq n \leq 2 \cdot 10^5,\ 1 \leq k \leq 10^9$) — the number of elements in $a$ and the number of operations done. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output the sum of elements after all $k$ operations on a new line. ## Footnotes The minimum excluded (MEX) of a collection of integers $d_1, d_2, \ldots, d_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $d$. ## 풀이 몇번정도 시뮬레이션 해보면 2번마다 똑같은 모양이 반복된다는 것을 알 수 있다. 그래서 5번정도 시뮬레이션한 후 남은 k mod 2만큼 추가로 이동시켜주었다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n, k; cin >> n >> k; vector<int> a(n), cnt(n+2); for(int i=0;i<n;i++) { cin >> a[i]; cnt[a[i]]++; } int goal; for(int i=0;i<5;i++) { if(k) { goal=n+1; for(int i=0;i<=n;i++) { if(cnt[i]==0) { goal=i; break; } } for(int i=0;i<n;i++) { if(goal<a[i] || cnt[a[i]]!=1) { a[i]=goal; } } cnt = vector<int>(n+2); for(int i=0;i<n;i++) cnt[a[i]]++; goal=n+1; for(int i=0;i<=n;i++) { if(cnt[i]==0) { goal=i; break; } } k--; } } ll sum=0; for(int i=0;i<n;i++) { if(k%2==0 || cnt[a[i]]==1) sum += a[i]; else sum += goal; } cout << sum << '\n'; } } ```