Project Euler 217

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

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

        // 上半分と下半分それぞれに付いて、
        // 上位桁から順々に「桁の和」に対応する個数と和を足して求めて行く。
        // そして上下半分の同じ「桁の和」に対応する箇所を足し合わせる。
        // Tはより小さいけたの値も含むので、直前のTの値も足す。
        private function solve(N : uint) : Number
        {
        		var T : Array = [45];
        		var i : uint, j : uint, k : uint, l : uint;
        		for(k = 2;k <= N;k++){
	        		var s1 : Array = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
	        		var ss1 : Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
	        		for(l= 0;l < int(k/2-1);l++){
		        		var ns1 : Array = new Array(s1.length + 9);
		        		var nss1 : Array = new Array(ss1.length + 9);
		        		
		        		for(i = 0;i < ns1.length;i++)ns1[i] = 0;
		        		for(i = 0;i < nss1.length;i++)nss1[i] = 0;
		        		for(i = 1;i < s1.length;i++){
		        			for(j = 0;j <= 9;j++){
		        				ns1[i+j] += s1[i];
		        				ns1[i+j] %= M;
		        			}
		        		}
		        		for(i = 1;i < ss1.length;i++){
		        			for(j = 0;j <= 9;j++){
		        				nss1[i+j] += ss1[i] * 10 + j * s1[i];
		        				nss1[i+j] %= M;
		        			}
		        		}
		        		
		        		s1 = ns1;
		        		ss1 = nss1;
	        		}
	        		
	        		var s2 : Array = [1];
	        		var ss2 : Array = [0];
	        		for(l = 0;l < int(k/2);l++){
		        		var ns2 : Array = new Array(s2.length + 9);
		        		var nss2 : Array = new Array(ss2.length + 9);
		        		
		        		for(i = 0;i < ns2.length;i++)ns2[i] = 0;
		        		for(i = 0;i < nss2.length;i++)nss2[i] = 0;
		        		for(i = 0;i < s2.length;i++){
		        			for(j = 0;j <= 9;j++){
		        				ns2[i+j] += s2[i];
		        				ns2[i+j] %= M;
		        			}
		        		}
		        		for(i = 0;i < ss2.length;i++){
		        			for(j = 0;j <= 9;j++){
		        				nss2[i+j] += ss2[i] * 10 + j * s2[i];
		        				nss2[i+j] %= M;
		        			}
		        		}
		        		
		        		s2 = ns2;
		        		ss2 = nss2;
	        		}
	        			        		
	        		var sum : Number = 0;
	        		if(k % 2 == 0){
		        		// ss1*s2*10^(n/2) + ss2*s1
	        			var E : Number = exmod(10, k/2, M);
	        			for(i = 0;i < s1.length && i < s2.length;i++){
	        				sum += mulmod(M, ss1[i], s2[i], E);
	        				sum += mulmod(M, ss2[i], s1[i]);
	        				sum %= M;
	        			}
	        		}else{
		        		// ss1*10*s2*10^((n+1)/2) + 
		        		// 45*s1*s2*10^((n-1)/2) +
		        		// ss2*10*s1
		        		var F : Number = exmod(10, (k+1)/2+1, M);
		        		var G : Number = exmod(10, (k-1)/2, M);
		        		for(i = 0;i < s1.length && i < s2.length;i++){
		        			sum += mulmod(M, ss1[i], s2[i], F);
		        			sum += mulmod(M, 45, s1[i], s2[i], G);
		        			sum += mulmod(M, ss2[i], 10, s1[i]);
		        			sum %= M;
		        		}
	        		}
	        		
	        		sum += T[T.length - 1];
	        		sum %= M;
	        		T.push(sum);
        		}
        		return T.pop();
        }
        
        private function mulmod(m : uint, ...o : Array) : Number
        {
        		var ret : Number = 1;
        		for each(var e : Number in o){
        			ret *= e;
        			ret %= m;
        		}
        		return ret;
        }
        
        private function exmod(a : uint, n : uint, p : uint) : uint
        {
            var mul : Number = a;
            var ret : Number = 1;
            for(var i : uint = n;i > 0;i >>= 1){
                if((i & 1) == 1){
                    ret *= mul;
                    ret %= p;
                }
                mul *= mul;
                mul %= p;
            }
            return ret;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}