競技プログラミング 知識集積所

ABC468 G - Restricted Permutation

制約付き順列

問題ページ解答例

考え方

まず、入力の先頭が 'x' だった場合。
これは、$1$ だけ見たときに $1$ の順列として連続していないと言っている。
そんなものがあるわけないので、答えは $0$。

次に、入力の末尾が 'x' だった場合。
これは、$1$ から $N$ までの順列全体を見たときに $1$ から $N$ までの順列として連続していないと言っている。
そんなものがあるわけないので、答えは $0$。

そして、$N$ が $1$ である場合。
そもそも順列が $1$ つしかなく、それは条件を満たすので、答えは $1$。

これらは、コーナーケースとして省いておく。

さて、例えば入力で "ooxoxxo" が来たとしよう。
これにおける $5$ と $6$ と $7$ の置き方を考えると、以下のようになる。
ただし、$(1-4)$ は、$1$ から $4$ までを "ooxo" となるように並べたもの。

この $5$ と $6$ と $7$ の置き方は実は、入力 "oxxo" に対する $1$ から $4$ までの並び順に対応する。
つまり、"ooxoxxo" のパターン数は、"ooxo" のパターン数と "oxxo" のパターン数の積である。

同様に、"ooxo" のパターン数は "oo" のパターン数と "oxo" のパターン数の積である。
つまり、'o' が先頭と末尾だけという入力に対する答えが全て求まれば、あとはただの掛け算となる。

そして、それは動的計画法で求まる。
ここからは 0-indexed で考える。
dp[i][j] は、$0$ から $i$ までを並べたとき、$0$ 番目の次に初めて o となるのが $j$ 番目である並べ方の個数。
初期値として、 dp[1][1] の値は明らかに $2$ である。

遷移は、以下のようになる。

まず、$i>j$ である場合。
この場合は、$0$ から $j$ までの並べ方 dp[j][j] 通りのいずれかを $1$ つ選ぶ。
それを $1$ つのカタマリとして、それと $j+1$ 以上の数を自由に並べればよい。
よって dp[i][j] は、dp[j][j] に $(i-j+1)!$ をかければよい。

次に、$i=j$ である場合（'o' が先頭と末尾だけという入力に対応している）。
これは、$\sum\nolimits_{j=1}^{i} dp[i][j] = (i+1)!$ であることから求まる。
すなわち、$1 \leq j < i$ であるようなものを全て $(i+1)!$ から引けばよい。

これで 'o' が先頭と末尾だけという入力に対する答えが全て求まった。
よって、あとは前述の通りのただの掛け算となる。
計算量は、DP部分が支配的で $O(N^2)$ となる。

入力例1での動作

入力を受け取る。

n: 3
s: "oxo"

先頭と末尾はどちらも o であり、$n=1$ でもないので、DP の処理へ進む。
result は $1$ で初期化されている。

result: 1

まず、$0$ と $1$ の並べ方は、

0 1
1 0

の $2$ 通りである。
どちらも $0$ と $1$ が連続しているので、初期値は次のようになる。

dp[1][1]: 2

次に、i=2 の場合を求める。
$0,1,2$ の並べ方は全部で $3!=6$ 通りなので、まず次のように初期化する。

dp[2][2]: 6

この中から、$0$ 番目の次に初めて o となるのが $1$ 番目である並べ方を除く。

$0$ と $1$ の内部の並べ方は dp[1][1]=2 通りである。
さらに、$0$ と $1$ のまとまりブロックと $2$ の並べ方は $2!=2$ 通りである。
したがって、該当する並べ方は、$\mathrm{dp}[1][1]\times 2! = 2\times 2 = 4$ 通りである。
これを引いて、$\mathrm{dp}[2][2]=3!-\mathrm{dp}[1][1]\times 2!=6-4=2$ となる。

dp[2][2]: 2

DP テーブルを作り終えたら、文字列 s を先頭の次から見る。
counter は、直前の o から何文字進んだかを表し、最初は $0$ である。

$i=1$ では、まず counter に $1$ 加える。

counter: 1

s[1] は x なので、まだ result には何も掛けず、次へ進む。

$i=2$ では、さらに counter に $1$ 加える。

counter: 2

s[2] は o である。
直前の o である s[0] からの距離は $2$ である。
よって、この区間に対応する並べ方の個数 dp[2][2]=2 を result に掛ける。

result: 2
counter: 0

注意点

階乗や DP の掛け算の途中結果は、int 型からはみ出る。
long long 型を用いること。

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 する。

別解

特になし。