ichirin2501's diary

いっちりーん。

Project Euler 113

重複組み合わせだよなー、と、ぐぐる


n種から重複を許してr個取る組み合わせ
{}_n H _r \;\;=\;\; {}_{n+r-1} C _r

増加数は0を使わないが、0を含めると、
0が0個 -> M桁の増加数
0が1個 -> M-1桁の増加数
0が2個 -> M-2桁の増加数
のように表現することができる。
0がM個のときは正数ではないので、省く。


増加数は、
10種から重複を許してM個取る組み合わせ数
{}_{10} H _M \;\;=\;\; {}_{10+M-1} C _M \;\;=\;\; {}_{M+9} C _{(10+M-1)-M} \;\;=\;\; {}_{M+9} C _9
0がM個のときは除くから {}_{M+9} C _9 \;-\;1

減少数は0を使う。
増加数と同様に桁数を決定する番兵?のようなものをイメージして、11種考えれば良い。


減少数は、
11種から重複を許してM個取る組み合わせ数
{}_{11} H _M \;\;=\;\; {}_{11+M-1} C _M \;\;=\;\; {}_{M+10} C _{(11+M-1)-M} \;\;=\;\; {}_{M+10} C _{10}
番兵がM個のとき、番兵と0のみの組み合わせのときは省くから
{}_{M+10} C _{10} \;-\;1 \;-\;M
更に、111、222、333などの値は増加数・減少数ともに出てくる。
これらは 9*M 出てくるから、この値を引く。

long long C(int n, int r){
   if( r==0 )return 1;
   return C(n,r-1) * (n-r+1)/r;
}
void pro113(void){
   long long ans;
   int M = 100;
   ans = C(9+M,9)-1 + C(10+M,10)-M-1 - 9*M;
   printf("ans:%lld\n",ans);
}


hatenaのTex記法汚いなー。
アンチエイリアスが効いた画像を貼り付けたほうがずっと見栄えがいい。
組み合わせを求める再帰関数を、

long long C(int n, int r){
   if( n<=0 || r<0 ) return 0;
   if( r==0 )return 1;
   return C(n-1,r) + C(n-1,r-1);
}

のように書いてて、とてつもなく遅かった。