yukicoder No.171 スワップ文字列(Med)

入れ替えにより結局任意の並び替えができるので、求める答え自体はyukicoder No.170 スワップ文字列(Easy)と同じ
しかし文字列の長さが最大1000になっているので階乗は計算出来ない

modの法573が小さな素因数3を持つので、逆元を用いて頑張るのもめんどくさい
ということでちょっと考え方を変える
文字iをa[i]個使うような長さsの文字列を次のように構成する
文字1を使う位置をs個の中からa[1]個選ぶ
文字2を使う位置をs-a[1]個の中からa[2]個選ぶ
…以下同様
このように考えると、位置の選び方と完成する文字列が1対1に対応するので、求める答えは $\displaystyle{\prod_{i=1}^{n}{}_{s-\sum_{k< i}a_k}C_{a_{i}}}$ となる
コンビネーションなのでパスカルの三角形を使えば求まる

ということで頑張って実装。

a[1010][1010];
int main(){
	int i,j,s,x,m=573,n[99]={};
	char t[1010];
	
	//パスカルの三角形
	for(i=0;i<=1e3;i++)for(j=0;j<=i;j++){
		if(j==0)a[i][j]=1;
		else a[i][j]=(a[i-1][j]+a[i-1][j-1])%m;
		//j==iのときa[i-1][j]は0
	}
	
	gets(t);s=1;x=0;
	//文字の個数
	for(i=0;t[i];i++){
		x++;
		n[t[i]]++;
	}
	
	//計算
	for(i='A';i<='Z';i++){
		s=s*a[x][n[i]]%m;
		x-=n[i];
	}
	printf("%d",(s-1+m)%m);
	return 0;
}

ということで各部分を特に工夫なく短縮していくと

n[99],a[1010][1010],m=573,x,i,j;
main(s){
	for(**a=1;i++<1e3;)for(j=-1;j++<i;a[i][j]=a[i-1][j]+a[i-1][j-1]%m);
	//本来は(a[i-1][j]+a[i-1][j-1])%mとすべきだが、mが小さいのでオーバーフローの心配はなくカッコを外す事ができる
	for(;i=getchar()-10;n[i]++)x++;
	for(i=99;--i;x-=j)s=s*a[x][j=n[i]]%m;
	i=!printf("%d",(s-1+m)%m);
}

となる。

パスカルの三角形の計算は以前やったようにjの正負を逆にすることで

for(**a=1;i+j--?a[i][-j]=a[i-1][-j]+a[i-1][~j]%m,1:(j=i++<999););

と2B縮む。このループは5000回くらい実行されるので、読み込み処理もまとめてしまえば

for(**a=1;i+j--?a[i][-j]=a[i-1][-j]+a[i-1][~j]%m,1:(j=i++<999);s>10?x++,n[s]++:0)s=getchar();

ループ終了時iが1000、sが-1であることを利用して以下のようにまとめられる

n[999],a[1010][1010],m=573,x,i,j;
//nのサイズが1桁増えた
main(s){
	for(**a=1;i+j--?a[i][-j]=a[i-1][-j]+a[i-1][~j]%m,1:(j=i++<999);s>10?x++,n[s]++:0)s=getchar();
	for(;--i;x-=j)s=s*a[x][j=n[i]]%m;
	i=!printf("%d",(m-s-1)%m);
	//sは-1倍されている
}

読み込み部分をもうちょっと工夫する
s>10?の部分が冗長に見えるので、sが-1でもn[s]++が動くことを祈って

for(;;s>10?x++,n[s]++:0)s=getchar();
for(;;x+=s>10,n[s]++)s=getchar();
for(;;n[s]++)s=getchar(x+=s>10);

と書き換え。ただしこれによりn[10]に1が入ってしまい、最後の計算部分でa[0][1]（この値は0）が掛けられてしまうことを防ぐために終了条件をいじって

n[999],a[1010][1010],m=573,x,i,j;
main(s){
	for(**a=1;i+j--?a[i][-j]=a[i-1][-j]+a[i-1][~j]%m,1:(j=i++<999);n[s]++)s=getchar(x+=s>10);
	for(;--i>10;x-=j)s=s*a[x][j=n[i]]%m;
	i=!printf("%d",(m-s-1)%m);
}

193B　もうちょい縮みそう？

メモ

yukicoderでゆるふわgolf

yukicoder No.171 スワップ文字列(Med)