Project Euler 169

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

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

        // 10^25を2進数表示する。
        // このうち、1になっているところ(C1)は、各桁の最大値を2まで許容すると、100→020→012のように一意に分解できていく。
        // これは次の1(N1)の位置まで続くが、この系列は、1→02→012→0112→01112・・・
        // のように2項目以降は2桁目が必ず1以上になるため、
        // N1が1の状態であるときは、C1は(C1の1の桁数-N1の1の桁数)通りの状態数を、
        // N1が2項目以降の状態であるときは、C1は(C1の1の桁数-N1の1の桁数+1)通りの状態数をもつ。
        // これをDPで計算していく。
        private function solve(s : String) : Number
        {
            var a : Array = [];
            var i : int;
            var prev : int = -1;
            for(i = 0;i < s.length;i++){
                if(s.charAt(i) == "1"){
                    if(prev != -1){
                        a.push(i - prev);
                    }
                    prev = i;
                }
            }
            if(prev != -1)a.push(s.length - prev);
            t(a);
            
            var uprev : Number = a[0];
            var vprev : Number = 1;
            for(i = 1;i < a.length;i++){
                var ucur : Number = uprev * a[i] + vprev * (a[i] - 1);
                var vcur : Number = uprev + vprev;
                uprev = ucur;
                vprev = vcur;
            }
            
            return uprev;
        }

	private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}