2022 SCPC 2차 예선 후기

기분이 좋다. 작년보다 약간 쉬운 난이도로 느껴지는데, 만점자 수는 비슷하다. 인원이 줄어든 것인지, 내 실력이 증가한 것인지(당연히 전자다) 모르겠지만, 그래도 작년보다 부담감이 덜 했다.

준비를 진짜 말 그대로 하나도 안 했는데도 불구하고 본선을 비벼볼만 하다는 생각이 든다. 좋다 기분.

 

중간에 토스 챌린지때문에 2시간 뺐음에도 불구하고 시간이 남아서(빨리 포기해서) 가벼운 마음으로 마무리 했다. 이제 졸업하게 되면서 마지막 scpc가 될 것 같은데… 정말 정말 정말 기쁘다.

 

1. 수열 연산(09:15)

• 그리디
• 투포인터

배열에서 [i, j]의 값들을 모두 1씩 증가시키는 연산을 할 수 있다. 각 연산의 비용은 (j - i + 1)이 된다. 배열의 모든 값을 k이상으로 만들고 싶을 때 연산 횟수와 연산 비용을 최소화 시키는 문제다.

 

처음엔 조금 난해해 보였는데, 가장 왼쪽이든 가장 오른쪽이든 한쪽을 고정시키면 update시켜야할 범위가 바로 정해진다. 어쨌거나 연산횟수 최소화가 1 목적이기 때문에 left를 고정시키면 k보다 작은 가장 먼 right를 찾아서 left와 right중 작은 값이 k가 되도록 연산을 적용하면 된다. left와 right를 투포인터로 관리하면 된다.

 

1번 tle를 받았는데, 연산을 정말 일일히 1번씩 하는 방식(미쳤나 진짜…)으로 구현해버리는 바람에 tle를 받았다. k - min(arr[left], arr[right])로 한번에 update하도록해서 시간내에 들어왔다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifndef DEBUG
#define endl '\n'
#endif

#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 100005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int arr[MAX_N];

void solve() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    
    int minValue = *min_element(arr, arr + n);
    if (minValue >= k) cout << pii(0, 0) << endl;
    else {
        cout << k - minValue << ' ';

        int l = 0, r = n - 1;
        ll ans = 0;
        ll plus = 0;
        while (true) {
            while (l < n && arr[l] + plus >= k) ++l;
            while (r >= 0 && arr[r] + plus >= k) --r;
            if (l > r) break;
            ll up = (ll)k - max(arr[l] + plus, arr[r] + plus);
            plus += up;
            ans += (r - l + 1) * up;
        }
        cout << ans << endl;
    }
}

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

    int testcase;
    cin >> testcase;
    for (int tc = 1; tc <= testcase; ++tc) {
        cout << "Case #" << tc << endl;
        solve();
    }

    return 0;
}

 

2. 반 협동게임(09:32)

• 그리디
• 세그먼트 트리
• 펜윅 트리

학생들이 일렬로 서있고, 각 학생의 반 번호가 주어져있다. 반 협동게임의 턴 마다 같은 반에 속한 두 학생이 배열에서 빠져나오게 되는데, i번에 서있던 학생과 j번에 서있던 학생이 빠져나오게 될 경우 j - i점을 얻게 된다. 그리고 학생들이 빠져나오게되어 빈 자리가 발생하면 왼쪽으로 붙어서 빈자리를 메꾸게 된다. 게임에서 얻을 수 있는 최대 점수를 구하는 문제다.

 

보자마자 그리디 풀이가 생각이 났다. 1번과 풀이가 거의 유사한데, 왼쪽에서부터 1명을 선택해서 같은 반에 있는 가장 오른쪽에 있는 학생과 같이 내보내면 최대 점수를 얻게 된다. 빠져나가게 되어서 중간에 빈 자리가 발생하는 경우는 부분합 세그로 1로 마킹해주어서 중간에 빠진 자리 개수를 세어주면 된다.

 

1번과 유사함에도 불구하고 3번이나 틀렸는데, 1번은 그리디 풀이가 맞는지 확인하기 위해 세그트리 없이 naive구현으로 섭테를 긁어보았고, 2번은 초기화를 똑바로 안 해서…

마지막 scpc 대회인데 이제야 init과 solve 함수를 각각 구현해서 처리해주는게 좋다는 걸 깨달았다…

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 300005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int n;
int arr[MAX_N];
vector<int> pos[MAX_N];
int tree[MAX_N * 4];

