Project Euler 113
重複組み合わせだよなー、と、ぐぐる。
n種から重複を許してr個取る組み合わせ
増加数は0を使わないが、0を含めると、
0が0個 -> M桁の増加数
0が1個 -> M-1桁の増加数
0が2個 -> M-2桁の増加数
のように表現することができる。
0がM個のときは正数ではないので、省く。
増加数は、
10種から重複を許してM個取る組み合わせ数
0がM個のときは除くから
減少数は0を使う。
増加数と同様に桁数を決定する番兵?のようなものをイメージして、11種考えれば良い。
更に、111、222、333などの値は増加数・減少数ともに出てくる。
減少数は、
11種から重複を許してM個取る組み合わせ数
番兵がM個のとき、番兵と0のみの組み合わせのときは省くから
これらは 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); }
のように書いてて、とてつもなく遅かった。