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" となるように並べたもの。
- $(1-4),6,7,5$
- $(1-4),7,5,6$
- $(1-4),7,6,5$
- $6,(1-4),7,5$
- $5,7,(1-4),6$
- $5,6,7,(1-4)$
- $5,7,6,(1-4)$
- $6,5,7,(1-4)$
この $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 なので、DP で必要な値を求める。
$0$ と $1$ の並べ方は、
0 1
1 0の $2$ 通りなので、$\mathrm{dp}[1][1]=2$ である。
次に $i=2$ を求める。
$0$ 番目の次に初めて o となるのが $1$ 番目である並べ方は、
$0$ と $1$ のまとまりと $2$ を並べることで、
$\mathrm{dp}[2][1]=\mathrm{dp}[1][1]\times2!=2\times2=4$ 通りとなる。
$0,1,2$ の並べ方は全部で $3!=6$ 通りなので、o が先頭と末尾だけになる並べ方は、
$\mathrm{dp}[2][2]=6-4=2$ 通りである。
入力 "oxo" では、o は位置 $0$ と $2$ にある。
したがって、この区間に対応する $\mathrm{dp}[2][2]=2$ がそのまま答えとなる。
実際、条件を満たす順列は次の $2$ 通りである。
1 3 2
2 3 1注意点
階乗や DP の掛け算の途中結果は、int 型からはみ出る。
long long 型を用いること。
答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 する。
別解
特になし。