/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/t5iv
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// TODO C(3)を全数チェック
// @see http://projecteuler.net/index.php?section=problems&id=
public class Euler extends Sprite {
private var _tf : TextField;
public function Euler() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
tr(solve());
var g : int = getTimer();
tr((g - s) + " ms");
}
private var _cache : Array;
private const N : uint = 2;
private function solve() : Number
{
_cache = makeArray(N+1, N+1, N+1, N+1, 8);
var ret : Number = 0;
// 左上隅, 左下隅がアクティブ(台形)
var sum : Number = 0;
var i : uint, j : uint;
for(i = 1;i < N;i++){
for(j = i;j < N;j++){
sum += (rec(N, 0, 0, i) * rec(0, 0, N, N - j) * rec(0, N, 0, j - i + 1)) % 100000000;
}
}
tr(1, sum);
ret += sum * 4;
// 左上隅、右下隅がアクティブ(台形)
sum = 0;
for(i = 1;i < N;i++){
for(j = 1;j < N;j++){
// 隅を削る
sum += (rec(N, 0, 0, i) * rec(0, j, 0, N - i) * rec(0, N - i, N, 0)) % 100000000;
}
}
tr(2, sum);
ret += sum * 4;
// 左上隅、右下隅がアクティブ(対角線)
sum = (rec(N, 0, 0, N) * rec(0, N, N, 0)) % 100000000;
tr(3, sum);
ret += sum * 2;
// 左上隅だけがアクティブ
sum = 0;
for(i = 1;i < N;i++){
sum += (rec(N - 1, 0, 0, i) * rec(0, N - 1, N - 1, N - i)) % 100000000;
}
sum *= 2;
for(i = 1;i < N;i++){
for(j = 1;j < N;j++){
sum += (rec(N - 1, 0, 0, i) * rec(0, N - 1, j, 0) * rec(0, 0, N - j, N - i)) % 100000000;
}
}
tr(4, sum);
ret += sum * 4;
// すべてノンアクティブ
sum = rec(N - 1, N - 1, N - 1, N - 1);
tr(5, sum);
ret += sum;
return ret % 100000000;
}
// NESW
private function rec(a : uint, b : uint, c : uint, d : uint, prev : uint = 0) : Number
{
// tr(a, b, c, d, prev);
if(a + b + c + d <= 1)return 0;
if(a + b + c + d <= 3)return 1;
var ret : Number = 0;
var x : uint, y : uint, z : uint, w : uint;
if(_cache[a][b][c][d][prev] != null){
// tr(a,b,c,d,prev,_cache[a][b][c][d][prev]);
return _cache[a][b][c][d][prev];
}
/*
if(b == 0 && d == 0){
ret = C(a + c, c);
}else if(a == 0 && c == 0){
ret = C(b + d, d);
}else
}else{
*/
// a-b
x = a; y = b; z = c; w = d;
if(prev <= 0){
if((x >= 3 && y >= 1) || (x >= 2 && y >= 2) || (x == 2 && y == 1 && (z > 0 || w > 0)))ret = (ret + rec(a - 1, b, c, d, 0)) % 100000000;
if((y >= 3 && x >= 1) || (y >= 2 && x >= 2) || (y == 2 && x == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b - 1, c, d, 0)) % 100000000;
}
// b-c
x = b; y = c; z = d; w = a;
if(prev <= 1){
if((x >= 3 && y >= 1) || (x >= 2 && y >= 2) || (x == 2 && y == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b - 1, c, d, 1)) % 100000000;
if((y >= 3 && x >= 1) || (y >= 2 && x >= 2) || (y == 2 && x == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b, c - 1, d, 1)) % 100000000;
}
// c-d
x = c; y = d; z = a; w = b;
if(prev <= 2){
if((x >= 3 && y >= 1) || (x >= 2 && y >= 2) || (x == 2 && y == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b, c - 1, d, 2)) % 100000000;
if((y >= 3 && x >= 1) || (y >= 2 && x >= 2) || (y == 2 && x == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b, c, d - 1, 2)) % 100000000;
}
// d-a
x = d; y = a; z = b; w = c;
if(prev <= 3){
if((x >= 3 && y >= 1) || (x >= 2 && y >= 2) || (x == 2 && y == 1 && (z > 0 || w > 0)))ret = (ret + rec(a, b, c, d - 1, 3)) % 100000000;
if((y >= 3 && x >= 1) || (y >= 2 && x >= 2) || (y == 2 && x == 1 && (z > 0 || w > 0)))ret = (ret + rec(a - 1, b, c, d, 3)) % 100000000;
}
if(prev <= 4){
if(a == 1 && b == 1 && c == 1 && d == 1){
ret = 2;
}else if(a <= 1 && c <= 1){
ret = C(b + d, d);
}else if(b <= 1 && d <= 1){
ret = C(a + c, c);
}
}
/*
if(prev <= 4 && a >= 1 && c >= 1 && b == 1)ret = (ret + rec(a, 0, c, d, 4)) % 100000000;
if(prev <= 5 && a >= 1 && c >= 1 && d == 1)ret = (ret + rec(a, b, c, 0, 5)) % 100000000;
if(prev <= 6 && b >= 1 && d >= 1 && c == 1)ret = (ret + rec(a, b, 0, d, 6)) % 100000000;
if(prev <= 7 && b >= 1 && d >= 1 && a == 1)ret = (ret + rec(0, b, c, d, 7)) % 100000000;
*/
/*
// a-c, b-d
if(ret == 0){
if(a >= 2 && c >= 1 && (b == 0 || d == 0))ret = (ret + rec(a - 1, b, c, d, 4)) % 100000000;
if(c >= 2 && a >= 1 && (b == 0 || d == 0))ret = (ret + rec(a, b, c - 1, d, 5)) % 100000000;
if(b >= 2 && d >= 1 && (a == 0 || c == 0))ret = (ret + rec(a, b - 1, c, d, 6)) % 100000000;
if(d >= 2 && b == 1 && (a == 0 || c == 0))ret = (ret + rec(a, b, c, d - 1, 7)) % 100000000;
if(a == 1 && c == 1 && b == 1 && d == 1)ret = (ret + 2) % 100000000;
}
*/
_cache[a][b][c][d][prev] = ret;
return ret;
}
private function C(n : uint, k : uint) : Number
{
var mul : Number = 1;
for(var i : uint = 1;i <= k;i++){
mul *= n - i + 1;
mul /= i;
}
return mul;
}
private function makeArray(...o : Array) : Array
{
var l : uint = o.shift();
var ret : Array = new Array(l);
if(o.length > 0){
for(var i : uint = 0;i < l;i++){
ret[i] = makeArray.apply(null, o);
}
}
return ret;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