int update(int index, int value, int id = 1, int nodeLeft = 0, int nodeRight = MAX_N - 1) {
	int mid = (nodeLeft + nodeRight) / 2;
	if (index < nodeLeft || index > nodeRight)
		return tree[id];
	if (nodeLeft == nodeRight)
		return tree[id] = value;
	return tree[id] = update(index, value, id * 2, nodeLeft, mid) + update(index, value, id * 2 + 1, mid + 1, nodeRight);
}

int query(int left, int right, int id = 1, int nodeLeft = 0, int nodeRight = MAX_N - 1) {
	int mid = (nodeLeft + nodeRight) / 2;
	if (right < nodeLeft || left > nodeRight)
		return 0;
	if (left <= nodeLeft && right >= nodeRight)
		return tree[id];
	return query(left, right, id * 2, nodeLeft, mid) + query(left, right, id * 2 + 1, mid + 1, nodeRight);
}

void solve() {
    memset(tree, 0, sizeof(tree));
    for (int i = 0; i < MAX_N; ++i) pos[i].clear();

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        pos[arr[i]].emplace_back(i);
    }
    for (int i = 1; i <= n; ++i)
        sort(all(pos[i]));
    
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if (pos[arr[i]].empty()) continue;
        if (pos[arr[i]].back() <= i) continue;
        int partnerPos = pos[arr[i]].back();
        ans += partnerPos - i - query(i, partnerPos);
        update(partnerPos, 1);
        pos[arr[i]].pop_back();
    }
    cout << ans << endl;
}

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

    int testcase;
    cin >> testcase;
    for (int tc = 1; tc <= testcase; ++tc) {
        cout << "Case #" << tc << endl;
        solve();
    }

    return 0;
}

 

3. ABC(12:43)

• DFS
• DP
• 사이클판별
• SCC

Self cycle이 없는 단방향 그래프에서 간선에 알파벳 3개(A, B, C)가 주어진다. 아무 정점에서 시작해서 다음과 같은 규칙을 만족하도록 간선을 타서 움직여야한다. 알파벳 A이후는 B 간선을, B이후에는 C간선을, C이후에는 A간선을 타야한한다. 하나의 간선을 여러번 탈 수도 있다.

이렇게 간선을 타서 문자열을 만들게 되었을 때 최대로 만들 수 있는 문자열의 길이을 구해야한다. 다만, 딱 K번 위 규칙을 무시하고 문자열에 문자를 추가하지않으며 간선을 탈 수 있는데, K는 0, 1, 2 또는 무한대(-1) 로만 주어진다. 만약 문자열의 길이를 무한히 만들 수 있으면 -1을 출력해야한다.

 

굉장히 까다로웠다. 먼저 딱 봐도 따로 처리해줘야할 것 같은 K가 무한대인 경우를 제외하고 생각해보자. K가 0이든 1이든 2이든 DFS + DP(caching)로 해결이 가능하다. DP[i][j][k]를 k번 스킵해서 i번째 노드에 있을 때 j문자를 타야하는 경우로 정의해보자. 그럼

DP[i][j][k] = max(
DP[nxt][(j + 1) % 3][k] + 1, (j와 nxt로 가는 edge의 알파벳이 같은 경우)
DP[nxt][j][k + 1] (j와 nxt로 가는 edge의 알파벳이 다른 경우)
)

로 정의할 수 있다.

 

다만, 이렇게 DP 테이블을 채우기 위해서 DFS(재귀)를 돌리다가 문자열이 무한대로 만들어지는 경우를 판별해야하는데, 이는 사이클을 판별을 통해서(finished 체크) 무한대임을 판별할 수 있다.

진짜 문제는 K가 -1로 무한대일 때이다. K가 0, 1, 2일 때에는 DP테이블이 작기 때문에 가능하지만, 무한대 일때는 공간복잡도가 O($n^2$)이 되기 때문에 DP로는 불가능하다. 완전히 다른 로직으로 짜야하는 것을 대충 유추해볼 수 있다.

 

무한히 스킵이 가능하기 때문에, 사이클을 묶었을 때 A, B, C에 해당하는 간선이 있으면 무조건 무한한 문자열을 만들 수 있다. 반면, 그렇지 않은 경우는 무슨 수를 쓰더라도 문자열 길이가 유한하게 만들어진다. SCC로 사이클을 모두 묶어주고, 사이클에 있는 문자를 마스킹해주어서 문자열을 무한하게 만들 수 있는 경우만 필터링해주고, 나머지 경우는 K가 0, 1, 2일 때 처럼 DP를 돌리면 된다. DP 점화식은 완전히 동일하고, 사이클 코드만 빠지면 된다.

 

