問題はこちら
No.170 スワップ文字列(Easy) - yukicoder
任意に入れ替えられるので元の文字列の並び順は関係なく、どの文字がいくつ使われているかを数えれば良い
あとは高校数学でやった「同じものを含む順列」
文字iが各a[i]個ある長さsの文字列を並べかえる順列はs!/Π(a[i]!) となる（Πは総積記号）
この式はa[i]に0が混ざっていても正しいので次のように書ける
int f(int n){return n<2?1:n*f(n-1);} int main(){ int i,s=1,a[99]={}; char x[10]; gets(x); for(i=0;x[i];i++)a[x[i]]++; s=f(strlen(x)); for(i='A';i<='Z';i++)s/=f(a[i]); printf("%d",s-1); //元の文字列と一致する分を引く return 0; }
一見すると割り算は最後にする必要があるように見えるが、次のように考えれば逐次実行できる
先頭から(n-1)文字目までの並び替えがs通りあるとする
このとき先頭からn文字目x[n]までの並び替えかたは、定義にしたがって計算するときに分子分母に新たに登場するものを考えれば
s*n/(n文字目までのx[n]の個数)となる
ということで
i,a[99];main(s){for(;i=getchar()-10?:!printf("%d",s-1);s=s*++*a/++a[i]);}
73B
