SCPC 2022 2차 풀이
SCPC 2022 2차 대회가 8월 6일 오전 9시부터 12시간동안 진행되었다.
SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다.
이 게시글에서는 해당 문제들의 풀이를 다룬다.
1. 수열 연산
문제를 요약하면, 주어진 수열 $A$의 모든 수를 주어진 수 $K$ 이상으로 만들기 위해서 최소 횟수의 연산을 사용하고, 이 때 가능한 총 비용의 최솟값을 구하는 문제다. 한 연산은 연속된 구간의 모든 수를 $1$ 증가시키고, 이 연산의 비용은 구간의 길이이다.
연산을 수열 전체에 사용한다고 생각하면 사용해야하는 연산의 횟수는 $\max(K - \min A, 0)$이다. 이 이하로 사용해서는 최솟값을 $K$ 이상으로 만들 수 없다. 이제 가능한 총 비용의 최솟값을 구하자.
이전 관찰로, 우리는 연산을 수열의 최솟값에 해당하는 인덱스에만 증가시켜주면 된다는 것을 알 수 있다(최솟값이 늘어나면, 필요한 횟수가 줄어든다.) 그렇기에 최솟값에 해당하는 모든 인덱스를 포함하는 가장 짧은 구간에 연산을 사용하면 된다는 것을 알 수 있다. 이를 그대로 구현하면 $O((\max A) \times N)$ 정도의 시간이 든다.
원래 최솟값이었던 수는 항상 연산에 포함되어있다는 사실을 주목하자. 각 인덱스가 증가되는 횟수는 이 값을 최대로 해서 바깥으로 갈수록 줄어드는 모양이라는 것을 알 수 있다(연산의 구간이 연속되어있다.) 이를 이용해서 각 인덱스가 증가되는 횟수를, 자기 이전 혹은 이후 인덱스가 증가되는 횟수에 따라 계산해주면 된다. 시간 복잡도는 $O(N)$ 이다.
2. 반 협동 게임
문제를 요약하면, 수열 $A$가 주어지는데 이 수열에 있는 수 중 같은 수 두 개를 잡아서 제거할 수 있다. 이렇게 제거할 때마다, 제거한 두 수의 인덱스 차에 해당하는 점수를 얻는다. 가능한 점수의 최댓값은 무엇인가?
수가 같은 $4$개의 인덱스 $a < b < c < d$가 존재하고, 제거 연산이 $(a, d) \rightarrow (b, c)$순이 아니면, 제거 연산을 $(a, d) \rightarrow (b, c)$순으로 바꾸어 주는 것으로 더 높은 점수를 얻을 수 있다. 이를 통해, 우리는 같은 수에서 제거되는 쌍을 바깥쪽부터 차례로 만드는 것이 가장 이득이라는 것을 알 수 있다.
네 인덱스 $a < b < c < d$에 대해, $(a, c)$와 $(b, d)$는 어느것을 먼저 수행해도 상관 없고, $(a, d)$와 $(b, c)$는 $(a, d)$의 제거 연산을 먼저 수행하는 것이 이득이라는 것을 알 수 있다. 이를 통해, 우리는 정해진 쌍을 제거하는 연산을 두 인덱스 차이 순서대로 실행하면, 가능한 최고의 점수를 얻는다는 것을 알 수 있다.
이를 세그먼트 트리 등을 이용하여 시뮬레이션하면, 시간복잡도는 $O(N \log N)$이다.
3. ABC
문제를 요약하면, 간선에 $A, B, C$중 하나가 써있는 유향그래프가 주어진다. 이 중, 아무 정점에서나 시작해서, 간선을 타고가며 간선에 있는 글자를 만나는 순서대로 붙여서 문자열을 만드는데, $A$ 다음에는 $B$, $B$ 다음에는 $C$, $C$ 다음에는 $A$가 와야한다. 글자는 항상 붙여야하지만, 주어진 $K = 0, 1, 2$ 혹은 $\infty$번만큼 간선에서 글자를 붙이지 않아도 된다.이렇게 만들어지는 문자열의 최대 길이를 구하여라(문자열이 무수히 길어질 수 있다.)
$D[a][k][c]$를 현재 $a$ 정점에 있고, $k$번 스킵할 수 있으며, 다음 간선의 문자가 $c$일때 가능한 최대 길이라고 정의하자.
다음 문자를 스킵하는 경우와 경우하지 않는 경우의 두 가지가 있다.
- 문자가 일치하는 경우: $a \xrightarrow{c} b$에 대해서 $1+D[b][k][next(c)]$, $next(c): c$의 다음 문자
- 문자가 일치하지 않는 경우 :$a \xrightarrow{c} b$에 대해서 $D[b][k-1][c]$. $(k > 0)$
현재 위치에서 끝낼수 있으므로, 0과 위 값들의 최댓값을 구하면 된다.
이를 동적계획법을 사용하여 해결하면 되는데, 정의가 순환적이라는 문제가 생긴다. 즉 이전 방문한 DP상태를 다음에도 방문할 수 있다는 의미이다. 이를 위해서 DP를 순서대로 돌리는 것이 아니라, memoization을 활용하고, 다음과 같은 방법으로 처리한다.
- 현재 상태를 방문한 적이 없는 경우, 위 DP식을 이용해 답을 찾는다.
- 현재 상태에서 정답을 찾은 적이 있을경우, 기존에 저장한 해당 정답을 반환한다.
- 현재 상태에서 정답을 찾은 적이 없는데 이전에 방문한 적이 있는 경우, 현재 상태에서 다시 정답으로 돌아오는 방법이 있다는 의미이다. 이 경우에는 방문 횟수가 무한할 수 있다.
$k = 0, 1, 2$일 때는 방문 횟수가 무한하면 문자열의 길이가 무한하지만, $k=-1$일 때는 문자열의 길이가 무한하지 않을 수 있다(가령이면, $A, B$가 있는 사이클을 무한히 반복한다.) 이를 처리하는 방법은 다양한 방법이 있는데 하나는 SCC를 구해서 정점을 압축하는 방식이다. 다른 방법은 방문한 사이클이 유효하게 문자를 붙여오면서 한바퀴를 돌았는지를 판단하는 방법이 있다. 뒤의 방법을 조금 더 설명한다.
문자를 붙일 때마다(즉, 1번 경우만) 깊이가 $1$씩 깊어지도록 코드를 작성하면 같은 상태를 다시 방문했을 때 깊이가 깊어졌으면 문자를 붙이는 사이클이 존재하므로 답은 무한하다. 그렇지 않으면, "사이클은 존재하지만, 해당 사이클을 방문하면서 문자를 붙일수 없는 상태"이기 때문에, 답을 현재 상태에서 갱신하지 않는다(즉, 0을 반환한다.)
이와 같이 구현하면 시간복잡도는 $k$가 유한할 때 $O(kM)$이 된다. $k = \infty$ 일 때는 $k$가 가질 수 있는 상태가 $\infty$ 하나로 유일하기 때문에 시간복잡도가 $O(M)$이다.
4. 직사각형
문제를 요약하면, $1$부터 $N^2$까지의 수가 하나씩 써있는 $N \times N$ 격자에서 꽉찬 직사각형의 수를 세는 것이다. 꽉찬 직사각형이란 이 영역 안의 수들을 재배열해서 연속적으로 만들 수 있으면 꽉 찬 직사각형이라고 한다.
어떤 직사각형이 꽉 찬 직사각형인지 판단하는 법을 생각해보자. 우리가 직사각형 내부 칸의 최솟값과 최댓값을 안다면 직사각형 안에는 최솟값부터 최댓값까지 모든 수가 다 존재해야 한다. 즉, 최댓값에서 최솟값을 뺀 값에 $1$을 더한 값이 면적과 같은지 확인하면 된다.
이제 직사각형의 최솟값 $T$를 고정시켜보자. 해당 수만 포함하는 직사각형은 자명하게 꽉 찬 직사각형이다. 이제 다음으로 큰 꽉 찬 직사각형을 구해보자. 이 꽉 찬 직사각형은 상하좌우중 한 방향으로 늘어나야한다. 이 중 "늘어나는 영역의 최솟값과 최댓값"에 대해 살펴보자.
- 늘어나는 영역의 최솟값이 $T$이하이면 해당 영역을 포함하면 직사각형의 최솟값이 $T$가 아니기 때문에 해당 방향으로 늘어나날 수 없다.
- 늘어나는 영역의 최댓값중 가장 작은 값 $C$쪽으로는 항상 늘어나야 한다. 다른 방향으로만 늘이게 되면 최댓값은 $C$보다 큰데 $C$를 포함하지 않게 된다.
각 수에 대해 직사각형 영역은 $2N-1$번 늘어나므로, 총 $2N^3-N^2$번 미만 늘어난다. $O(N^3)$에 전처리를 해서 늘어나는 구간에 대한 정보를 $O(1)$에 계산할 수 있으면, 시간복잡도 $O(N^3)$에 문제를 풀 수 있다.
5. 황금카드
문제를 요약하면, 카드가 $N$ 종류가 있고 각 카드가 뽑힐 확률은 $\frac{p_i}{P}$이다. $(P = p_1 + \cdots + p_N)$ 카드를 $k$장 뽑았을 때 뽑힌 카드 종류 개수의 기댓값을 $E_k$라고 하면, $k = 1, \cdots, K$에 대해서 $P^k E_k$를 $998,244,353$으로 나눈 나머지를 구하는 문제이다.
일단, $P^k E_k$를 구하는 식을 써보자. 카드 종류 개수의 기댓값은 기댓값의 선형성을 이용하면 $1$번 카드가 뽑힐 확률 + $2$번 카드가 뽑일 확률 + $\cdots$ + $N$번 카드가 뽑힐 확률로 계산할 수 있다. 여사건인 $i$번 카드가 $k$번 중에 한 번도 뽑히지 않을 확률은 $\left(\frac{P-p_i}{P}\right)^k$이므로 $i$번 카드가 뽑힐 확률은 $1-\left(\frac{P-p_i}{P}\right)^k$이다. $P^k E_k$는 이를 $i = 1, \cdots, N$에 대해 더한 $\sum_{i=1}^N P^k - (P-p_i)^k$와 같이 계산할 수 있다. 이를 직접 계산하면 $O(NK)$가 된다.
이제 시간복잡도를 줄여보자. 위 식을 정리하면 $N P^k - \sum_{i=1}^N q_i^k$ $(q_i = P-p_i)$가 된다. $F_k = \sum_{i=1}^N q_i^k$을 모든 $i = 1, \cdots, K$에 대해 빠르게 구해야 한다. 생성함수 $f(x) = \sum_{k=0}^{\infty} F_k x^k$를 생각하자. $f(x) = \sum_{k=0}^{\infty} \left( \left( \sum_{i=1}^N q_i^k \right) x^k \right) = \sum_{i=1}^N \left( \sum_{k=0}^{\infty} \left( (q_i x)^k \right) \right) = \sum_{i=1}^N \frac{1}{1-q_i x}$가 된다.
$\sum_{i=1}^N \frac{1}{1-q_i x}$을 분수형태로 구하는 법은, 좌우 절반으로 나눠서 왼쪽이 $\frac{A(x)}{B(x)}$, 오른쪽이 $\frac{C(x)}{D(x)}$일 때 $\frac{A(x)D(x) + B(x)C(x)}{B(x)D(x)}$로 구하면 되고, 다항식 곱셈을 세 번 사용하면 된다. 이를 구하는 시간복잡도는 $T(N) = 2T(N/2) + O(N \log N)$이고, $T(N) = O(N \log^2 N)$이다.
이제, $\frac{A(x)}{B(x)}$와 같은 식을 실제로 계산해야 하는데, 다항식 나눗셈을 사용하면 이 값을 $K$번째 항까지 $O(K \log K)$에 계산할 수 있다. $f(x)$의 각 항을 구할 수 있으니, 각 $F_k$를 알 수 있다.
시간복잡도는 $O(N \log^2 N + K \log K)$이다.
코드
1번
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
pair<int, int64_t> solve(int K, vector<int> A)
{
int N = A.size();
for (int &a : A)
a = max(0, K - a);
vector<int> L(N), R(N);
L[0] = A[0];
for (int i = 1; i < N; i++)
L[i] = max(L[i - 1], A[i]);
R[N - 1] = A[N - 1];
for (int i = N - 2; i >= 0; i--)
R[i] = max(R[i + 1], A[i]);
int64_t ans = 0;
for (int i = 0; i < N; i++)
ans += min(L[i], R[i]);
return {*max_element(A.begin(), A.end()), ans};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
int N, K;
cin >> N >> K;
vector<int> A(N);
for (int &a : A)
cin >> a;
auto [f, s] = solve(K, A);
cout << "Case #" << tc << "\n"
<< f << " " << s << endl;
}
}
|
cs |
2번
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
struct Seg
{
int N;
vector<int> idx;
Seg(vector<int> V)
{
N = 1;
while (N < (int)V.size())
N *= 2;
idx.resize(2 * N);
copy(V.begin(), V.end(), idx.begin() + N);
for (int i = N - 1; i > 0; i--)
idx[i] = idx[2 * i] + idx[2 * i + 1];
}
int get(int a, int b)
{
a += N, b += N;
int ans = 0;
while (a <= b)
{
if (a % 2 == 1)
ans += idx[a++];
if (b % 2 == 0)
ans += idx[b--];
a /= 2;
b /= 2;
}
return ans;
}
void set(int a, int v)
{
idx[a += N] = v;
while ((a = a / 2))
idx[a] = idx[2 * a] + idx[2 * a + 1];
}
};
int64_t solve(vector<int> A)
{
int N = A.size();
vector<int> used(N, 1);
vector<vector<int>> idx(N);
for (int i = 0; i < N; i++)
idx[A[i] - 1].push_back(i);
vector<pair<int, int>> P;
for (auto &V : idx)
{
int K = V.size();
for (int i = 0; i < K / 2; i++)
{
P.emplace_back(V[i], V[K - 1 - i]);
used[V[i]] = used[V[K - 1 - i]] = 0;
}
}
sort(P.begin(), P.end(), [&](pair<int, int> a, pair<int, int> b)
{ return a.second - a.first < b.second - b.first; });
Seg S = used;
long ans = 0;
for (auto [l, r] : P)
{
ans += 1 + S.get(l, r);
S.set(l, 1);
S.set(r, 1);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
int N;
cin >> N;
vector<int> A(N);
for (int &a : A)
cin >> a;
cout << "Case #" << tc << "\n"
<< solve(A) << endl;
}
}
|
cs |
3번
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
int solve(int N, int K, const vector<vector<pair<int, int>>> &G)
{
bool inf = K == -1;
if (inf)
K = 0;
vector<vector<vector<int>>> ans(N, vector<vector<int>>(1 + K, vector<int>(3, -1))), vis = ans;
function<int(int, int, int, int)> dfs = [&](int a, int k, int c, int d)
{
if (ans[a][k][c] != -1)
return ans[a][k][c];
if (vis[a][k][c] == d)
return 0;
if (vis[a][k][c] > 0)
return -1;
vis[a][k][c] = d;
int ret = 0;
for (auto [v, t] : G[a])
{
if (t == c)
{
int res = dfs(v, k, c == 2 ? 0 : c + 1, d + 1);
if (res == -1)
return -1;
ret = max(ret, 1 + res);
}
if (k > 0 || inf)
{
int res = dfs(v, inf ? k : k - 1, c, d);
if (res == -1)
return -1;
ret = max(ret, res);
}
}
return ans[a][k][c] = ret;
};
int ret = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < 3; j++)
{
int v = dfs(i, K, j, 1);
if (v == -1)
return -1;
ret = max(ret, v);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
int N, M, K;
cin >> N >> M >> K;
vector<vector<pair<int, int>>> G(N);
for (int i = 0; i < M; i++)
{
int a, b;
char c;
cin >> a >> b >> c;
a--;
b--;
c -= 'A';
G[a].emplace_back(b, c);
}
cout << "Case #" << tc << "\n"
<< solve(N, K, G) << endl;
}
}
|
cs |
4번
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int solve(const vector<vector<int>> &A)
{
int N = A.size();
vector<vector<vector<int>>> Hx(N, vector<vector<int>>(N, vector<int>(N)));
auto Vx = Hx, Hn = Hx, Vn = Hx;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = j; k < N; k++)
if (j == k)
{
Hx[i][j][k] = Hn[i][j][k] = A[i][k];
Vx[i][j][k] = Vn[i][j][k] = A[k][i];
}
else
{
Hx[i][j][k] = max(Hx[i][j][k - 1], A[i][k]);
Hn[i][j][k] = min(Hn[i][j][k - 1], A[i][k]);
Vx[i][j][k] = max(Vx[i][j][k - 1], A[k][i]);
Vn[i][j][k] = min(Vn[i][j][k - 1], A[k][i]);
}
int ans = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
int L = j, R = j, U = i, D = i, T = A[i][j], C = A[i][j];
++ans;
while (true)
{
int ls = (L == 0 || Vn[L - 1][U][D] < T) ? N * N + 1 : Vx[L - 1][U][D];
int rs = (R == N - 1 || Vn[R + 1][U][D] < T) ? N * N + 1 : Vx[R + 1][U][D];
int us = (U == 0 || Hn[U - 1][L][R] < T) ? N * N + 1 : Hx[U - 1][L][R];
int ds = (D == N - 1 || Hn[D + 1][L][R] < T) ? N * N + 1 : Hx[D + 1][L][R];
int mn = min({ls, rs, us, ds});
if (mn == N * N + 1)
break;
C = max(C, mn);
if (mn == ls)
--L;
else if (mn == rs)
++R;
else if (mn == us)
--U;
else if (mn == ds)
++D;
if ((R - L + 1) * (D - U + 1) == C - T + 1)
++ans;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
int N;
cin >> N;
vector<vector<int>> V(N, vector<int>(N));
for (auto &y : V)
for (int &x : y)
cin >> x;
cout << "Case #" << tc << "\n"
<< solve(V) << endl;
}
}
|
cs |
5번
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
struct Mint
{
static const int MOD = 998'244'353;
static const int prr = 3;
Mint() : _v(0) {}
Mint(int v) : _v((v % MOD + MOD) % MOD) {}
int val() const { return _v; }
Mint &operator+=(const Mint &rhs)
{
_v += rhs._v;
if (_v >= MOD)
_v -= MOD;
return *this;
}
Mint &operator-=(const Mint &rhs)
{
_v -= rhs._v;
if (_v < 0)
_v += MOD;
return *this;
}
Mint &operator*=(const Mint &rhs)
{
_v = (long long)_v * rhs._v % MOD;
return *this;
}
Mint &operator/=(const Mint &rhs) { return *this = *this * rhs.inv(); }
Mint operator+() const { return *this; }
Mint operator-() const { return Mint() - *this; }
Mint pow(long long n) const
{
assert(0 <= n);
Mint x = *this, r = 1;
while (n)
{
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
Mint inv() const
{
assert(_v);
return pow(MOD - 2);
}
friend Mint operator+(const Mint &lhs, const Mint &rhs) { return Mint(lhs) += rhs; }
friend Mint operator-(const Mint &lhs, const Mint &rhs) { return Mint(lhs) -= rhs; }
friend Mint operator*(const Mint &lhs, const Mint &rhs) { return Mint(lhs) *= rhs; }
friend Mint operator/(const Mint &lhs, const Mint &rhs) { return Mint(lhs) /= rhs; }
friend bool operator==(const Mint &lhs, const Mint &rhs) { return lhs._v == rhs._v; }
friend bool operator!=(const Mint &lhs, const Mint &rhs) { return lhs._v != rhs._v; }
static Mint w(int n)
{
assert((MOD - 1) % n == 0);
return Mint(prr).pow((MOD - 1) / n);
}
private:
int _v;
};
template <class F>
void fft(vector<F> &a, bool inv)
{
int N = a.size(), j = 0;
vector<F> roots(N / 2);
for (int i = 1; i < N; i++)
{
int bit = N >> 1;
while (j >= bit)
{
j -= bit;
bit >>= 1;
}
j += bit;
if (i < j)
swap(a[i], a[j]);
}
F w = F::w(N);
if (inv)
w = w.inv();
for (int i = 0; i < N / 2; i++)
roots[i] = i ? w * roots[i - 1] : F(1);
for (int i = 2; i <= N; i <<= 1)
{
int step = N / i;
for (int j = 0; j < N; j += i)
for (int k = 0; k < i / 2; k++)
{
F u = a[j + k], v = a[j + k + i / 2] * roots[step * k];
a[j + k] = u + v;
a[j + k + i / 2] = u - v;
}
}
}
template <class F>
vector<F> convolution(vector<F> a, vector<F> b)
{
int n = int(a.size()), m = int(b.size());
if (!n || !m)
return {};
int z = 2;
while (z < n + m - 1)
z <<= 1;
a.resize(z), fft(a, false);
b.resize(z), fft(b, false);
for (int i = 0; i < z; i++)
a[i] *= b[i];
fft(a, true), a.resize(n + m - 1);
F iz = F(z).inv();
for (int i = 0; i < n + m - 1; i++)
a[i] *= iz;
return a;
}
template <class F, vector<F> (*conv)(vector<F>, vector<F>)>
class Polynomial
{
vector<F> p;
public:
Polynomial() : p() {}
Polynomial(vector<F> v) : p(v) {}
int deg() const { return (int)p.size() - 1; }
F &operator[](int idx) { return p[idx]; }
const F &operator[](int idx) const { return p[idx]; }
void set_degree(int deg)
{
assert(deg >= -1);
p.resize(deg + 1);
}
Polynomial operator+(const Polynomial &rhs) const
{
Polynomial ret = *this;
if (ret.deg() < rhs.deg())
ret.set_degree(rhs.deg());
for (int i = 0; i <= rhs.deg(); i++)
ret[i] += rhs[i];
return ret;
}
Polynomial &operator+=(const Polynomial &rhs)
{
if (deg() < rhs.deg())
set_degree(rhs.deg());
for (int i = 0; i <= rhs.deg(); i++)
p[i] += rhs[i];
return *this;
}
Polynomial operator*(const Polynomial &rhs) const { return Polynomial(conv(p, rhs.p)); }
Polynomial &operator*=(const Polynomial &rhs)
{
p = move(conv(p, rhs.p));
return *this;
}
Polynomial inv(int degree = -1) const
{
if (degree == -1)
degree = deg();
assert(deg() >= 0 && degree >= 0 && p[0] == F(1));
Polynomial a({F(1)});
for (int l = 1; l <= degree; l *= 2)
{
Polynomial p0 = vector(p.begin(), p.begin() + min(l, (int)p.size()));
Polynomial p1;
if ((int)p.size() >= l)
p1 = vector(p.begin() + l, p.begin() + min(2 * l, (int)p.size()));
Polynomial ap0 = a * p0;
Polynomial c = vector(ap0.p.begin() + l, ap0.p.end());
Polynomial b = a * p1;
b.set_degree(l - 1);
b += c;
b *= a;
b.set_degree(l - 1);
a.p.resize(2 * l);
for (int i = l; i < 2 * l; i++)
a.p[i] -= b[i - l];
}
a.set_degree(degree);
return a;
}
};
using Poly = Polynomial<Mint, convolution<Mint>>;
int solve(int K, vector<Mint> p)
{
int N = p.size();
Mint P = 0;
for (Mint x : p)
P += x;
for (Mint &x : p)
x = P - x;
function<pair<Poly, Poly>(int, int)> mul = [&](int s, int e)
{
if (s == e)
return make_pair(Poly({1}), Poly({1, -p[s]}));
auto [lu, ld] = mul(s, (s + e) / 2);
auto [ru, rd] = mul((s + e) / 2 + 1, e);
return make_pair(lu * rd + ru * ld, ld * rd);
};
auto [u, d] = mul(0, N - 1);
u *= d.inv(K);
int ans = 0;
for (int i = 1; i <= K; i++)
ans ^= (Mint(N) * P.pow(i) - u[i]).val();
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
int N, K;
cin >> N >> K;
vector<Mint> p(N);
for (Mint &x : p)
{
int v;
cin >> v;
x = v;
}
int ans = solve(K, p);
cout << "Case #" << tc << '\n'
<< ans << endl;
}
}
|
cs |