SCC를 쓰면 바로 해결된다는 것은 빠르게 파악했는데, 굳이 SCC를 쓰지 않아도 풀릴 것 같아서 오기로 SCC를 안 박고 있다가 조금 많이 늘어졌다. 특히 일반 DFS가 아니라 DP이기 때문에 사이클 판별을 일반적인 방법으로 하면 안 될 것 같아서 이것 저것 많이 건드려봤는데, 일반적인 방법으로 해도 된다….

 

문제 자체는 어렵지 않았으나, 케이스워킹같은 느낌이 들어서 구현이 상당히 귀찮았다. 마찬가지로 3번 틀리고 4번째 시도에 맞았는데, SCC를 박자마자 바로 맞았다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifndef DEBUG
#define endl '\n'
#endif

#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 100005
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int n, m, k;
vector<pii> adj[MAX_N];

int dp[MAX_N][3][3];
bool finished[MAX_N][3][3];
bool isInfinity = false;

int dp2[MAX_N][3];

int cnt; // cnt : dfsn세기 위해 필요
int dfsn[MAX_N]; // dfsn
bool finished2[MAX_N]; // scc가 구성됬는지 체크하는 배열
stack<int> st; // scc구성하기위해 필요
int sn[MAX_N]; // i번째 vertex가 들어간 scc의 번호
vector<vector<int>> scc; // scc와 scc의 원소들을 저장
int sccValue[MAX_N];

int dfs(int here) {
	dfsn[here] = ++cnt;
	st.push(here);

	int result = dfsn[here];
	for (int i = 0; i < adj[here].size(); i++) {
		int next = adj[here][i].first;

		if (dfsn[next] == 0)
			result = min(result, dfs(next));
		else if (!finished2[next])
			result = min(result, dfsn[next]);
	}

	if (result == dfsn[here]) {
		vector<int> curScc;

		while (true) {
			int top = st.top();
			st.pop();
			curScc.push_back(top);
			finished2[top] = true;
			sn[top] = scc.size();

			if (top == here)
				break;
		}

		scc.push_back(curScc);
	}

	return result;
}

void init() {
    for (int i = 0; i < MAX_N; ++i) adj[i].clear();
    memset(dp, -1, sizeof(dp));
    memset(finished, false, sizeof(finished));
    isInfinity = false;

    
    memset(dp2, -1, sizeof(dp2));
    memset(finished2, false, sizeof(finished2));
    memset(dfsn, 0, sizeof(dfsn));
    memset(sn, 0, sizeof(sn));
    memset(sccValue, 0, sizeof(sccValue));
    for (int i = 0; i < scc.size(); ++i) scc[i].clear();
    scc.clear();
    while(st.size()) st.pop();
    cnt = 0;

}

int getDp(int i1, int i2, int i3) {
    if (i3 > k) return -INF;

    int& ret = dp[i1][i2][i3];
    if (ret != -1) {
        if (i3 == 0 && finished[i1][i2][i3] == false) {
            isInfinity = true;
        }
        return ret;
    }

    ret = 0;
    for (pii& edge : adj[i1]) {
        if (isInfinity) break;

        int nxt = edge.first;
        int alphabet = edge.second;
        if (i2 != alphabet) ret = max(ret, getDp(nxt, i2, i3 + 1));
        else ret = max(ret, getDp(nxt, (i2 + 1) % 3, i3) + 1);
    }
    finished[i1][i2][i3] = true;
    return ret;
}

int getDp2(int i1, int i2) {
    int& ret = dp2[i1][i2];
    if (ret != -1) {
        return ret;
    }

    ret = 0;
    for (pii& edge : adj[i1]) {
        if (isInfinity) break;
        int nxt = edge.first;
        int alphabet = edge.second;
        
        if (i2 != alphabet) ret = max(ret, getDp2(nxt, i2));
        else ret = max(ret, getDp2(nxt, (i2 + 1) % 3) + 1);
    }
    return ret;
}

void solve() {
    cin >> n >> m >> k;
    while(m--) {
        int a, b;
        char c;
        cin >> a >> b >> c;
        c -= 'A';
        adj[a].emplace_back(b, c);
    }
    for (int i = 1; i <= n; ++i) {
        sort(all(adj[i]));
        adj[i].erase(unique(all(adj[i])), adj[i].end());
    }

    int ans = 0;
    if (k == -1) {
        for (int i = 1; i <= n; ++i) {
            if (dfsn[i] == 0) {
                dfs(i);
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (auto e : adj[i]) {
                int nxt = e.first;
                int alpha = e.second;
                if (sn[i] == sn[nxt]) sccValue[sn[i]] |= (1 << alpha);
            }
            if (sccValue[sn[i]] == 7) {
                isInfinity = true;
                break;
            }
        }
        if (!isInfinity) {
            for (int i = 1; i <= cnt; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (dp2[i][j] == -1) {
                        ans = max(ans, getDp2(i, j));
                    }
                }
            }
        }
    } else {
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j < 3; ++j){
                if (dp[i][j][0] == -1) {
                    ans = max(ans, getDp(i, j, 0));
                    if (isInfinity) {
                        break;
                    }
                }
            }
        }
    }
    cout << (isInfinity ? -1 : ans) << endl;
}

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

    int testcase;
    cin >> testcase;
    for (int tc = 1; tc <= testcase; ++tc) {
        cout << "Case #" << tc << endl;
        init();
        solve();
    }

    return 0;
}

 

