package ggw2;

import java.math.BigInteger;
import java.util.*;

public final class PrintDValuesToMaple {
    public static final class Fraction {
        public static final Fraction ZERO = new Fraction(BigInteger.ZERO);
        public static final Fraction ONE = new Fraction(BigInteger.ONE);

        private BigInteger num;
        private BigInteger den;

        public Fraction(long num) {
            this(BigInteger.valueOf(num));
        }

        public Fraction(BigInteger num) {
            this(num, BigInteger.ONE);
        }

        public Fraction(BigInteger num, BigInteger den) {
            if (den.equals(BigInteger.ZERO)) throw new RuntimeException("div by 0");
            this.num = num;
            this.den = den;
            simplify();
        }

        private Fraction(BigInteger num, BigInteger den, Object o) {
            if (den.equals(BigInteger.ZERO)) throw new RuntimeException("div by 0");
            if (den.signum() == -1) {
                den = den.negate();
                num = num.negate();
            }
            this.num = num;
            this.den = den;
        }

        public Fraction(Fraction d) {
            this(d.num, d.den);
        }

        private void simplify() {
            if (num.equals(BigInteger.ZERO)) {
                den = BigInteger.ONE;
                return;
            }
            if (den.signum() == -1) {
                den = den.negate();
                num = num.negate();
            }
            if (!den.equals(BigInteger.ONE)) {
                BigInteger gcd1 = num.gcd(den);
                num = num.divide(gcd1);
                den = den.divide(gcd1);
            }
        }

        public Fraction add(Fraction d) {
            return new Fraction(num.multiply(d.den).add(den.multiply(d.num)), den.multiply(d.den));
        }

        public Fraction subtract(Fraction d) {
            return new Fraction(num.multiply(d.den).subtract(den.multiply(d.num)), den.multiply(d.den));
        }

        public Fraction multiply(Fraction d) {
            if (num.equals(BigInteger.ZERO) || d.num.equals(BigInteger.ZERO)) return ZERO;
//
            Fraction a = new Fraction(num, d.den);
            Fraction b = new Fraction(d.num, den);
            return new Fraction(a.num.multiply(b.num), a.den.multiply(b.den), null);
        }

        public Fraction divide(Fraction d) {
            if (num.equals(BigInteger.ZERO)) return ZERO;
            return new Fraction(num.multiply(d.den), den.multiply(d.num));
        }

        public BigInteger getNum() {
            return num;
        }

        public BigInteger getDen() {
            return den;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Fraction fraction = (Fraction) o;

            if (num.equals(fraction.num) && den.equals(fraction.den)) return true;

            return subtract(fraction).num.equals(BigInteger.ZERO);
        }

        @Override
        public int hashCode() {
            return 31 * num.hashCode() + den.hashCode();
        }

        public String toString() {
            return num + (den.equals(BigInteger.ONE) ? "" : "/" + den);
        }
    }

    public static final class MultiPolynomial {
        public final List<Polynomial> factors = new ArrayList<>();

        public MultiPolynomial(Polynomial polynomial) {
            factors.add(polynomial);
        }

        public MultiPolynomial simpleFactor(int level) {
            while (tryFactor(new Polynomial(0, 1))) ;
            for (int i = level - 2; i < level + 2; i++) {
                while (tryFactor(new Polynomial(-i, 1))) ;
            }
            factorOutLcm();
            return this;
        }

        public boolean tryFactor(Polynomial divisor) {
            if (divisor.coefficients.size() == 1 && divisor.coefficients.get(0).equals(Fraction.ONE)) return false;
            try {
                Polynomial polynomial = factors.get(0);
                factors.set(0, polynomial.divideExact(divisor));
                factors.add(divisor);
                return true;
            } catch (Throwable ignored) {
                return false;
            }
        }

        public boolean factorOutLcm() {
            BigInteger lcm = BigInteger.ONE;
            for (Fraction fraction : factors.get(0).coefficients) {
                BigInteger i = fraction.getDen();
                BigInteger gcd = lcm.gcd(i);
                if (gcd.equals(BigInteger.ONE)) {
                    lcm = lcm.multiply(i);
                } else if (!i.equals(gcd)) {
                    lcm = lcm.multiply(i.divide(gcd));
                }
            }

            return tryFactor(new Polynomial(new Fraction(BigInteger.ONE, lcm)));
        }
    }

    public static final class Polynomial {
        public static final Polynomial ZERO = new Polynomial(new Fraction[0]);

        public final List<Fraction> coefficients = new ArrayList<>();

        public Polynomial(Collection<Fraction> coefficients) {
            this.coefficients.addAll(coefficients);
            simplify();
        }

