Project Euler 294

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

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.utils.getTimer;
	// @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(9));
//			tr(solve(42));
			tr(solve(Math.pow(11, 12)));
			var g : int = getTimer();
			tr((g - s) + " ms");
		}

		private function solve(N : Number) : Array
		{
			var i : uint, j : uint, k : uint, l : uint;
			
			// 合計iの数字が列に並んでいる場合の組み合わせ
			var upper : Array = makeComb(Math.floor(N / 22) + 1);
			var lower : Array = makeComb(Math.floor(N / 22));
			
			tr(upper);
			tr(lower);
			
			var t : Array = new Array(24 * 23);
			for(i = 0;i <= 24 * 23;i++)t[i] = [0];
			t[0] = [1];
			var mm : uint = 1;
			var ind : uint; 
			for(i = 0;i < 22;i++){
				var nex : Array = new Array(24 * 23);
				for(j = 0;j <= 24 * 23;j++)nex[j] = [0];
				for(k = 0;k <= 23;k++){
					for(j = 0;j <= 23 - k;j++){ 
						var ul : Number = i < N % 22 ? upper[j] : lower[j];
						var ula : Array = [ul % 1E7, uint(ul / 1E7)];
						for(l = 0;l < 23;l++){
							ind = (k + j) * 23 + ((l + mm * j) % 23);
							nex[ind] = NX.add(nex[ind], NX.mul(t[k * 23 + l], ula));
//							nex[ind] += (t[k * 23 + l] * upper[j]) % 1E9;
//							nex[ind] %= 1E9;
						}
					}
				}
				
				for(j = 0;j < 24 * 23;j++){
					t[j] = NX.mod(nex[j], [0, 100]);
				}
				
//				t = nex;
				tr(t);
				
				mm = (mm * 10) % 23;
			}
			
			return t[23 * 23];
		}
		
		private function makeComb(n : Number) : Array
		{
			var ret : Array = new Array(24);
			ret[0] = 1;
			var ps : Array = p([n % 1E7, int(n / 1E7)], 23);
			for(var i : uint = 1;i <= 23;i++){
				var s : Number = 0;
				for each(var d : Object in divide(i, Math.min(9, i))){
					var len : uint = 0;
					for each(var x : uint in d)len += x;
					if(len > n)continue;
					var cur : Array = ps[len];
					for each(x in d){
						for(var j : uint = 2;j <= x;j++){
							cur = NX.div(cur, [j])[0];
						}
					}
					s += cur[0] + (cur.length > 1 ? (cur[1] % 100) : 0) * 1E7;
				}
				ret[i] = s % 1E9;
			}
			return ret;
		}
		
		private function p(n : Array, k : uint) : Array
		{
			var ret : Array = [];
			var num : Array = [1];
			var nn : Array = n.concat();
			for(var i : uint = 0;i <= k;i++){
				ret.push(num.concat());
				num = NX.mul(num, nn);
				nn[0]--;
				if(nn[0] == -1){
					nn[0] += 1E7;
					nn[1]--;
				}
			}
			return ret;
		}
		
		private function divide(n : int, lim : int) : Array
		{
			if(n == 0)return [{}];
			if(n == 1){
				var o : Object = {};
				o[1] = 1;
				return [o];
			}
			var ret : Array = [];
            for(var i : uint = 1;i <= lim && i <= n;i++){
                for each(var val : Object in divide(n - i, i)){
                		if(val[i]){
                			val[i]++;
                		}else{
                			val[i] = 1;
                		}
                		ret.push(val);
                }
            }
            return ret;
		}
		
		/*
        private function divide(n : int, lim : int) : Array
        {
            if(n == 1)return [[1]];
            if(n == 0)return [[]];
            var ret : Array = [];
            for(var i : uint = 1;i <= lim && i <= n;i++){
                for each(var val : Array in divide(n - i, i)){
                    ret.push([i].concat(val));
                }
            }
            return ret;
        }
        */
        
		private function tr(...o : Array) : void
		{
			_tf.appendText(o + "\n");
			_tf.scrollV = _tf.maxScrollV;
		}
		
		private function test(N : Number) : Number
		{
			var lim : uint = Math.pow(10, N);
			var ct : uint = 0;
			for(var i : uint = 0;i < lim;i+=23){
				var sum : uint = 0;
				for(var j : uint = i;j > 0;j /= 10){
					sum += j % 10;
				}
				if(sum == 23){
					ct++;
				}
			}
			return ct;
		}
	}
}

class NX{
	public static const N : Number = 1E7;	
	
	public static function add(a : Array, b : Array) : Array
	{
		var i : uint;
		var minl : uint = Math.min(a.length, b.length);
		for(i = 0;i < minl;i++){
			a[i] += b[i];
		}
		for(i = a.length;i < b.length;i++){
			a.push(b[i]);
		}
		carry(a);
		return a;
	}
	