4. 직사각형(16:25)

N x N 크기의 2차원 배열에 1 부터 N*N 까지의 서로 다른 수가 들어가있다. 모든 r1, r2, c1, c2(1 ≤ r1 ≤ r2 ≤ N, 1 ≤ c1 ≤ c2 ≤ N) 범위에 대해 범위 안에 있는 수들을 정렬했을 때 연속적인 모든 범위의 개수를 구하는 문제다.

보자마자 2D 세그부터 붙여넣기했다. 수가 모두 distinct하므로 어떤 범위에 대해서 min값과 max값을 알 수 있으면 범위의 크기 = (max값 - min값)이 되면 조건에 맞는 범위가 된다.

이를 min, max를 보관하는 2D세그를 이용해서 긁으려 했는데, O($N^4 log(N^2)$)으로 테케 2번까지 시간내에 들어올 줄 알았으나, 상수항이 상당히 커서 테케 1번만 긁을 수 있었다.

row를 O($N^2$)으로 고정시키고, O($N^2$)으로 column을 탐색할 때 1D 세그를 row마다 만들면 O($N^2 log(N)$)에 가능하다. 다만, top-down 세그를 쓰면 TLE가 뜰 것 같아서 bottom-up 세그를 급하게 긁어와서 N개 만들어서 적용시켰다. 테케 2번 통과 시간을 보니 1초도 안 걸려서 top-down을 써도 크게 문제는 없었을 것 같다.

정해는 sparse table + 세그 라는데… 다이아 5정도는 될 것 같다. 당장 테케 3번 점수가 188점?으로 굉장히 차이가 많이나서 테케2번까지만 긁고 고민도 하지 않았다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifndef DEBUG
#define endl '\n'
#endif

#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 260
#define MOD 1'000'000'007
#define MOD2 1'000'000'009

int n;
int arr[MAX_N][MAX_N];
int minTree[MAX_N][MAX_N * 4];
int maxTree[MAX_N][MAX_N * 4];

void treeInit() {
    for (int column = 0; column < n; ++column) {
        for (int i = 0; i < n; ++i) {
            minTree[column][i + n] = arr[i][column];
            maxTree[column][i + n] = arr[i][column];
        }
    }
    for (int column = 0; column < n; ++column) {
        for(int i = n - 1; i > 0; i--) {
            minTree[column][i] = min(minTree[column][i << 1], minTree[column][i << 1 | 1]);
            maxTree[column][i] = max(maxTree[column][i << 1], maxTree[column][i << 1 | 1]);
        }
    }
}

pii query(int column, int l, int r) {
    pii res = {INF, -INF};
    for(l += n, r += n; l <= r; l >>= 1, r >>= 1) {
        if(l & 1) {
            res.first = min(res.first, minTree[column][l]);
            res.second = max(res.second, maxTree[column][l]);
            ++l;
        }
        if(!(r & 1)) {
            res.first = min(res.first, minTree[column][r]);
            res.second = max(res.second, maxTree[column][r]);
            --r;
        }
    }
    return res;
}

void init() {

}

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> arr[i][j];
        }
    }
    treeInit();
    
    if (n > 64) {
        cout << 0 << endl;
        return;
    }

    ll ans = 0;
    for (int r1 = 0; r1 < n; ++r1) {
        for (int r2 = r1; r2 < n; ++r2) {
            for (int c1 = 0; c1 < n; ++c1) {
                pii ret = {INF, -INF};
                for (int c2 = c1; c2 < n; ++c2) {
                    /* [r1, r2] * [c1, c2] 의 최소, 최대 */
                    pii temp = query(c2, r1, r2);
                    ret.first = min(ret.first, temp.first);
                    ret.second = max(ret.second, temp.second);
                    if ((r2 - r1 + 1) * (c2 - c1 + 1) == ret.second - ret.first + 1) ++ans;
                }
            }
        }
    }
    cout << ans << endl;
}

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

    int testcase;
    cin >> testcase;
    for (int tc = 1; tc <= testcase; ++tc) {
        cout << "Case #" << tc << endl;
        init();
        solve();
    }

    return 0;
}

 