        public Polynomial(Fraction... coefficients) {
            Collections.addAll(this.coefficients, coefficients);
            simplify();
        }

        public Polynomial(long... coefficients) {
            for (long i : coefficients) {
                this.coefficients.add(new Fraction(i));
            }
            simplify();
        }

        public Polynomial(Polynomial p) {
            coefficients.addAll(p.coefficients);
            simplify();
        }

        private Polynomial simplify() {
            for (int i = coefficients.size() - 1; i >= 0; i--) {
                Fraction c = coefficients.get(i);
                if (!c.equals(Fraction.ZERO)) break;
                coefficients.remove(i);
            }
            return this;
        }

        public Polynomial add(Polynomial p) {
            int n = Math.max(coefficients.size(), p.coefficients.size());
            Polynomial ret = new Polynomial(new ArrayList<>(n));
            for (int i = 0; i < n; i++) {
                Fraction a = coefficients.size() > i ? coefficients.get(i) : Fraction.ZERO;
                Fraction b = p.coefficients.size() > i ? p.coefficients.get(i) : Fraction.ZERO;
                ret.coefficients.add(a.add(b));
            }
            return ret.simplify();
        }

        public Polynomial subtract(Polynomial p) {
            int n = Math.max(coefficients.size(), p.coefficients.size());
            Polynomial ret = new Polynomial(new ArrayList<>(n));
            for (int i = 0; i < n; i++) {
                Fraction a = coefficients.size() > i ? coefficients.get(i) : Fraction.ZERO;
                Fraction b = p.coefficients.size() > i ? p.coefficients.get(i) : Fraction.ZERO;
                ret.coefficients.add(a.subtract(b));
            }
            return ret.simplify();
        }

        public Polynomial multiply(Polynomial p) {
            int n = coefficients.size() + p.coefficients.size() - 1;
            Polynomial ret = new Polynomial(new ArrayList<>(n));
            for (int i = 0; i < n; i++) {
                ret.coefficients.add(Fraction.ZERO);
            }
            for (int i = 0; i < coefficients.size(); i++) {
                Fraction a = coefficients.get(i);
                for (int j = 0; j < p.coefficients.size(); j++) {
                    Fraction b = p.coefficients.get(j);
                    ret.coefficients.set(i + j, ret.coefficients.get(i + j).add(a.multiply(b)));
                }
            }
            return ret.simplify();
        }

        public Polynomial divide(Polynomial b) {
            Polynomial a = this;
            if (b.coefficients.isEmpty()) throw new RuntimeException("div by 0 polynomial");
            if (a.coefficients.size() < b.coefficients.size()) return ZERO;

            Fraction coefficient = a.coefficients.get(a.coefficients.size() - 1).divide(b.coefficients.get(b.coefficients.size() - 1));
            int exponent = a.coefficients.size() - b.coefficients.size();

            Polynomial c = new Polynomial(ZERO);
            for (int i = 0; i < exponent; i++) {
                c.coefficients.add(Fraction.ZERO);
            }
            c.coefficients.add(coefficient);

            return c.add(a.subtract(b.multiply(c)).divide(b)).simplify();
        }

        public Polynomial divideExact(Polynomial b) {
            Polynomial ret = divide(b);
            if (ret.multiply(b).equals(this)) return ret;
            throw new RuntimeException("polynomial division has remainder");
        }

        public MultiPolynomial simpleFactor(int level) {
            return new MultiPolynomial(this).simpleFactor(level);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            return coefficients.equals(((Polynomial) o).coefficients);
        }

        @Override
        public int hashCode() {
            return coefficients.hashCode();
        }
    }

    private static BigInteger c(int N, int j, int[] K) {
        if (accumulate(K) == 0) return BigInteger.ONE;
        int sum = 0;
        for (int i = N; i < K.length; i++) {
            sum += K[i];
        }
        if (sum != 0) return BigInteger.ZERO;
        int sumK = accumulate(K);
        BigInteger num = BigInteger.valueOf(j);
        BigInteger den = BigInteger.valueOf(N * sumK);
        for (int i = 0; i < j + sumK; i++) num = num.multiply(BigInteger.valueOf(-1L));
        num = num.multiply(factorial(sumK));
        for (int i : K) {
            den = den.multiply(factorial(i));
        }
        for (int i = 0; i < N; i++) {
            for (int jj = 0; jj < (i >= K.length ? 0 : K[i]); jj++) {
                num = num.multiply(choose(N, i + 1));
            }
        }
        return num.divide(den);
    }

