整数分割

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

// forked from uwi's Project Euler 181
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://mathworld.wolfram.com/Partition.html
    public class Partition extends Sprite {
        private var _tf : TextField;
  
        public function Partition() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(5, solve(5));
            tr(10, solve(10));
            tr(50, solve(50));
            tr(100, solve(100));
            tr(200, solve(200));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var _cache : Array;
        private var _N : uint;

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