	public static function sub(a : Array, b : Array) : Array
	{
		var i : uint;
		for(i = 0;i < b.length;i++){
			a[i] -= b[i];
		}
		minuscarry(a);
		shave(a);
		return a;
	}
	
	public static function minuscarry(a : Array) : Array
	{
		for(var i : uint = 0;i < a.length;i++){
			if(a[i] < 0){
				var c : uint = (-a[i] + N - 1) / N;
				a[i] += N * c;
				a[i+1] -= c;
			}
		}
		return a;
	}

	public static function mul(a : Array, b : Array) : Array
	{
			var ret : Array = new Array(a.length + b.length);
	    var i : uint, j : uint;
	    for(i = 0;i < ret.length;i++)ret[i] = 0;
	    for(i = 0;i < a.length;i++){
	        for(j = 0;j < b.length;j++){
	            ret[i + j] += a[i] * b[j];
	        }
	    }
	    carry(ret);
	    shave(ret);
	    return ret;
	}

	public static function mulint(a : Array, b : uint) : Array
	{
			for(var i : uint = 0;i < a.length;i++){
				a[i] *= b;
			}
			carry(a);
	    return a;
	}

	public static function comp(a : Array, b : Array) : int
	{
			if(a.length != b.length)return a.length - b.length;
			for(var i : int = a.length - 1;i >= 0;i--){
				if(a[i] != b[i]){
					return a[i] - b[i];
				}
			}
			return 0;
	}

	public static function div(ao : Array, bo : Array) : Array
	{
			var p : Array = ao.concat();
			if(ao.length - bo.length < 0){
				return [0, p];
			}
			var b : Array = bo.concat();
			p.push(0);
			var d : Array = [];
			for(var i : int = p.length - b.length - 1;i >= 0;i--){
				var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
				var r : Array = b.concat();
				r = mulint(r, q0);
				while(true){
					var le : Boolean = false;
					for(var k : int = r.length;k >= 0;k--){
						var pp : Number = p[i+k] || 0;
						var rr : Number = r[k] || 0;
						if(pp != rr){
							le = pp < rr;
							break;
						}
					}
					if(le){
						q0--;
						sub(r, b);
					}else{
						break;
					}
				}
				d.push(q0);
			for(var j : uint = 0;j < r.length;j++){
				p[j + i] -= r[j];
			}
			minuscarry(p);
			}
			d.reverse();
			carry(d);
			shave(p);
			return [d, p];
	}

	public static function mod(ao : Array, bo : Array) : Array
	{
			var p : Array = ao.concat();
			if(ao.length - bo.length < 0){
				return p;
			}
			var b : Array = bo.concat();
			p.push(0);
			var d : Array = [];
			for(var i : int = p.length - b.length - 1;i >= 0;i--){
				var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
				var r : Array = b.concat();
				r = mulint(r, q0);
				while(true){
					var le : Boolean = false;
					for(var k : int = r.length;k >= 0;k--){
						var pp : Number = p[i+k] || 0;
						var rr : Number = r[k] || 0;
						if(pp != rr){
							le = pp < rr;
							break;
						}
					}
					if(le){
						q0--;
						sub(r, b);
					}else{
						break;
					}
				}
			for(var j : uint = 0;j < r.length;j++){
				p[j + i] -= r[j];
			}
			minuscarry(p);
			}
			shave(p);
			return p;
	}


	public static function carry(a : Array) : Array
	{
			for(var i : uint = 0;i < a.length;i++){
				if(a[i] >= N){
					var c : uint = a[i] / N;
					if(i == a.length - 1){
						a.push(0);
					}
					a[i + 1] += c;
					a[i] %= N;
				}
			}
			return a;
	}

	private static function gcd(a : Array, b : Array) : Array
	{
		while(b.length > 1 || b[0] > 0){
			var c : Array = a;
			a = b;
			b = mod(c, b);
		}
		return a;
	}
    
	public static function shave(a : Array) : Array
	{
			for(var i : uint = a.length - 1;i >= 1;i--){
				if(a[i] > 0)break;
				a.pop();
			}
			return a;
	}

        private static function addFractions(...o : Array) : Array
        {
        		if(o.length == 0)return [[0], [1]];
        		var ret : Array = o[0].concat();
        		for(var i : uint = 1;i < o.length;i++){
				var num : Array = add(mul(ret[0], o[i][1]), mul(ret[1], o[i][0]));
				var den : Array = mul(ret[1], o[i][1]);
				var g : Array = gcd(num, den);
        			ret[0] = div(num, g)[0];
        			ret[1] = div(den, g)[0];
        		}
        		return ret;
        }
}