solved.ac Grand Arena #3

이 문제에서는 각 사이즈별로 구매할 티셔츠 묶음 수와, 구매할 펜 묶음 수를 구해야합니다. 우선, 간단한 펜 묶음의 수 부터 구해봅시다.

## 펜

펜 묶음을 몇 개 주문할지 구하기 위해서는, $N$개의 펜을 $P$개 단위로 묶어야합니다. 나눗셈을 사용하면, $N$을 $P$로 나눈 몫 $q$와 나머지 $r$을 구할 수 있습니다. 수식으로는 $N \div P = q \cdots r$으로 표현합니다. 이는 펜을 $P$개씩 묶으면 $q$개가 묶이고, $r$개가 남는다는 뜻입니다. 이 $q, r$이 펜을 주문해야하는 묶음 수와, 주문 후 펜을 한 자루씩 주문해야하는 수입니다.

## 티셔츠

### 풀이 1

이제 S사이즈의 티셔츠를 몇 묶음 구매해야 하는지 계산합시다.

$S$ 사이즈의 티셔츠를 $T$장 단위로 묶기 위해서 나눗셈을 씁니다. $S$를 $T$로 나눈 몫과 나머지를 각각 $q, r$라고 표현합시다. $(S \div T = q \cdots r)$

- $r = 0$인 경우에, 딱 $q$ 묶음을 주문하면 티셔츠를 남김 없이 나누어 줄 수 있습니다. 이 때의 답은 $q$입니다.

- $r > 0$인 경우에, $q$묶음을 주문하면 추가로 $r$개의 티셔츠를 주문해야 합니다. 티셔츠는 한 장씩 따로 주문할 수는 없으므로, 한 묶음을 더 주문해야하고 이 때의 답은 $q+1$입니다.

각각의 언어로는 다음과 같이 구현할 수 있습니다. 변수명은 각각 `S, T` 이고 결과는 `res` 입니다.

### C++

```C++
int q = S / T, r = S % T;
int res = q + (r > 0 ? 1 : 0);
```

### Python

```python
q, r = S // T, S % T
res = q + (1 if r > 0 else 0)
```

### Rust

```rust
let q = S / T;
let r = S % T;
let res = q + if r > 0 { 1 } else { 0 };
```

### 풀이 2

`if` 문을 사용하지 않고도 코드를 작성할 수 있습니다. 우선, 다음과 같은 기호를 쓰겠습니다.

- $\frac{a}{b}$: $a$를 $b$로 나눈 값입니다.
  - 이 글에서는 정수 나눗셈이 아니라, 실수 사이의 나눗셈을 사용합니다.
  - 예를 들어, $\frac{9}{5} = 1.8$입니다.
- $\left \lfloor x \right \rfloor, \left \lceil x \right \rceil$: 각각 $x$보다 작은 최대의 정수, $x$보다 큰 최소의 정수를 의미합니다.
  - 예를 들어, $\lfloor 3 \rfloor = 3, \lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$입니다.
  - 예를 들어, $\lceil 3 \rceil = 3, \lceil 3.14 \rceil = 4, \lceil 4 \rceil = 4$입니다.
  - $x$가 정수일 때는, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor$입니다.
  - $x$가 정수가 아닐 때는, $\left \lceil x \right \rceil = \left \lfloor x \right \rfloor + 1$입니다. 

우리가 정수 나눗셈에서 구하는 $S$를 $T$로 나눈 몫은, $\left\lfloor \frac{S}{T} \right \rfloor$입니다. $S$를 $T$로 나눈 후에, $T$개씩 묶지 못하는 소수 부분을 없애줍니다. 하지만, 이 문제에서 구해야 할 것은 $\left \lceil \frac{S}{T} \right \rceil$입니다. 소수부분이 남더라도, 그 부분을 $1$개의 묶음으로 생각해줘야합니다. 

이제, 다음을 증명합시다. $0$ 이상인 정수 $S$와, $1$ 이상인 정수 $T$에 대해, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac{S+T-1}{T} \right\rfloor$입니다.

- $S$가 $T$의 배수인 경우에는, $\left\lceil \frac{S}{T} \right\rceil = \frac{S}{T}$ 이고, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S}{T} + \frac{T-1}{T} \right\rfloor$입니다. $\frac{S}{T}$는 정수이고, $\frac{T-1}{T}$는 $1$보다 작은 부분이기 때문에, 무시되어서, $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \frac{S}{T}$입니다.

- $S$가 $T$의 배수가 아닌 경우에는, $\frac{S}{T}$가 정수가 아니기 때문에, $\left\lceil \frac{S}{T} \right\rceil = \left\lfloor \frac S T \right\rfloor + 1$입니다. 또한, $S$에서 나머지가 $1$개 이상 남기 때문에, $S-1$을 $T$로 나누어도 몫이 동일합니다. 즉, $\left \lfloor \frac{S-1}{T} \right \rfloor = \left \lfloor \frac{S}{T} \right\rfloor$입니다. $\left\lfloor \frac{S+T-1}{T} \right\rfloor = \left\lfloor \frac{S-1}{T} + \frac{T}{T} \right\rfloor = \left\lfloor \frac{S}{T} \right \rfloor + 1 = \left\lceil \frac S T \right \rceil$입니다.

