SRM716 div2 hard

概要

最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。

解法

条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個の順列を取れば求まるため C(m, 1) * (m+n-1)!となり、これを引く。ここで、1点のみを固定して考えたとき重複してカウントしてしまっているパターンがある。m個の中から2個が条件を満たしていない場合の順列の個数は同様に考えると、C(m, 2) * (m+n-2)!となるため、これを足す。同様に重複して足した場合…と考えていくと、iが奇数の場合引いて、偶数の場合足している。つまり包除原理で解くことが出来る。