Project Euler 181

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/5kkL
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=181
    public class Euler181 extends Sprite {
        private var _tf : TextField;
  
        public function Euler181() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(10, 4));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var _cache : Array;
        private var _N : uint;
        private var _W : uint;

        // n : 残り個数
        // w : 残り個数のうちの白の個数
        // m : 最大の部分集合の要素数
        // wm : 最大の部分集合での白の最大数 (要素数mのとき以外は無効)
        // としてDP
        // n>=w>=wm, m>=wm, 
        // mが下がるとwmはmと同じになる、ということに注意
        private function solve(N : uint, W : uint) : Array
        {
        		_N = N;
        		_W = W;
        	
        		_cache = new Array((N+1) * (W+1) * (N+1) * (W+1));
        		for(var i : uint = 0;i < _cache.length;i++)_cache[i] = 0;
        		
        		return rec(N, W, N, W);
        }
        
        private function rec(n : uint, w : uint, m : uint, wm : uint) : Array
        {
        		if(n == 0 || m == 1)return [1, 0];
        		
        		var code : Number = (((n*(_W+1))+w)*(_N+1)+m)*(_W+1)+wm; 
        		if(_cache[code])return _cache[code];
        		var sum : Array = [0, 0];
        		var i : uint, j : uint;
        		if(n - m < m){
	        		for(j = 0;j <= wm;j++){
	        			if(n - m < w - j)continue;
	        			sum = N2.add(sum, rec(n - m, w - j, n - m, Math.min(n - m, w - j)));
	        		}
        		}else{
	        		for(j = 0;j <= wm;j++){
	        			if(n - m < w - j)continue;
	        			sum = N2.add(sum, rec(n - m, w - j, m, Math.min(w - j, j)));
	        		}
        		}
        			
        		sum = N2.add(sum, rec(n, w, m - 1, Math.min(m - 1, w)));
        		
//        		tr(n,w,m,wm,sum[0]);
        		_cache[code] = sum;
        		return sum;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}

class N2{
	public static const N : Number = 1E15;	
	public static function add(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] + b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + b[1] + rp;
		return [r0, r1];
	}
	
	public static function sub(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] - b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] - b[1] + rp;
		return [r0, r1];
	}
	
	public static function inc(a : Array, b : Number) : Array
	{
		var r0 : Number = a[0] + b;
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + rp;
		
		a[0] = r0;
		a[1] = r1;
		return a;
	}
}