이를 이용하면 좀 더 간단하게 코드를 작성할 수 있습니다. 아래는 각 언어로 작성된 모범답안입니다.

### 코드 (C++)

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> sizes(6);
    for (int &size : sizes)
        cin >> size;
    int T, P;
    cin >> T >> P;
    int sumv = 0;
    for (int size : sizes)
        sumv += (size + T - 1) / T;
    cout << sumv << endl;
    cout << N / P << " " << N % P << endl;
}
```

### 코드 (Python)

```python
def main():
    N = int(input())
    sizes = list(map(int, input().split()))
    T, P = map(int, input().split())
    print(sum((size + T - 1) // T for size in sizes))
    print(N // P, N % P)


if __name__ == '__main__':
    main()
```

### 코드 (Rust)

```rust
use std::io::*;

fn main() {
    let n = read_vec()[0];
    let sizes = read_vec();
    let (t, p) = {
        let v = read_vec();
        (v[0], v[1])
    };

    println!("{}", sizes.iter().map(|x| (x + t - 1) / t).sum::<u32>());
    println!("{} {}", n / p, n % p);
}

fn read_vec() -> Vec<u32> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```


현재 수도꼭지에서 나오는 물의 양을 $A_i$, $i$번째 수도꼭지가 열려있으면 $B_i = 1$, 잠겨있으면 $B_i = 0$이라고 표현합시다.  이 때 각 쿼리와 구해야 할 것을 다음과 같습니다.

- 쿼리 $1, i, x$는 $A_i := x$로 바꾼다는 의미입니다.
- 쿼리 $2, i$는 $B_i$가 $0$이면 $1$로, $1$이면 $0$으로 바꾼다는 의미입니다.

- 각 수도꼭지가 물탱크에 내보내는 물의 양은 $B_iA_i$로 표현될 수 있습니다. 즉, 수도꼭지가 열려있으면 $A_i$, 잠겨있으면 $B_i$입니다. 문제에서는 $B_1A_1 + B_2A_2 + \cdots + B_NA_N$을 구해야합니다.

$i$번째 수도꼭지를 조작하는 쿼리는 $B_iA_i$만 바꾸고, 나머지 값들을 바꾸지 않는다는 점을 이용합시다. 이전 쿼리의 답을 $S$라고 합니다.

- $i$번째 수도꼭지를 제외한 곳에서 나오는 물의 양은, 전체에서 $B_iA_i$를 뺀 $T = S-B_iA_i$로 계산할 수 있습니다. 이 값은 쿼리 전후에서 바뀌지 않습니다.
- 쿼리를 처리한 후, $B_iA_i$가 $B'_i A'_i$로 바뀝니다.
- 전체 수도꼭지에서 나오는 물의 양을 구하기 위해, $i$번째 수도꼭지에서 나오는 물 양을 더합니다. 즉, 이번 쿼리의 답은 $S' = T + B'_iA'_i$가 됩니다.

### 코드 (C++)

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    vector<bool> B(N, true);
    int64_t S = 0;
    for (int &a : A)
        cin >> a, S += a;
    cout << S << '\n';
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++)
    {
        int t, i;
        cin >> t >> i;
        i--;

        if (B[i])
            S -= A[i];

        if (t == 1)
        {
            int x;
            cin >> x;
            A[i] = x;
        }
        if (t == 2)
            B[i] = !B[i];

        if (B[i])
            S += A[i];
        cout << S << '\n';
    }
}
```

### 코드 (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [True]*N
    S = sum(A)
    print(S)

    Q = int(input())
    for _ in range(Q):
        qry = list(map(int, input().split()))
        (t, i) = (qry[0], qry[1]-1)

        if B[i]:
            S -= A[i]

        if t == 1:
            A[i] = qry[2]
        if t == 2:
            B[i] = not B[i]

        if B[i]:
            S += A[i]
        print(S)


if __name__ == '__main__':
    main()
```

### 코드 (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

fn main() {
    let n = read_vec()[0];
    let mut a = read_vec();
    let mut b = vec![true; n];
    let mut ans = a.iter().sum::<u64>();
    println!("{}", ans);
    let q = read_vec()[0];
    for _ in 0..q {
        let q = read_vec();
        let t = q[0];
        let i = (q[1] - 1) as usize;
        if b[i] {
            ans -= a[i];
        }
        match t {
            1 => a[i] = q[2],
            2 => b[i] = !b[i],
            _ => panic!(),
        };
        if b[i] {
            ans += a[i];
        }
        println!("{}", ans);
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| { cell.borrow_mut().read_line(&mut s).unwrap(); });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```

## 풀이 1

사용할 과일을 두 종류 고릅니다. 그 이후, 두 종류의 과일로 이루어진 가장 긴 연속된 부분수열을 구합니다. 가장 긴 연속된 부분수열을 구하는 방법은 언어에서 지원하는 `split` 함수 등을 사용하거나, `cnt`변수를 관리하며 앞쪽부터 훑어보는 방법이 있습니다. 원하는 종류의 과일일 때는 `cnt`를 $1$ 더하고, 원하지 않는 종류일 경우에는 `cnt`를 $0$으로 초기화 해주면서, `cnt`의 최댓값을 구하면 됩니다.

과일의 종류 $d = 9$라고 하면, 과일을 두 개 고르는 방법이 $\frac{d(d-1)}{2} = 36$가지 있고, 이 각각에 대해서 $\mathcal{O}(N)$ 시간이 듭니다. 총 시간복잡도는 $\mathcal{O}(d^2N)$입니다.

### 코드 (C++20)

```cpp
#include <iostream>
#include <ranges>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j < i; j++)
        {
            auto v = S | views::transform([&](int x)
                                          { return x == i || x == j; });
            for (auto w : views::split(v, false))
                ans = max(ans, (int)distance(w.begin(), w.end()));
        }
    cout << ans << endl;
}
```

### 코드 (Python)

```python
import re


def main():
    input()
    s=''.join(input().split())
    ans = 0
    for i in range(1, 10):
        for j in range(1, i):
            ans = max(ans, max(map(len, re.split(f'[^{i}{j}]', s))))
    print(ans)


if __name__ == "__main__":
    main()
```

### 코드 (Rust)

```rust
use std::io::*;
use std::iter::FromIterator;

fn main() {
    stdin().read_line(&mut String::new()).unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let s = String::from_iter(s.chars().filter(|&x| !x.is_ascii_whitespace()));
    let mut ans = 0;
    for i in '1'..='9' {
        for j in '1'..i {
            ans = ans.max(
                s.split(|x| x != i && x != j)
                    .map(|x| x.len())
                    .max()
                    .unwrap_or_default(),
            );
        }
    }
    println!("{}", ans);
}
```

## 풀이 2

$S_l$로 시작해서, 두 종류 이하의 과일이 등장하는 최대 길이 구간의 오른쪽 끝 점을 $R_l$이라고 합시다. 즉, $S_l, S_{l+1}, \cdots, S_{R_l}$에서 두 종류 이하의 과일이 등장합니다. $S_l$을 제외한 $S_{l+1}, \cdots, S_{R_l}$도 두 종류 이하의 과일이 등장하기 때문에, $R_{l+1}$은 $R_l$보다 항상 크거나 같습니다. 즉, $l$에 따라 $R_l$은 증가하는 형태를 보이게 됩니다.

$R_{l-1}$이 계산되었다고 할 때, $R_l$이 $R_l$보다 크다는 것을 알 기 때문에, $r = R_{l-1}$로 시작해서 $r$을 $1$씩 증가시켜보면서 $S_{l}, \cdots, S_r$에서 두 종류 이하의 과일이 등장하는 최대 $r$을 naive하게 반복문으로 구현해도 됩니다. 반복문을 돌리면서 $r$은 총 $N$ 증가하기 때문에, 확인하는 총 횟수는 $O(N)$번이 넘지 않습니다.

이제 $S_l, \cdots, S_r$에 있는 과일 종류를 빠르게 구하면 됩니다. 이는 길이 $10$의 `cnt` 배열을 관리해, 각 과일이 현재 보고 있는 $S_l, \cdots, S_r$ 구간에 몇 개 있는지를 저장하고, 동시에 $1$개 이상 존재하는 과일이 몇 종류인지를 저장하면 $O(1)$에 문제를 풀 수 있습니다. 총 시간복잡도는 $O(N)$입니다.

아래 코드에서 변수 `r` 은 $R_l + 1$을 관리하도록 구현되어있습니다.

### 코드 (C++)

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0, r = 0, non_zero = 0;
    vector<int> cnt(10);
    for (int l = 0; l < N; l++)
    {
        while (r < N)
        {
            int nxt_non_zero = non_zero + (cnt[S[r]] == 0 ? 1 : 0);
            if (nxt_non_zero <= 2)
            {
                cnt[S[r]]++;
                r++;
                non_zero = nxt_non_zero;
            }
            else
                break;
        }
        ans = max(ans, r - l);
        cnt[S[l]]--;
        if (cnt[S[l]] == 0)
            non_zero--;
    }
    cout << ans << endl;
}
```

### 코드 (Python)

```python
def main():
    N = int(input())
    S = map(int, input().split())

    ans = r = non_zero = 0
    cnt = [0]*10

    for l in range(N):
        while r < N:
            nxt_non_zero = non_zero + (1 if cnt[S[r]] == 0 else 0)
            if nxt_non_zero <= 2:
                cnt[S[r]] += 1
                r += 1
                non_zero = nxt_non_zero
            else:
                break
        ans = max(ans, r - l)
        cnt[S[l]] -= 1
        if cnt[S[l]] == 0:
            non_zero -= 1

    print(ans)


if __name__ == "__main__":
    main()
```

### 코드 (Rust)

```rust
use std::io::*;

fn main() {
    let n = read_vec()[0];
    let s = read_vec();

    let mut ans = 0;
    let mut r = 0;
    let mut non_zero = 0;
    let mut cnt = [0; 10];

    for l in 0..n {
        while r < n {
            let nxt_non_zero = non_zero + if cnt[s[r] as usize] == 0 { 1 } else { 0 };
            if nxt_non_zero <= 2 {
                cnt[s[r]] += 1;
                r += 1;
                non_zero = nxt_non_zero;
            } else {
                break;
            }
        }
        ans = ans.max(r - l);
        cnt[s[l]] -= 1;
        if cnt[s[l]] == 0 {
            non_zero -= 1;
        }
    }

    println!("{}", ans);
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```


$A$와 $B$의 최대 공통 부분 수열에 등장할 수 있는 가장 큰 수는, $A$와 $B$ 모두에게 등장하는 수 중 가장 큰 수 $x$ 입니다. 사전 순 비교의 정의에 따라서, 앞에 등장하는 수가 가장 큰 수이면 좋기 때문에, 최대 공통 부분 수열의 가장 처음 원소로 $x$가 오게 됩니다.

해당하는 $x$가 여러번 등장할 경우, 그리디하게 $A$와 $B$의 가장 앞쪽에 있는 $x$를 사용하는 것이 좋습니다. 가장 앞쪽에 있는 $x$를 사용해야, 뒤에 더 긴 부분 수열을 남기게 되고, 가능한 최대 공통 부분 수열의 종류를 늘리기 때문입니다.

즉, 가장 큰 수부터 보면서, $A$와 $B$에 모두 등장하는 원소의 처음으로 등장하는 위치를 찾아, 그 이후에 오는 수열에 대해서 동일한 문제를 풀어주면 됩니다. 시간 복잡도는 $\mathcal{O}((N+M + \max A_i + \max B_i)^2)$ 정도입니다.

참고로, 구현을 우선순위 큐 등을 이용하여 최적화해서 $\mathcal{O}((N+M) \log (N+M))$ 시간복잡도에도 해결할 수 있습니다.

### 코드 (C++20)

```cpp
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    int M;
    cin >> M;
    vector<int> B(M);
    for (int &b : B)
        cin >> b;

    int mx = max(ranges::max(A), ranges::max(B));
    auto it_a = A.begin(), it_b = B.begin();
    vector<int> ans;

    for (int i = mx; i >= 1; --i)
    {
        while (true)
        {
            auto nxt_a = find(it_a, A.end(), i), nxt_b = find(it_b, B.end(), i);
            if (nxt_a == A.end() || nxt_b == B.end())
                break;

            ans.push_back(i);
            it_a = next(nxt_a), it_b = next(nxt_b);
        }
    }

    cout << ans.size() << endl;
    for (int v : ans)
        cout << v << " ";
    cout << endl;
    return 0;
}
```

### 코드 (Python)

```python
def main():
    input()
    a = list(map(int, input().split()))
    input()
    b = list(map(int, input().split()))

    mx = max(max(a), max(b))
    ans = []
    for i in range(mx, 0, -1):
        while True:
            if i not in a or i not in b:
                break

            ans.append(i)
            a = a[a.index(i)+1:]
            b = b[b.index(i)+1:]

    print(len(ans))
    print(*ans, sep=' ')


if __name__ == "__main__":
    main()
```

### 코드 (Rust)

```rust
use std::io::*;

fn main() {
    read_vec();
    let a = read_vec();
    read_vec();
    let b = read_vec();

    let mx = *a.iter().chain(b.iter()).max().unwrap();
    let mut a = &a[..];
    let mut b = &b[..];
    let mut ans = Vec::new();
    for i in (1..=mx).rev() {
        loop {
            let ai = a.iter().position(|&x| x == i);
            let bi = b.iter().position(|&x| x == i);
            if ai == None || bi == None {
                break;
            }
            ans.push(i);
            a = &a[ai.unwrap() + 1..];
            b = &b[bi.unwrap() + 1..];
        }
    }
    println!("{}", ans.len());
    for i in ans {
        print!("{} ", i);
    }
    println!();
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .into_iter()
        .map(|x| x.parse().unwrap())
        .collect()
}
```


## 풀이

집합의 크기를 구한다는 것은 어떤 집합의 원소를 하나씩 세는 것으로 생각할 수 있습니다. 즉, 주어진 식은 다음과 같이 변형할 수 있습니다.
$$
a_{k} = \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}
$$

이때 $\mathcal{S}$는 집합에 들어있을 수 있는 가능한 모든 수들의 집합, 즉 $\mathcal{S} = \bigcup_{i} S_{i}$이고, $[a \in A]_{\mathbf{1}}$은 $a$가 집합 $A$에 포함되어 있으면 $1$, 아니면 $0$의 값을 갖는 수식입니다.

이제 합의 순서를 바꾸어 이 식을 **각 $s$에 대해** 봅시다. 정해진 $s$에 대해, 집합 중 $k$개를 고른 이후 교집합한 것이 $s$를 포함하려면 고른 $k$개의 집합 모두에 $s$가 모두 포함되어 있어야 합니다. $S_{i}$가 $s$를 포함하는 횟수를 $c_{s}$라 한다면, $s$를 포함하는 $c_{s}$개의 집합 중에서 $k$개를 골라야 고른 집합 모두가 $s$를 포함합니다. 이러한 경우는 정확히 $\binom{c_{s}}{k}$번 있습니다.

이상의 논의를 정리하면 다음과 같습니다.

$$
\begin{aligned}a_{k} &= \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}} \\&= \sum_{s \in \mathcal{S}} \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}\\&= \sum_{s \in \mathcal{S}}\binom{c_{s}}{k}.\end{aligned}
$$

이항 계수를 구하는 시간은 $\mathcal{O}(1)$로 줄일 수 있습니다. $\binom{a}{b} = \frac{a!}{b!(a-b)!}$에서 $a$, $b$가 $10^{6}$을 넘을 수 없으므로, 모듈로 $p = 998\,244\,353$으로 팩토리얼과 팩토리얼의 역수 $0!$, $1!$, $2!$, $\cdots$, $10^{6}!$, $(0!)^{-1}$, $(1!)^{-1}$, $(2!)^{-1}$, $\cdots$, $(10^{6}!)^{-1}$를 모두 전처리하면, 모듈로 $p$에서의 곱셈 두 번으로 이항 계수를 빠르게 구할 수 있습니다.

그러나 지금은 $|S|$가 $N$을 넘지 않고 $k = 1, \cdots, N$에 대해서 모든 값을 빠르게 구해야 하니, 이대로 계산한다면 $\mathcal{O}(N^{2})$로 시간 초과를 받게 됩니다.

시간을 더 줄이기 위해 $c_{s} < k$이면 $\binom{c_{s}}{k} = 0$이라는 점에 주목합니다. 중요한 것은 $s$의 등장 횟수뿐이니, $a_{k}$를 $k = 1$부터 차례로 늘려 가면서 구하되, $c_{s}$를 미리 처리해 두고 $c_{s} < k$가 되는 순간 $s$를 더 생각하지 않는 방식을 사용하면 모든 $a_{k}$를 $\sum_{s \in \mathcal{S}} c_{s} + \mathcal{O}(N)$에 비례하는 시간에 계산할 수 있습니다.

그런데 위 식에서 $\sum_{s \in \mathcal{S}} c_{s} = a_{1}$이고, $a_{1}$은 하나씩 골라 크기를 모두 구해 더한 값이므로 $\sum_{i} \left|S_{i}\right|$인데, 문제에서 이 값은 $10^{6}$을 넘지 않는다고 주어져 있습니다! 따라서 이 최적화를 시행하면 (정렬 시간을 제외하고) $\mathcal{O}(N)$ 시간에 통과하는 코드를 짤 수 있습니다.

### 코드 (C++20)

```cpp
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998'244'353;
int ipow(int a, int b)
{
    if (b == 0)
        return 1;
    if (b % 2 == 1)
        return 1LL * a * ipow(a, b - 1) % MOD;
    long long r = ipow(a, b / 2);
    return r * r % MOD;
}
int modinv(int v) { return ipow(v, MOD - 2); }
struct Comb
{
    vector<int> fact, rfact;
    Comb(int sz) : fact(sz + 1), rfact(sz + 1)
    {
        fact[0] = 1;
        for (int i = 1; i <= sz; i++)
            fact[i] = 1LL * i * fact[i - 1] % MOD;
        rfact[sz] = modinv(fact[sz]);
        for (int i = sz - 1; i >= 0; --i)
            rfact[i] = 1LL * (i + 1) * rfact[i + 1] % MOD;
        assert(rfact[0] == 1);
    }
    int C(int n, int k)
    {
        return 1LL * fact[n] * rfact[k] % MOD * rfact[n - k] % MOD;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> arr, coeff(N + 1);
    for (int i = 0; i < N; i++)
    {
        int t;
        cin >> t;
        while (t--)
        {
            int x;
            cin >> x;
            arr.push_back(x);
        }
    }
    ranges::sort(arr);
    int last = -1, cnt = 0;
    for (int x : arr)
    {
        if (last != x)
        {
            if (cnt > 0)
                ++coeff[cnt];
            last = x, cnt = 0;
        }
        ++cnt;
    }
    ++coeff[cnt];

    Comb comb(1'000'000);

    vector<int> result(N + 1);
    for (int i = 0; i <= N; i++)
        if (coeff[i])
            for (int j = 0; j <= i; j++)
                result[j] = (result[j] + 1LL * coeff[i] * comb.C(i, j)) % MOD;

    for (int i = 1; i <= N; i++)
        cout << result[i] << '\n';
}
```

### 코드 (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


MOD = 998_244_353


class Comb:
    def __init__(self, sz):
        self.fact = [1] * (sz + 1)
        self.rfact = [1] * (sz + 1)
        for i in range(1, sz + 1):
            self.fact[i] = (i * self.fact[i - 1]) % MOD
        self.rfact[sz] = pow(self.fact[sz], -1, MOD)
        for i in range(sz - 1, -1, -1):
            self.rfact[i] = ((i + 1) * self.rfact[i + 1]) % MOD
        assert self.rfact[0] == 1

    def C(self, n, k):
        return (self.fact[n] * self.rfact[k] % MOD * self.rfact[n - k]) % MOD


def main():
    N = int(input())
    arr = []
    coeff = [0] * (N + 1)
    for _ in range(N):
        arr.extend(list(map(int, input().split()))[1:])
    arr.sort()

    cnt, last = 0, -1
    for x in arr:
        if last != x:
            if cnt > 0:
                coeff[cnt] += 1
            last, cnt = x, 0
        cnt += 1
    coeff[cnt] += 1

    comb = Comb(1_000_000)

    result = [0] * (N + 1)
    for i in range(N + 1):
        if coeff[i]:
            for j in range(i + 1):
                result[j] = (result[j] + coeff[i] * comb.C(i, j)) % MOD

    for i in range(1, N + 1):
        print(result[i])


if __name__ == "__main__":
    main()
```

### 코드 (Rust)

```rust
use std::{cell::*, collections::HashMap, fmt::Debug, io::*, str::*};

const MOD: u64 = 998_244_353;
fn ipow(a: u32, b: u32) -> u32 {
    (match b {
        0 => 1,
        v if v % 2 == 0 => {
            let c: u64 = ipow(a, v / 2) as u64;
            c * c % MOD
        }
        v if v % 2 == 1 => a as u64 * ipow(a, b - 1) as u64 % MOD,
        _ => panic!(),
    }) as u32
}
fn modinv(a: u32) -> u32 {
    ipow(a, MOD as u32 - 2)
}
struct Comb {
    fact: Vec<u32>,
    rfact: Vec<u32>,
}
impl Comb {
    fn new(sz: usize) -> Comb {
        let mut fact = vec![1; sz + 1];
        let mut rfact = vec![1; sz + 1];
        fact[0] = 1;
        for i in 1..=sz {
            fact[i] = ((i as u64) * (fact[i - 1] as u64) % MOD) as u32;
        }
        rfact[sz] = modinv(fact[sz]);
        for i in (0..sz).rev() {
            rfact[i] = (((i + 1) as u64) * (rfact[i + 1] as u64) % MOD) as u32;
        }
        assert_eq!(rfact[0], 1);
        Comb { fact, rfact }
    }
    fn c(&self, n: usize, k: usize) -> u32 {
        ((self.fact[n] as u64) * (self.rfact[k] as u64) % MOD * (self.rfact[n - k] as u64) % MOD)
            as u32
    }
}

fn main() {
    let n = read_vec()[0];
    let mut hm = HashMap::new();
    for _ in 0..n {
        for v in read_vec::<u32>().into_iter().skip(1) {
            hm.insert(v, *hm.get(&v).unwrap_or(&0) + 1);
        }
    }
    let comb = Comb::new(1_000_000);
    let mut ans = vec![0; n + 1];
    for v in hm.values().cloned() {
        for i in 1..=v {
            ans[i] = (ans[i] + comb.c(v, i)) % (MOD as u32);
        }
    }

    for i in ans.into_iter().skip(1) {
        println!("{} ", i);
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```

## 풀이

그래프 $G$의 MST의 비용을 $\mathrm{mst}(G)$라고 표기합시다.

임의의 그래프 $G$에서 간선 하나의 가중치를 $1$ 증가시키면, $\mathrm{mst}(G)$는 최대 $1$만큼 증가합니다. 가중치를 증가시킨 그래프 $G'$에서 $G$의 MST에 해당하는 트리의 비용은 최대 $1$만큼 커지는데, $\mathrm{mst}(G')$는 그보다 작거나 같기 때문입니다.

이제 다음과 같은 과정을 생각합시다. $i$번 간선의 가중치를 $l_i$에서 시작해서 $r_i$가 될 때까지 $1$씩 증가시킵니다. 해당 과정을 $1$번 간선부터 $M$번 간선까지 전부 순서대로 진행합니다.

지금까지 증가시킨 가중치의 총량이 $t$일 때의 그래프를 $G_t$라고 하고, $r_i - l_i$의 합을 $X$라고 합시다. 위와 같은 과정이 진행되는 동안 $\mathrm{mst}(G_t)$는 $\mathrm{mst}(G_0)$ 이상 $\mathrm{mst}(G_X)$ 이하의 모든 정수를 지나면서 단조 증가합니다.

따라서, $\mathrm{mst}(G_0) \le K \le \mathrm{mst}(G_X)$가 성립한다면 $t$에 대한 이분 탐색을 진행하여 $\mathrm{mst}(G_t) = K$가 되는 순간을 찾을 수 있습니다. $G_t$는 $\mathcal{O}(M)$ 시간에 구성할 수 있으며, MST의 비용은 $\mathcal{O}(M\log M)$ 시간에 구할 수 있으므로, 총 $\mathcal{O}(M \log M \log X)$ 시간에 문제를 해결할 수 있습니다.

### 코드 (C++)

```cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct DisjointSet
{
    vector<int> par;

    DisjointSet(int N) : par(N)
    {
        iota(par.begin(), par.end(), 0);
    }

    int find(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = find(par[x]);
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return false;
        par[y] = x;
        return true;
    }
};

struct Edge
{
    int u, v;
    long long c;
    bool operator<(const Edge &E) const { return c < E.c; }
};

long long mst(int N, const vector<tuple<int, int, long long, long long>> &G, long long t)
{
    // construct G_t
    vector<Edge> E;
    for (auto [u, v, l, r] : G)
    {
        long long c = min(t, r - l);
        E.push_back({u, v, l + c});
        t -= c;
    }
    sort(E.begin(), E.end());

    // find MST
    DisjointSet dsu(N + 1);
    long long sum = 0;
    for (auto [x, y, c] : E)
        if (dsu.merge(x, y))
            sum += c;
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<tuple<int, int, long long, long long>> G(M);
    long long X = 0;
    for (auto &[u, v, l, r] : G)
    {
        cin >> u >> v >> l >> r;
        X += r - l;
    }

    // binary search
    long long s = -1, e = X;
    while (s + 1 < e)
    {
        long long m = (s + e) / 2;
        if (mst(N, G, m) >= K)
            e = m;
        else
            s = m;
    }

    // print answer
    if (mst(N, G, e) == K)
    {
        cout << "YES\n";
        for (auto &[u, v, l, r] : G)
        {
            int c = min(e, r - l);
            cout << min(l + c, r) << '\n';
            e -= c;
        }
    }
    else
    {
        cout << "NO\n";
    }

    return 0;
}
```

### 코드 (Python)

```python
import sys

def input():
    return sys.stdin.readline().rstrip()

class DisjointSet:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        self.par[y] = x
        return True

def mst(N, G, t):
    # construct G_t
    E = []
    for u, v, l, r in G:
        c = min(t, r - l)
        E.append((u, v, l + c))
        t -= c
    E.sort(key=lambda x: x[2])

    # find MST
    dsu = DisjointSet(N)
    sum = 0
    for x, y, c in E:
        if dsu.merge(x, y):
            sum += c
    return sum

def main():
    N, M, K = [int(x) for x in input().split()]
    G = []
    for i in range(M):
        u, v, l, r = [int(x) for x in input().split()]
        G.append((u, v, l, r))

    X = sum(r - l for u, v, l, r in G)

    # binary search
    s, e = -1, X
    while s + 1 < e:
        m = (s + e) // 2
        if mst(N, G, m) >= K:
            e = m
        else:
            s = m

    # print answer
    if mst(N, G, e) == K:
        print("YES")
        for u, v, l, r in G:
            c = min(e, r - l)
            print(min(l + c, r))
            e -= c
    else:
        print("NO")

if __name__ == "__main__":
    main()
```

### 코드 (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

struct DisjointSet {
    par: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> DisjointSet {
        DisjointSet {
            par: (0..n).collect(),
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            let parent = self.find(self.par[x]);
            self.par[x] = parent;
            parent
        }
    }

    fn merge(&mut self, x: usize, y: usize) -> bool {
        let x = self.find(x);
        let y = self.find(y);
        if x == y {
            false
        } else {
            self.par[y] = x;
            true
        }
    }
}

struct Edge {
    u: usize,
    v: usize,
    c: i64,
}

fn mst(n: usize, g: &Vec<(usize, usize, i64, i64)>, mut t: i64) -> i64 {
    // construct G_t
    let mut e = Vec::new();
    for &(u, v, l, r) in g {
        let c = t.min(r - l);
        e.push(Edge { u, v, c: l + c });
        t -= c;
    }
    e.sort_by_key(|k| k.c);

    // find MST
    let mut dsu = DisjointSet::new(n + 1);
    let mut sum = 0;
    for edge in e {
        if dsu.merge(edge.u, edge.v) {
            sum += edge.c;
        }
    }
    sum
}

fn main() {
    let (n, m, k) = {
        let v = read_vec();
        (v[0], v[1], v[2] as i64)
    };

    let mut g = vec![(0, 0, 0, 0); m];
    for (u, v, l, r) in &mut g {
        let edge = read_vec();
        *u = edge[0];
        *v = edge[1];
        *l = edge[2] as i64;
        *r = edge[3] as i64;
    }
    let x = g.iter().map(|&(_u, _v, l, r)| r - l).sum();

    // binary search
    let mut s = -1;
    let mut e = x;
    while s + 1 < e {
        let m = (s + e) / 2;
        if mst(n, &g, m) >= k {
            e = m;
        } else {
            s = m;
        }
    }

    // print answer
    if mst(n, &g, e) == k {
        println!("YES");
        let mut e = e;
        for (_u, _v, l, r) in g {
            let c = e.min(r - l);
            println!("{}", r.min(l + c));
            e -= c;
        }
    } else {
        println!("NO");
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```


## 풀이

문제에서 방문하는 건물 순서를 역순으로 뒤집어서 생각합니다. 이러면 $u \rightarrow v$를 방문해서 $v$를 $p$번 색으로 덧칠하는 연산이, $v \rightarrow u$번 순으로 방문할 때, $v$를 $p$번 색으로 칠하는 연산으로 바뀝니다. 단, 이미 $v$에 색이 칠해져 있다면 칠하지 않습니다.

즉, 문제는 건물들을 모두 방문하는 방문 순서를 찾는데, 처음 $v$라는 정점에 방문 했을 경우, $r_v$번 색의 간선만 이용할 수 있고, 두 번째부터는 어떠한 색이든 이용할 수 있습니다.

이를 이용해서, 각 건물을 두 번 방문하도록 DFS를 돌립니다.

- 처음 $v$번 건물에 도착했을 경우, 각 건물에서 $r_v$번 색의 간선 하나를 이용해서 다른 건물로 이동합니다.
- 두 번째로 $v$번 건물에 도착했을 경우, 인접한 건물 중, 두 번 미만으로 방문한 건물들을 방문합니다.

마지막으로, 출력할 때 답을 역순으로 출력합니다.

인접한 $r_v$번 색의 간선이 존재하지 않거나, 모든 건물이 서로 연결되어 있지 않다면 답은 `NO`이고, 아닌 경우 위 알고리즘이 올바르게 동작하기 때문에 답은 `YES`입니다. 각 건물은 (dfs과정에서 돌아오는 때를 제외하고) 두 번씩만 방문하기 때문에, 방문 총 횟수가 $4N$번 이하입니다.

### 코드 (C++)

```cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> R(N);
    for (int &r : R)
        cin >> r;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    vector<int> vis(N), history;
    function<bool(int)> dfs = [&](int u)
    {
        ++vis[u];
        history.push_back(u);
        if (vis[u] == 1)
        {
            // only can jump to matching color
            for (auto [v, c] : G[u])
                if (R[u] == c)
                {
                    if (vis[v] != 2)
                    {
                        bool ret = dfs(v);
                        history.push_back(u);
                        return ret;
                    }
                    else
                    {
                        history.push_back(v);
                        return dfs(u);
                    }
                }
            return false;
        }
        else
        {
            // visit everywhere
            for (auto [v, c] : G[u])
                if (vis[v] != 2)
                {
                    if (!dfs(v))
                        return false;
                    history.push_back(u);
                }
            return true;
        }
    };

    bool res = dfs(0);
    if (!res || ranges::any_of(vis, [](int x)
                               { return x != 2; }))
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        cout << history.size() << '\n';
        ranges::reverse(history);
        for (int h : history)
            cout << h + 1 << ' ';
        cout << '\n';
    }

    return 0;
}
```

### 코드 (Python)

```python
import sys
sys.setrecursionlimit(1_000_000)


def input(): return sys.stdin.readline().rstrip()


def main():

    n, m, _ = map(int, input().split())
    g = [[] for _ in range(n)]
    r = list(map(int, input().split()))
    for _ in range(m):
        u, v, c = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((v, c))
        g[v].append((u, c))

    vis = [0] * n
    history = []

    def dfs(u):
        vis[u] += 1
        history.append(u)
        if vis[u] == 1:
            # only can jump to matching color
            for v, c in g[u]:
                if r[u] == c:
                    if vis[v] != 2:
                        ret = dfs(v)
                        history.append(u)
                        return ret
                    else:
                        # visit v, and return u.
                        history.append(v)
                        return dfs(u)
            return False
        else:
            # visit everywhere
            for v, _ in g[u]:
                if vis[v] != 2:
                    if not dfs(v):
                        return False
                    history.append(u)
            return True

    res = dfs(0)
    if not res or any(x != 2 for x in vis):
        print('NO')
    else:
        print('YES')
        print(len(history))
        print(' '.join(map(lambda x: str(x+1), history[::-1])))


if __name__ == '__main__':
    main()
```

### 코드 (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

fn main() {
    let (n, m, _) = {
        let v = read_vec();
        (v[0], v[1], v[2])
    };
    let mut g = vec![Vec::new(); n];
    let r = read_vec();
    for _ in 0..m {
        let (u, v, c) = {
            let v = read_vec::<usize>();
            (v[0] - 1, v[1] - 1, v[2])
        };
        g[u].push((v, c));
        g[v].push((u, c));
    }

    struct Dfs<'a> {
        g: &'a Vec<Vec<(usize, usize)>>,
        r: &'a Vec<usize>,
        vis: Vec<usize>,
        history: Vec<usize>,
    }
    impl Dfs<'_> {
        fn dfs(&mut self, u: usize) -> bool {
            self.vis[u] += 1;
            self.history.push(u);
            match self.vis[u] {
                1 => {
                    // only can jump to matching color
                    for &(v, c) in &self.g[u] {
                        if self.r[u] == c {
                            if self.vis[v] != 2 {
                                let ret = self.dfs(v);
                                self.history.push(u);
                                return ret;
                            } else {
                                // visit v, and return u.
                                self.history.push(v);
                                return self.dfs(u);
                            }
                        }
                    }
                    false
                }
                2 => {
                    // visit everywhere
                    for &(v, _) in &self.g[u] {
                        if self.vis[v] != 2 {
                            if !self.dfs(v) {
                                return false;
                            }
                            self.history.push(u);
                        }
                    }
                    true
                }
                _ => panic!(),
            }
        }
    }

    let mut dfs = Dfs {
        g: &g,
        r: &r,
        vis: vec![0; n],
        history: Vec::new(),
    };
    let res = dfs.dfs(0);
    if !res || dfs.vis.iter().any(|&x| x != 2) {
        println!("NO");
    } else {
        println!("YES");
        println!("{}", dfs.history.len());
        for i in dfs.history.into_iter().rev() {
            print!("{} ", i + 1);
        }
        println!();
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        STDOUT.with(|cell| write!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```
