Project Euler 15

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。

では、20 × 20 のマス目ではいくつのルートがあるか。

Mathematica

Binomial[40,20]

これは高校のテストなどでもある問題です。Combinationというやつですね。
Mathematicaなので1行で済みますが、Cなどで行う場合はint型の範囲を軽く超えてしまうため、各桁を配列にいれるなどの工夫が必要になるでしょう。

C/C++

とかなんとか上で言っていたけど、多倍長演算ライブラリmpir様のおかげで楽々。

#pragma comment(lib,"mpir.lib")
#include <iostream>
#include <mpir.h>
using namespace std;

// 階乗(mpir版)
void factorial(int n, mpz_t* ans){
	mpz_init_set_ui(*ans, 1);

	for(int i=1 ; i<=n ; i++){
		mpz_mul_ui(*ans,*ans, i);
	}
}


// combination(mpir版)
void combination(int m, int n, mpz_t* ans){
	mpz_t mf, nf, mnf;
	mpz_init_set_ui(*ans, 1);

	factorial(m, &mf);
	factorial(n, &nf);
	factorial(m-n, &mnf);

	mpz_mul(*ans, *ans, mf);
	mpz_div(*ans, *ans, nf);
	mpz_div(*ans, *ans, mnf);
}

int main(){
	int m=40, n=20;
	mpz_t ans;
	
	combination(m, n, &ans);
	mpz_out_str(stdout, 10, ans);

	return 0;
}

最初は関数の返り値をmpz_tにしようとしてたんですが、「配列を返り値にできるわけないだろ」的なことを言われたのでポインタ。本当は値の引数と格納用の変数は別にしておくべきなんですよねきっと。