Project Euler 290

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=290
    public class Euler290 extends Sprite {
        private var _tf : TextField;
  
        public function Euler290() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(18));
//            tr(test(3));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // 0<=n<10^18の数のうち、
        // (nの各桁の和)=(137nの各桁の和)となるものは何通りあるか。
        //
        // 下の位から順に、
        // 137をかけたときの該当桁までの各位の和の差=D,と、
        // 該当桁以上=Uの箇所をあわせて状態として持って成長させていく。
        // 3の場合、3*137=411の1の位での差は-2=D,十の位以上は41=U
        // これを18桁分繰り返して、残ったUの部分はもう位上がりしないので和を逆算して
        // D=-Uとなるところを全部足せばOK
        // -9*18<=D<9*18
        // U<=137
        private function solve(n : int) : Array
        {
        		// upper, delta
        		var N : uint = 330;
        		var H : uint = 165;
        		var seed : Array = new Array(138*N);
        		var next : Array = new Array(138*N);
        		var i : uint, j : uint
        		for(i = 0;i < seed.length;i++){
        			seed[i] = 0;
        		} 
        		
        		seed[0*N+H] = 1;
        		for(i = 1;i <= n;i++){ 
	        		for(j = 0;j < seed.length;j++)next[j] = 0;
    				for(j = 0;j <= 137;j++){
        				for(var k : uint = 0;k <= 9;k++){
        					var nn : uint = j + k * 137;
        					var sub : int = (nn % 10) - k;
        					nn /= 10;
        					for(var l : uint = 0;l < N;l++){
	        					if(seed[j*N+l])next[nn*N+(l+sub)] += seed[j*N+l];
        					}
        				}
        			}
        			var d : Array = seed;
        			seed = next;
        			next = d;
        		}
        		
        		/*
        			for(j = 0;j < 138*500;j++){
        				if(seed[j] != 0){
        					tr(int(j/500), (j%500)-170, seed[j]);
        				}
        			}
        			*/
        			
        		var ret : Array = [0, 0];
        		for(i = 0;i <= 137;i++){
        			var sum : int = 0;
        			for(j = i;j > 0;j /= 10)sum += j % 10;
        			N2.inc(ret, seed[i*N+H-sum]);
        		}
        		return ret;
        }
        
        private function test(n : uint) : Number
        {
        		var lim : uint = Math.pow(10, n);
        		var j : uint;
        		var ret : uint = 0;
        		for(var i : uint = 0;i < lim;i++){
        			var ct : int = 0;
        			for(j = i;j > 0;j /= 10)ct += j % 10;
        			for(j = 137 * i;j > 0;j /= 10)ct -= j % 10;
        			if(ct == 0){
        				ret++;
        			}
        		}
        		return ret;
        }

        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;
	}
}