5. 황금 카드(18:54)

N개 종류의 카드가 총 P장 들어있는 카드팩이 여러개 있다. 여기서 i번째 종류 카드는 p_i장 들어있다. 하나의 카드팩에 정확히 하나의 카드가 황금색으로 장식되어 있는데, 각 카드가 황금색일 확률은 동일하다(1/P). 카드팩을 1~K개 열었을 때 얻을 수 있는 서로 다른 종류의 황금색 카드의 개수의 기대값을 구하는 문제다.

 

3차원 DP로 O($N^5$)으로 테케 1번만 뚫었다. 총 K개의 카드를 뽑을 수 있고, 각 카드의 종류는 총 N개 있으므로 K개의 슬롯이 있고, 각 슬롯마다 N개의 카드가 채워질 수 있다고 생각할 수 있다. 따라서 DP테이블을 아래와 같이 정의할 수 있다.

DP[i][j][k] = i번 카드를 j번째 칸에 채울때 서로 다른 카드의 개수가 k개 인 경우

서로다른 카드의 개수가 필요한 이유는 최종적으로 카드 선택이 1 1 1 2 2 처럼 되었을 때, 서로 다른 카드 개수가 2개 이므로 기댓값에 2를 곱해주어야 하기 때문이다. 그리고 DP테이블을 이렇게 구성할 경우 카드의 순서가 고려되지 않으므로 팩토리얼을 곱해주어서 순서를 고려해주어야한다. 1 1 1 2 2의 경우 최종적으로 5! / 3! / 2!을 해주어야한다.

이런식으로 1~K를 모두 돌면서 구해주고, 테이블 하나를 채울 때 카드를 연속해서 채울것 이기 때문에 O(N)의 for loop이 하나 추가되어서 테이블 크기 * O(N) * O(K)가 걸린다.

 

경우의 수와 확률를 정말 못 하기 때문에 고생을 좀 했다. 2시간 반만에 풀었는데, 테케 2번이 1번보다 점수가 낮음에도 불구하고 느낌만 살짝 올 뿐, 끝까지 생각이 정리가 안 되고 멘탈도 많이 나간 상태라 밥먹고 대회를 마루리했다. 총 2번 제출했는데, 첫 제출 때 DP테이블 구성이 달라 비트마스킹을 사용해서 많이 느렸었다. 조금 거슬려서 다시 DP테이블을 구성하고 재 제출했다.

#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
    os << pai.first << ' ' << pai.second;
    return os;
}
template<typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
    is >> pai.first >> pai.second;
    return is;
}

#ifndef DEBUG
#define endl '\n'
#endif

#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 12
#define MOD 998'244'353
#define MOD2 1'000'000'009

int n, k;
ll arr[MAX_N];
ll dp[MAX_N][MAX_N * 5][MAX_N];

ll fact[MAX_N * 5];

ll ppow(ll a, int b){
    ll ret = 1;
    a %= MOD;
    while (b) {
        if (b % 2) {
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        b /= 2;
    }
    return ret;
}

ll mod(ll a, ll b) {
    a %= MOD;
    b %= MOD;
    return (a * ppow(b, MOD - 2)) % MOD;
}

ll getDp(int i1, int i2, int i3) {
    if (i1 == n) {
        if (i2 != k) return 0;
        return (i3 * fact[k]) % MOD;
    }

    ll& ret = dp[i1][i2][i3];
    if (ret != -1) return ret;

    ret = 0;
    ll mult = 1;
    for (int i = 0; i <= k - i2; ++i) {
        ret += mod(getDp(i1 + 1, i2 + i, i3 + (i != 0)) * mult % MOD, fact[i]);
        ret %= MOD;
        mult = (mult * arr[i1]) % MOD;
    }
    return ret % MOD;
}

void init() {
    memset(dp, -1, sizeof(dp));
}

void solve() {
    fact[0] = 1;
    for (int i = 1; i < MAX_N * 5; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    if (n > 10 || k > 50) {
        cout << -1 << endl;
        return;
    }

    ll ans = 0;
    int K = k;
    for (int i = 1; i <= K; ++i) {
        init();
        k = i;
        ans ^= getDp(0, 0, 0);
    }
    cout << ans << endl;
}

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

    int testcase;
    cin >> testcase;
    for (int tc = 1; tc <= testcase; ++tc) {
        cout << "Case #" << tc << endl;
        init();
        solve();
    }

    return 0;
}