/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/jQ9h
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.getTimer;
// @see http://projecteuler.net/index.php?section=problems&id=297
public class Euler297 extends Sprite {
private var _tf : TextField;
public function Euler297() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
var s : int = getTimer();
// tr(solve(NX.pow([10], 6)));
tr(solve2(NX.sub(NX.pow([10], 6), [1])));
var g : int = getTimer();
tr((g - s) + " ms");
}
// なんか知らないけどn個のものから間隔1以上あけてm個取る組み合わせはC(n-m+1,m)個になる。
private function solve(n : Array) : Array
{
// Fibonacci
var F : Array = [[1], [2]];
var i : int;
while(NX.comp(F[F.length - 1], n) < 0){
F.push(NX.add(F[F.length - 2].concat(), F[F.length - 1]));
}
// tr(F.join('\n'));
var frac : Array = makeFracs(F.length);
n = NX.sub(n, [1]);
// n--;
var j : uint;
var sz : Array = [0];
var p : uint = 0;
for(i = F.length - 1;i >= 0;i--){
if(NX.comp(n, F[i]) >= 0){
n = NX.sub(n, F[i]);
// n -= F[i];
for(j = 1;j <= (i + 1) / 2;j++){
// sz += co[i][j] * (j + p);
sz = NX.add(sz, NX.mulint(combs(frac, i, j), j + p));
}
// sz += 1 * (1 + p);
sz = NX.add(sz, [1 + p]);
p++;
}
}
return sz;
}
private function makeFracs(n : uint) : Array
{
var frac : Array = [[1]];
var base : Array = [1];
for(var i : uint = 1;i <= n;i++){
base = NX.mulint(base, i);
frac.push(base.concat());
}
return frac;
}
private function combs(frac : Array, n : uint, r : uint) : Array
{
if(n < 0 || r < 0 || n - r + 1 < r)return [0];
var ret : Array = frac[n-r+1];
ret = NX.div(ret, frac[r])[0];
ret = NX.div(ret, frac[n-2*r+1])[0];
return ret;
}
/*
// combs(n,m)=H(n,m)=C(n-m+1,m)
private function combs(n : uint) : Vector.<Vector.<Number>>
{
var m : uint = (n + 1) / 2;
var c : Vector.<Vector.<Number>> = new Vector.<Vector.<Number>>(n + 1);
var i : uint, j : uint, k : uint;
for(i = 0;i < n + 1;i++){
c[i] = new Vector.<Number>(m + 1);
}
for(i = 0;i < n + 1;i++){
c[i][0] = 1;
}
for(j = 1;j <= m;j++){
for(i = 0;i < n + 1;i++){
if(j > (i + 1) / 2){
c[i][j] = 0;
continue;
}
var sum : Number = c[0][j - 1];
for(k = 1;k <= i - 1;k++){
sum += c[i - k - 1][j - 1];
}
c[i][j] = sum;
}
}
return c;
}
*/
public function solve2(n : Array) : Array
{
// Fibonacci
F = [[1], [2]];
var i : int;
for(i = 0;i < 100;i++){
F.push(NX.add(F[F.length - 2].concat(), F[F.length - 1]));
}
return rec(n);
}
private function rec(n : Array) : Array
{
if(n.length == 1 && n[0] == 0)return [0];
var nc : String = n.join(',');
if(map[nc])return map[nc];
for(var u : uint = 0;NX.comp(F[u], n) <= 0;u++);
u--;
var v : Array = rec(NX.sub(F[u].concat(), [1]));
v = NX.add(v, rec(NX.sub(n.concat(), F[u])));
v = NX.add(v, NX.sub(NX.add(n.concat(), [1]), F[u]));
map[nc] = v.concat();
// tr(nc, v);
return v;
}
private var F : Array;
private var map : Object = {};
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
_tf.scrollV = _tf.maxScrollV;
}
}
}
class NX{
public static const N : Number = 1E8;
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(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;
}
public static function pow(a : Array, b : uint) : Array
{
var ret : Array = [1];
var m : Array = a.concat();
for(var u : uint = b;u > 0;u >>= 1){
if(u & 1){
ret = mul(ret, m);
}
m = mul(m, m);
}
return ret;
}
}
