No.171 スワップ文字列(Med)
No.171 スワップ文字列(Med) - yukicoder
- 組み合わせ計算問題
- 解くべき式は単純なんだけど、1/a! mod 573 をどう計算するか悩んだ。573 が素数のようなケースは過去にやったことがあったんだけど。
- 式変形して nCr の積に帰着させればよい。
- 最後の -1 部分でうっかり count=0 のケースで WA してしまった。こういうつまらないミスは本当になくしたいな....。
class SwapStringMed { public: void solve(void) { string S; cin>>S; const int Mod = 573; int N = S.size(); map<int,ll> cnt; for (auto c : S) { cnt.emplace(c,0); ++cnt[c]; } // 隣同士の swap だけ並び替えを表現できる // a,b,...,c をそれぞれのアルファベットの出現数として // N!/(a!b!...c!) を計算すればよいだけ // mod 込みの 1/a! 計算をする必要がある。 // // nCr = n!/(r!(n-r)!) より // N!/(a!b!) = N!/(a!(N-a)!) * (N-a!)/b! // = NCa * (N-a)Cb * (N-a-b)! // // と nCr で表現できるのでこれを計算すればよい nComb nCr(N, Mod); ll count = 1; for (auto c : cnt) { int a = c.second; (count *= nCr(N,a)) %= Mod; N -= a; } // (a+b+...+c = N より最後の (N-a-b)! = 0! = 1 となる) // 最初の文字列はのぞく(count=0 のときもあるので +Mod してから %Mod しておく) cout<<(count+Mod-1)%Mod<<endl; } };