https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_g
解説
https://atcoder.jp/contests/ttpc2019/submissions/7237908
操作は逆に行うこともできるので、問題の言い換えができる。
「操作をちょうどK回行うことで、文字列Tを何種類の回分にできるか」
という問題になる。
今回は操作の組み合わせではなく、結果の組み合わせだけを考えている。
そのため、ちょうどK回と指定があるが、K回以下の回数と考えても問題ない。
同じ所を編集すれば、回数を無駄に増やせるからである。
「操作をK回以下行うことで、文字列Tを何種類の回分にできるか」
これで何が良くなるかというと、あるゴールの回分を考えた時に、最短手順で構築して
手数がK回以下であるかを判定すればいいためである。
さて、まずはDPかなという感じもする。
回分を構築していくので、前半部分を構築すれば後半も構築できるので、N/2で考えていく。
奇数のときは、真ん中も考慮する必要がある。
dp[i][k] := i番目まで確定していてk回操作済みのときの組み合わせ
これはO(NK)でできる。
だが、Kが109なので、高速化は難しそう。
DPではないのか?
よくよく考えると、回分で対応している部分は他の部分とは独立している。
なので、DPで順番に決めていく必要はなさそうだ。
ここまでは経験から順当に行くかもしれないが、これ以降が難しい。
回分で対応するグループは3通りに分けられる。
same: s[i]=S[N-i]になってる
miss: s[i]!=S[N-1]になってる
center: Nが奇数の場合で中心になってる
sameをそのままの文字にするときは操作0回、違う文字にするなら操作2回必要。
missをそのままの文字にするときは操作1回、違う文字にするなら操作2回必要。
centerそのままの文字にするときは操作0回、違う文字にするなら操作1回必要。
これでだいぶ抽象化された。
sameとmissの文字を変える回数で全探索すれば、重複なく全通り数えられるのでは?
sameで違う文字にする組がcnt_same個、missで違う文字にする組がcnt_miss個とすると、
cnt_same2+cnt_miss2+(miss-cnt_miss)≦Kを満たせばいい。
この組み合わせ計算は、以下を事前計算しておく。
sameで違う文字にcnt_same組する場合の組み合わせ cmb_same(cnt_same) = C(same, cnt_same) * 25cnt_same
missで違う文字にcnt_miss組する場合の組み合わせ cmb_miss(cnt_miss) = C(miss, cnt_miss) * 24cnt_miss * 2miss-cnt_miss
すると、組み合わせはcmb_same(cnt_same)cmb_miss(cnt_miss)となる。
これで、O(N2)まで来た。
あとは、cnt_missで全探索する時に、使えるcnt_sameの範囲が[0,R]であるなら、
cmb_same(cnt_same)cmb_miss(0) + cmb_same(cnt_same)cmb_miss(1) + ... + cmb_same(cnt_same)cmb_miss(R)
= cmb_same(cnt_same) * (cmb_miss(0) + cmb_miss(1) + ... + cmb_miss(R))
となるため、累積和で高速化可能。
これでO(N)で間に合う(自分は横着してO(NlogN))
centerは2通りしかないので、こちらも全探索すればいい。
K=1のときは元々回分なのに壊すしかないというパターンが考えられるので場合分けして答えよう。
int N, K; string S; Comb<mint, 201010> com; mint cmb_miss[101010], cmb_same[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K >> S; int miss = 0, same = 0, center = N % 2; rep(i, 0, N / 2) { if(S[i] == S[N - 1 - i]) same++; else miss++; } if(K == 1) { int ans = 0; if (0 < center and miss == 0) ans = 25; else if (miss == 1) ans = 2; cout << ans << endl; return; } rep(cnt_same, 0, same + 1) cmb_same[cnt_same] = com.aCb(same, cnt_same) * (mint(25) ^ cnt_same); rep(cnt_same, 1, same + 1) cmb_same[cnt_same] += cmb_same[cnt_same - 1]; rep(cnt_miss, 0, miss + 1) cmb_miss[cnt_miss] = com.aCb(miss, cnt_miss) * (mint(24) ^ cnt_miss) * (mint(2) ^ (miss - cnt_miss)); mint ans = 0; rep(cnt_miss, 0, miss + 1) rep(cnt_center, 0, center + 1) { int ok = -1, ng = same + 1; while(ok + 1 != ng) { int cnt_same = (ok + ng) / 2; if (cnt_same * 2 + cnt_miss * 2 + (miss - cnt_miss) + cnt_center <= K) ok = cnt_same; else ng = cnt_same; } if(0 <= ok) { mint co = cmb_same[ok] * cmb_miss[cnt_miss]; if(0 < cnt_center) co *= 25; ans += co; } } cout << ans << endl; }