ABC172 E - NEQ (500)
たぶん包除原理ってやつ
Aを$ A_i = iに固定して最後に$ n! _mC_nをかける
Aと$ i文字被る文字列は$ _{m-i}P_{n-i} \times {}_nC_i通りある
固定されている$ i文字以外の残りの選び方は$ _{m-i}P_{n-i}通り
$ i文字のパターンは$ _nC_i通り
$ iが偶数な場合は足して、奇数の場合は引く
組み合わせを事前に求めるのが$ O(M)、階乗と$ i文字重複の場合を全て求めるのがそれぞれ$ O(N)で全体で$ O(M+N)