たぶん包除原理ってやつ 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)…