ABC171 F - Strivore (600)
小さい文字数で試してみると実は文字数が同じならば文字列は何でも良い
Sは全て同じ文字列と仮定してSの長さをNとする
求める組み合わせは作れる全ての組み合わせから1からK文字が元のSと重複する組み合わせを引けば良い
作れる全ての文字列は$ 26^k {}_{n+k}C_n通り
i文字が重複する場合に引く必要のある組み合わせは$ (_{n+k}C_k - 1) {}_{n+k}C_{k-i} 25^{k-i}
前準備が$ O(N+K)、引く場合を求めるのが$ O(K \log K)で全体で$ O(N + K \log K)