BOJ 34969 좋은 대화 수단

문제 링크입니다.

문제 요약

길이 $N$짜리 수열로 게임을 합니다. 각 턴마다 수열이 임의로 두 구간으로 나뉘면 한 구간에는 각 원소에 +1을, 다른 구간에는 각 원소에 -1을 해야 합니다. 게임을 아무리 진행해도 모든 원소를 1 이상으로 유지할 수 있도록 수열을 구성해야 합니다. $M$ 이하의 양의 정수로 이를 달성하는 방법의 수를 구하세요.

풀이

어떤 $x$가 존재하여, 모든 $i \in [1, N]$에 대해 $A_i \ge \vert i-x \vert +1$를 만족하는 경우 이를 역피라미드 꼴이라고 부릅시다.

Claim: 역피라미드 꼴임과 필승임이 동치입니다.

증명

① 역피라미드 꼴이면 필승입니다.

구간을 적당히 나눴을 때, 역피라미드의 중심이 있는 쪽에 +1을 하고, 다른 쪽에 -1을 합니다. 그러고 중심을 한 칸 옆으로 옮기면 여전히 역피라미드 꼴임을 알 수 있습니다.

역피라미드 꼴이 유지되는 한 모든 원소는 1 이상이므로 필승입니다.

② 역피라미드 꼴이 아니면 필승이 아닙니다.

각 원소마다 그 원소로 인해 역피라미드 꼴이 망가지지 않는 중심의 구간 $[L_i , R_i]$를 생각할 수 있습니다. 수열이 역피라미드 꼴이 아니라는 말은 모든 원소에 대해 그 원소가 $[L_i, R_i]$에 속하지 않게 되는 $i$가 존재함을 의미합니다.

$L$이 가장 큰 원소 $i$와 $R$이 가장 작은 원소 $j$를 고려합니다. 두 원소의 구간은 겹칠 수 없습니다. 겹치면 그 사이에 답이 되는 중심이 있다는 거니까요.

편의상 $L_{i} + 1 = R_{j}$이라고 합시다. 사이에 다른 원소가 있다면 그냥 없는 셈 치면 됩니다. 생각해 보면 $L_i$부터 $i$까지는 총 $A_i$개의 원소가 있고, $j$부터 $R_j$까지는 총 $A_j$의 원소가 있을 거에요. $A_i$로부터 $A_i$ 이상 떨어진 지점부터 $A_i$로 인해 역피라미드가 망가지는 거니까.

그래서 우리는 매번 구간을 $R_j$와 $L_i$가 끊어지도록 만들 수 있습니다. 이렇게 해서, $j \cdots R_j$와 $L_i \cdots i$가 각각 $A_j$와 $A_i$의 라이프처럼 사용되게 만들 겁니다. -1된 쪽이 길이가 줄어들고 +1된 쪽이 길이가 늘어나겠죠.

$i$ 또는 $j$까지 닿고 -1을 골라버리면 해당 원소가 $0$이 될 것이므로 우리는 반드시 방향 전환을 해야 합니다. 그런데 방향 전환을 하게 되면, 꺾이는 지점의 어느 한 원소가 혼자 -2를 퍼먹고 나머지 원소의 값은 그대로 유지되는 것을 발견할 수 있습니다.

이 과정을 계속 반복하면 어드밴티지 없이 사이의 원소들이 계속 깎여나가게 되어, 궁극적으로는 반드시 0인 원소가 생깁니다.

∴ 두 조건이 동치입니다!!

역피라미드 꼴이 성립하는 중심의 집합을 결정함에 따라 우리는 각 원소의 하한을 얻을 수 있습니다. 포함-배제의 원리를 적용하면 문제를 ${\cal O}(N^2 2^N)$ 정도에 해결할 수 있겠네요.

시간을 줄이기 위해 더블 카운팅을 합니다. 역피라미드 꼴이 성립하는 중심 중 가장 왼쪽에 있는 것을 기준으로 셀 겁니다. 오른쪽의 역피라미드는 일단 전부 무시하고, 피라미드 하나에 대한 답을 계산합니다. 순열의 개수의 곱 꼴로 나와서 쉽게 계산할 수 있어요.

여기서 왼쪽에 역피라미드가 있는 경우를 빼야 하는데요. 만약 두 위치 $j < i$를 중심으로 하는 역피라미드가 있다면, 두 역피라미드의 조건 중 더 어려운 쪽을 모든 원소가 만족하고 있으며, 역피라미드의 조건이 절댓값 함수 비스무리하게 생긴 꼴이라 $j+1$부터 $i-1$까지의 모든 위치를 중심으로 하는 역피라미드가 존재합니다.

$j+1$부터가 중요한 건 아니고, 왼쪽에 역피라미드가 있으면 $i-1$에 역피라미드가 있어야 한다는 점이 왕중요합니다. 그냥 이 경우만 빼면 포함-배제가 정상 작동한다는 의미거든요. 이 경우도 $i-1$과 $i$ 중 더 어려운 역피라미드 조건이 각 원소에 걸리고, 역시 순열의 개수의 곱 꼴로 계산됩니다.

팩토리얼 값과 그 역수를 전처리해 총 시간 복잡도 ${\cal O}(N+M)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

ll fac[1010101], inv[1010101];
inline ll P(ll n, ll r){return (n<r||r<0)?0:fac[n]*inv[n-r]%mod;}
 
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	fac[0] = 1; for(int i = 1; i <= 1000000; i++) fac[i] = fac[i-1]*i%mod;
	inv[1000000] = 490058372; for(int i = 1000000; i; i--) inv[i-1] = inv[i]*i%mod;
	int n, m; cin >> n >> m; ll ans = 0; for(int i = 1; i <= n; i++) ans = (ans+P(m, i)*P(m-1, n-i)%mod-(i!=1)*P(m-1, i-1)*P(m-1, n-i+1)%mod+2*mod)%mod; cout << ans;
}