    public static BigInteger d(int N, int j, int[] K) {
        int L = Math.max(N, j);
        BigInteger d = c(N, j, K);

        for (int i = 0; i < L; i++) {
            if (i < K.length && K[i] >= 1) {
                BigInteger addend = choose(j, i + 1);
                for (int ii = 0; ii < i + 1; ii++) addend = addend.multiply(BigInteger.valueOf(-1L));
                int[] K2 = Arrays.copyOf(K, K.length);
                K2[i]--;
                j -= i + 1;
                addend = addend.multiply(c(N, j, K2));
                d = d.add(addend);
                j += i + 1;
            }
        }
        return d;
    }

    private static final BigInteger[] FACTORIALS = new BigInteger[1000];

    static {
        for (int i = 0; i < 1000; i++) {
            BigInteger ret = BigInteger.ONE;
            for (int i1 = 0; i1 < i; i1++) {
                ret = ret.multiply(BigInteger.valueOf(i1 + 1));
            }
            FACTORIALS[i] = ret;
        }
    }

    private static BigInteger factorial(int n) {
        if (n >= FACTORIALS.length) throw new RuntimeException();
        return FACTORIALS[n];
    }

    public static BigInteger choose(int n, int k) {
        if (k > n) return BigInteger.ZERO;
        return factorial(n).divide(factorial(k)).divide(factorial(n - k));
    }

    private static int accumulate(int... list) {
        int ret = 0;
        for (int i : list) {
            ret += i;
        }
        return ret;
    }

    private static boolean isOneValue(Fraction... array) {
        Fraction v = array[0];
        for (Fraction i : array) {
            if (!v.equals(i)) return false;
        }
        return true;
    }

    public static Polynomial findPolynomial(List<Fraction> data) {
        Fraction[] coefficients = new Fraction[data.size() + 1];
        for (int i = 0; i < coefficients.length; i++) {
            coefficients[i] = Fraction.ZERO;
        }

        while (true) {
            Fraction[] copy = new Fraction[data.size()];
            for (int i = 0; i < data.size(); i++) {
                copy[i] = new Fraction(data.get(i));
            }

            Fraction[] d = copy;

            for (int N = 0; N < d.length; N++) {
                BigInteger pow = BigInteger.ONE;
                for (Fraction coefficient : coefficients) {      //subtract the current trial polynomial from the data
                    Fraction temp = coefficient.multiply(new Fraction(pow));
                    d[N] = d[N].subtract(temp);
                    pow = pow.multiply(BigInteger.valueOf(N + 1));
                }
            }

            if (d[0].equals(Fraction.ZERO) && isOneValue(d)) break;   //if data is 0 we are done

            int i = 0;
            while (!isOneValue(d)) {
                Fraction[] temp = new Fraction[d.length - 1];

                for (int N = 0; N < temp.length; N++) {
                    temp[N] = d[N + 1].subtract(d[N]);
                }

                d = temp;
                i++;
            }

            coefficients[i] = coefficients[i].add(new Fraction(d[0].divide(new Fraction(factorial(i)))));
        }

        return new Polynomial(coefficients);
    }

    public static void main(String... args) {
        int level = 6; // "level" is DEGREE.  Change this value to obtain different lines of the OEIS triangle A290053
        int dataCount = level + 20;
        System.out.println("restart;\n" +
                "prefy:=(d,r,N)->sum(zic[r][Norder]*N^Norder,Norder=0..d):\n" +
                "A:=(d,r)->[seq(prefy(d,r,n),n=1.." + dataCount + ")]:\n" +
                "\n" +
                "C:=(d,r)->A(d,r)-B[r]:\n" +
                "coefs:=(d,r)->solve({seq(C(d,r)[n]=0,n=1.." + dataCount + ")}):\n" +
                "fy:=(d,r,N)->factor(subs(coefs(d,r),prefy(d,r,N))): ");
        int[] k = new int[level];
        k[level - 1] = 1;
        int j = 0;
        for (int i = 0; i < k.length; i++) {
            j += (i + 1) * k[i];
        }

        System.out.print("B[" + j + "=" + Arrays.toString(k) + "]:=[");
        List<Fraction> list = new ArrayList<>();
        for (int N = 1; N < dataCount + 1; N++) { //
            if (N != 1) System.out.print(", ");
            System.out.print(d(N, j, k));
            list.add(new Fraction(d(N, j, k)));
        }
        System.out.println("]:");
        System.out.println("f[" + j + "=" + Arrays.toString(k) + "]:=fy(" + j + ", " + j + "=" + Arrays.toString(k) + ", N);");

        System.out.println("\n\n\n\n\n\n");
        MultiPolynomial f = findPolynomial(list).simpleFactor(level);
        List<Fraction> coefficients = f.factors.get(0).coefficients;
        for (int i = coefficients.size() - 1; i >= 0; i--) {
            System.out.print(coefficients.get(i) + ", ");
        }

        System.out.println();
    }
}