Educational Codeforces Round 113 (Rated for Div. 2)-C. Jury Meeting

문제 설명

다가오는 대회의 심사위원 회의를 하기위해 $n$명의 사람이 모였습니다. $i$번째 심사위원은 서류 $a_i$개를 처리해야하고, 서로 공유해서 처리하고 싶어합니다.

먼저 심사위원은 각자의 작업이 얼마나 남아있는지 설명하는 방식을 순서에 맞게 하자고 결정을 했습니다. $p$를 $1$부터 $n$까지 숫자로 이루어진 순열로 정합시다. ($1$부터 $n$까지 숫자가 한번씩 나오는 크기가 $n$인 배열이 $p$입니다.)

이후 토의는 다음과 같은 순서로 이루어집니다.

• 만약 심사위원 $p_1$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다.
• 만약 심사위원 $p_2$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다.
• ...
• 만약 심사위원 $p_n$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다.
• 만약 여전히 다른 심사위원이 해야할 작업이 남아있으면 처음부터 위의 작업을 반복합니다. 그렇지 않으면 토의를 마칩니다.

만약 심사위원 아무도 자신이 남아있는 작업의 개수를 연속해서 말하지 않는다면 순열 $p$는 좋은 순열이라고 합니다.

우리의 목표는 좋은 순열의 수를 구하는 것입니다. 정답은 매우 큰 수이기 때문에 답을 $998 244 353$으로 나눈 나머지를 출력합니다.

Input
첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 10^4)$

각 테스트케이스의 첫번째 줄에는 심사위원의 수 $n$이 주어진다. $(2 \le n \le 2*10^5)$

각 테스트케이스의 두번째 줄에는 $i$번째 심사위원이 처리해야할 작업의 수인 $n$개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^9)$가 주어진다.

Output
각 테스트 케이스마다 좋은 수열의 개수를 $998 244 353$으로 나눈 나머지인 정수 1개를 출력한다.

Example
input
4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3

output
1
6
0
540

문제 접근

사용한 알고리즘: 조합론, 수학
걸린 시간 : 00:17
내가 못하는 분야만 골라서 쏙쏙 나온 미친 문제이다. 이것만 2시간 잡고 풀어도 나는 못푼다. 도대체 이런 문제를 풀기위해서는 어떻게 해야할까? 아직도 막막하다.

처음 문제를 봤을 때 이게 내가 영어인지 외계어인지 문제가 이해가 안됬다. 코드포스에서는 위에서 아무리 상황을 부여해봤자 그냥 문제 입력값보고 출력값 본 다음, 아래에 적혀있는 Note를 보면서 문제를 이해하는게 훨씬 빠른것 같다. 실제로 Note를 ㄹ보면서 문제를 이해하고나서 위에서 말한 상황이 한번에 이해가 됐다.

결국 이 문제는 팩토리얼 개수 구하기랑 같은데 거기에 여러 조건을 덧붙여서 만든 문제이다. 이 문제를 이해하기 위해서
4
1 3 3 7
이 예시를 토대로 설명을 진행해보자.
각 심사위원이 처리해야할 작업의 수는 각각 1, 3, 3, 7개이다. 우리가 $p$를 [1, 2, 3, 4]로 정하면 토의는 다음과 같이 진행된다. 첫번째 사람이 1개의 작업을 처리, 2번째 사람이 1개의 작업을 처리, 3번째 사람이 1개의 작업을 처리, 4번째 사람이 1개의 작업을 처리. 여기까지 하면 각 심사위원이 처리해야할 작업의 수는 0, 2, 2, 6개이다. 우리가 정한 p에따르면 4번째 사람이 작업을 처리하면 바로 다음 사람인 1번째 사람이 작업을 처리해야하는데, 1번째 사람이 남아있는 작업의 수가 0개이다. 따라서 1번째 사람은 넘어가고, 2번째 사람이 1개의 작업을 처리한다. 이런 방식으로 계속 진행하면 결국 마지막 사람만 작업이 4개가 남아있는 상황이 온다. 이때 이 사람이 연속해서 작업을 처리해야하기 때문에 $p$ [1, 2, 3, 4]는 좋은 수열이 아니다. 이제 문제가 이해가 되기 시작했을거라 생각한다.

첫번째로 주의깊게 볼 점은 예제 테스트케이스 중
3
5 5 5
이다. 이 테스트케이스의 답은 6인데, 3!의 값은 6이다. 따라서 숫자가 모두 같으면 좋지 않은 수열이 하나도 없다는 사실을 유추할 수 있다. 그렇다면 5가 최대값이고 5의 개수가 2개인 경우에는 어떨까? 조금만 노트에 적고 위에서 말한 방식을 따라한다면 좋지 않은 수열이 하나도 없다는 사실을 또 유추할 수 있다. 이 유추를 통해 최대값이 1개가 아닌 경우에는 좋지 않은 수열이 하나도 없다고 생각할 수 있다. 그리고 이 생각은 맞다. 왜냐하면 최대값이 2개 이상인 경우 시간이 지나면 결국 최대값을 가진 사람이 남게 되고, 이 작업을 남은 사람이 번갈아 가면서 처리하면 되기 때문이다.

이제 최대값이 1개인 경우만 고려하면 된다.
최대값이 1개인 경우는 이 최대값보다 1이 작은 수의 개수가 중요하다. 결국 회의가 끝날때는 이 최대값을 가진 사람의 작업으로 반드시 마무리 되어야 한다는 사실은 자명하다. 그러면 이 순열이 좋은 순열이 되려면 최대값보다 1이 작은 수의 작업을 가진 사람이 최대값을 가진 사람 바로 이전에 작업을 처리해야 이 사람이 작업을 끝나고 남은 1개의 작업을 최대값을 가진 사람이 끝내면서 회의를 끝낼 수 있다. 이 말은 최대값을 가진 사람 앞에 최대값보다 1이 작은 수를 가진 사람이 없다면 좋지 않은 수열이 된다는 뜻이다. 여사건을 이용해서 모든 경우의 수 $n!$에 좋지 않은 수열을 빼서 답을 계산하자.

좋지 않은 수열을 계산해보자.
최대값보다 1이 작은 수의 개수를 $k$라고 하자. 그러면 최대값도 아니고, k도 아닌 수의 개수는 $n - k - 1$이다. 이 수를 차례로 나열하는 경우의 수는 $nP_{n - k - 1} == \frac{n!}{(k + 1)!}$이다. 남은 k + 1 개의 수 중에서 최대값을 맨 앞에 두고 남은 k개의 수를 나열하는 경우의 수는 $k!$이므로 좋지 않은 수열은 $\frac{n!}{(k + 1)! * k!} == \frac{n!}{k + 1}$이다.

이것을 계산하기 위해서 팩토리얼을 계산한다음에 k + 1일때만 나누게 해서 답을 구했다. 이때 나머지 연산에 주의할점이 있는데, 뺄셈의 나머지 연산을 할 때는 음수가 나올 수 있기 때문에 나머지 연산을 하는 수를 더한 다음 나머지 연산을 해야한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

const int mod = 998244353;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i];
        int m = *max_element(arr, arr + n);
        int m_cnt = count(arr, arr + n, m);
        int cnt = count(arr, arr + n, m - 1);
        int ans = 1, sub = 1;
        for(long long i = 1; i <= n; i++){
            ans = (ans * i) % mod;
            if(i != cnt + 1) sub = (sub * i) % mod;
        }
        cout << (m_cnt >= 2 ? ans % mod : (ans - sub + mod) % mod) << "\n";
    }
    return 0;
}