Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

Untitled diff

Creado hace 9 añosEl diff nunca expira

10 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

218 líneas

86 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

289 líneas

import java.io.OutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.io.OutputStream;

import java.io.PrintWriter;

import java.util.Arrays;

import java.io.BufferedWriter;

import java.io.Writer;

import java.io.OutputStreamWriter;

import java.util.InputMismatchException;

import java.io.IOException;

import java.io.InputStream;

/**

* Built using CHelper plug-in

* Actual solution is at the top

public class Main {

public static void main(String[] args) {

InputStream inputStream = System.in;

OutputStream outputStream = System.out;

InputReader in = new InputReader(inputStream);

OutputWriter out = new OutputWriter(outputStream);

ConnectedPermutations solver = new ConnectedPermutations();

ColoredForests solver = new ColoredForests();

solver.solve(1, in, out);

out.close();

}

static class ConnectedPermutations {

static class ColoredForests {

public static int mod = 924844033;

public static long pr = Utils.mod_exp(5, 21 * 21 * 2, mod);

public static long[] om;

public static long[] cways;

public long[] fact;

public long[] ifact;

public long[] inv;

public long[] vals;

public long[] tr;

static {

om = new long[21];

om[20] = pr;

for (int i = 19; i >= 0; i--) {

om[i] = om[i + 1] * om[i + 1] % mod;

}

public long comb(int n, int k) {

return fact[n] * ifact[k] % mod * ifact[n - k] % mod;

}

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.nextInt();

int n = in.nextInt(), c = in.nextInt();

int m = 1 << 19;

int m = 1 << 17;

cways = new long[m + 2];

cways[0] = 1;

long[][] x = Factorials.getFIF(m + 2, mod);

fact = x[0];

ifact = x[1];

inv = x[2];

for (int i = 0; i < c; i++) cways[i] = 0;

long[][] pow = new long[c + 1][cways.length];

for (int i = 1; i <= c; i++) {

pow[i][0] = 1;

for (int j = 1; j < cways.length; j++) {

pow[i][j] = pow[i][j - 1] * i % mod;

}

long[][] comb = new long[c + 1][c + 1];

for (int i = 0; i <= c; i++) for (int j = 0; j <= i; j++) comb[i][j] = comb(i, j);

for (int i = c; i < cways.length; i++) {

cways[i] = Utils.mod_exp(c, i, mod);

for (int j = i - 1; j >= i - c; j--) {

if (((i - j) & 1) == 1) {

cways[i] = (cways[i] - comb[c][c - i + j] * pow[c - i + j][i]) % mod;

if (cways[i] < 0) cways[i] += mod;

} else {

cways[i] = (cways[i] + comb[c][c - i + j] * pow[c - i + j][i]) % mod;

}

vals = new long[m + 1];

vals[1] = 1;

for (int i = 2; i <= m; i++) vals[i] = vals[i - 1] * i % mod;

tr = new long[m + 1];

System.arraycopy(vals, 0, tr, 0, m + 1);

for (int i = 1; i <= m; i++) {

f(1, m);

tr[i] = Utils.mod_exp(i, i - 2, mod) * ifact[i - 1] % mod * cways[i] % mod;

}

vals[0] = 1;

f(0, m - 1);

for (int i = 1; i <= n; i++)

out.println(vals[i]);

out.println(vals[i] * fact[i] % mod);

}

public void f(int start, int end) {

if (start == end) return;

if (start == end) {

if (start != 0) vals[start] = vals[start] * inv[start] % mod;

return;

}

int mid = (start + end) / 2;

f(start, mid);

long[] x = Arrays.copyOfRange(vals, start, mid + 1);

long[] rr = multiply(x, tr);

for (int i = mid + 1; i <= end; i++)

vals[i] = (vals[i] - rr[i - start] + mod) % mod;

vals[i] = (vals[i] + rr[i - start] + mod) % mod;

f(mid + 1, end);

}

public void fft(long[] a, long omega) {

int N = a.length;

if (N == 1) return;

long[] even = new long[N / 2];

long[] odd = new long[N / 2];

for (int i = 0; 2 * i < N; i++) even[i] = a[2 * i];

for (int i = 0; 2 * i + 1 < N; i++) odd[i] = a[2 * i + 1];

long omega2 = omega * omega % mod;

fft(even, omega2);

fft(odd, omega2);

long cur = 1;

for (int i = 0; i < N / 2; i++) {

long x = cur * odd[i] % mod;

a[i] = (even[i] + x) % mod;

a[i + N / 2] = (even[i] + mod - x) % mod;

cur = cur * omega % mod;

}

public long[] multiply(long[] a, long[] b) {

int resultSize = Integer.highestOneBit(a.length - 1) << 2;

resultSize = Math.max(resultSize, 2);

long[] ax = new long[resultSize];

long[] bx = new long[resultSize];

for (int i = 0; i < a.length; i++)

ax[i] = a[i];

for (int i = 0; i < b.length && i < resultSize; i++)

bx[i] = b[i];

int ww = 31 - Integer.numberOfLeadingZeros(resultSize);

fft(ax, om[ww]);

fft(bx, om[ww]);

for (int i = 0; i < resultSize; i++)

ax[i] = ax[i] * bx[i] % mod;

fft(ax, Utils.inv(om[ww], mod));

long[] result = new long[resultSize];

long d = Utils.inv(resultSize, mod);

for (int i = 0; i < resultSize; i++) {

result[i] = ax[i] * d % mod;

}

return result;

}

static class OutputWriter {

private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {

writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));

}

public OutputWriter(Writer writer) {

this.writer = new PrintWriter(writer);

}

public void close() {

writer.close();

}

public void println(long i) {

writer.println(i);

}

static class InputReader {

private InputStream stream;

private byte[] buf = new byte[1024];

private int curChar;

private int numChars;

public InputReader(InputStream stream) {

this.stream = stream;

}

public int read() {

if (this.numChars == -1) {

throw new InputMismatchException();

} else {

if (this.curChar >= this.numChars) {

this.curChar = 0;

try {

this.numChars = this.stream.read(this.buf);

} catch (IOException var2) {

throw new InputMismatchException();

}

if (this.numChars <= 0) {

return -1;

}

return this.buf[this.curChar++];

}

public int nextInt() {

int c;

for (c = this.read(); isSpaceChar(c); c = this.read()) {

;

}

byte sgn = 1;

if (c == 45) {

sgn = -1;

c = this.read();

}

int res = 0;

while (c >= 48 && c <= 57) {

res *= 10;

res += c - 48;

c = this.read();

if (isSpaceChar(c)) {

return res * sgn;

}

throw new InputMismatchException();

}

public static boolean isSpaceChar(int c) {

return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;

}

static class Utils {

public static long inv(long N, long M) {

long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;

while (b != 0) {

q = a / b;

t = a % b;

a = b;

b = t;

t = x;

x = lastx - q * x;

lastx = t;

t = y;

y = lasty - q * y;

lasty = t;

}

return (lastx + M) % M;

}

public static long mod_exp(long b, long e, long mod) {

long res = 1;

while (e > 0) {

if ((e & 1) == 1)

res = (res * b) % mod;

b = (b * b) % mod;

e >>= 1;

}

return res;

}

static class Factorials {

public static long[][] getFIF(int max, int mod) {

long[] fact = new long[max];

long[] ifact = new long[max];

long[] inv = new long[max];

inv[1] = 1;

for (int i = 2; i < max; i++) {

inv[i] = (mod - mod / i) * inv[mod % i] % mod;

}

fact[0] = 1;

ifact[0] = 1;

for (int i = 1; i < max; i++) {

fact[i] = fact[i - 1] * i % mod;

ifact[i] = ifact[i - 1] * inv[i] % mod;

}

return new long[][]{fact, ifact, inv};

}

Diferencias guardadas

Texto original

Abrir archivo

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        ConnectedPermutations solver = new ConnectedPermutations();
        solver.solve(1, in, out);
        out.close();
    }

static class ConnectedPermutations {
        public static int mod = 924844033;
        public static long pr = Utils.mod_exp(5, 21 * 21 * 2, mod);
        public static long[] om;
        public long[] vals;
        public long[] tr;

static {
            om = new long[21];
            om[20] = pr;
            for (int i = 19; i >= 0; i--) {
                om[i] = om[i + 1] * om[i + 1] % mod;
            }
        }

public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int m = 1 << 19;
            vals = new long[m + 1];
            vals[1] = 1;
            for (int i = 2; i <= m; i++) vals[i] = vals[i - 1] * i % mod;
            tr = new long[m + 1];
            System.arraycopy(vals, 0, tr, 0, m + 1);
            f(1, m);
            for (int i = 1; i <= n; i++)
                out.println(vals[i]);
        }

public void f(int start, int end) {
            if (start == end) return;
            int mid = (start + end) / 2;
            f(start, mid);
            long[] x = Arrays.copyOfRange(vals, start, mid + 1);
            long[] rr = multiply(x, tr);
            for (int i = mid + 1; i <= end; i++)
                vals[i] = (vals[i] - rr[i - start] + mod) % mod;
            f(mid + 1, end);
        }

public void fft(long[] a, long omega) {
            int N = a.length;
            if (N == 1) return;
            long[] even = new long[N / 2];
            long[] odd = new long[N / 2];
            for (int i = 0; 2 * i < N; i++) even[i] = a[2 * i];
            for (int i = 0; 2 * i + 1 < N; i++) odd[i] = a[2 * i + 1];
            long omega2 = omega * omega % mod;
            fft(even, omega2);
            fft(odd, omega2);
            long cur = 1;
            for (int i = 0; i < N / 2; i++) {
                long x = cur * odd[i] % mod;
                a[i] = (even[i] + x) % mod;
                a[i + N / 2] = (even[i] + mod - x) % mod;
                cur = cur * omega % mod;
            }
        }

public long[] multiply(long[] a, long[] b) {
            int resultSize = Integer.highestOneBit(a.length - 1) << 2;
            resultSize = Math.max(resultSize, 2);
            long[] ax = new long[resultSize];
            long[] bx = new long[resultSize];
            for (int i = 0; i < a.length; i++)
                ax[i] = a[i];
            for (int i = 0; i < b.length && i < resultSize; i++)
                bx[i] = b[i];
            int ww = 31 - Integer.numberOfLeadingZeros(resultSize);
            fft(ax, om[ww]);
            fft(bx, om[ww]);
            for (int i = 0; i < resultSize; i++)
                ax[i] = ax[i] * bx[i] % mod;
            fft(ax, Utils.inv(om[ww], mod));
            long[] result = new long[resultSize];
            long d = Utils.inv(resultSize, mod);
            for (int i = 0; i < resultSize; i++) {
                result[i] = ax[i] * d % mod;
            }
            return result;
        }

}

static class OutputWriter {
        private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

public void close() {
            writer.close();
        }

public void println(long i) {
            writer.println(i);
        }

}

static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

public InputReader(InputStream stream) {
            this.stream = stream;
        }

public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

if (this.numChars <= 0) {
                        return -1;
                    }
                }

return this.buf[this.curChar++];
            }
        }

public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

int res = 0;

while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

throw new InputMismatchException();
        }

public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

}

static class Utils {
        public static long inv(long N, long M) {
            long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
            while (b != 0) {
                q = a / b;
                t = a % b;
                a = b;
                b = t;
                t = x;
                x = lastx - q * x;
                lastx = t;
                t = y;
                y = lasty - q * y;
                lasty = t;
            }
            return (lastx + M) % M;
        }

}
}

Texto modificado

Abrir archivo

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        ColoredForests solver = new ColoredForests();
        solver.solve(1, in, out);
        out.close();
    }

static class ColoredForests {
        public static int mod = 924844033;
        public static long pr = Utils.mod_exp(5, 21 * 21 * 2, mod);
        public static long[] om;
        public static long[] cways;
        public long[] fact;
        public long[] ifact;
        public long[] inv;
        public long[] vals;
        public long[] tr;

static {
            om = new long[21];
            om[20] = pr;
            for (int i = 19; i >= 0; i--) {
                om[i] = om[i + 1] * om[i + 1] % mod;
            }
        }

public long comb(int n, int k) {
            return fact[n] * ifact[k] % mod * ifact[n - k] % mod;
        }

public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), c = in.nextInt();
            int m = 1 << 17;
            cways = new long[m + 2];
            cways[0] = 1;
            long[][] x = Factorials.getFIF(m + 2, mod);
            fact = x[0];
            ifact = x[1];
            inv = x[2];
            for (int i = 0; i < c; i++) cways[i] = 0;
            long[][] pow = new long[c + 1][cways.length];
            for (int i = 1; i <= c; i++) {
                pow[i][0] = 1;
                for (int j = 1; j < cways.length; j++) {
                    pow[i][j] = pow[i][j - 1] * i % mod;
                }
            }
            long[][] comb = new long[c + 1][c + 1];
            for (int i = 0; i <= c; i++) for (int j = 0; j <= i; j++) comb[i][j] = comb(i, j);
            for (int i = c; i < cways.length; i++) {
                cways[i] = Utils.mod_exp(c, i, mod);
                for (int j = i - 1; j >= i - c; j--) {
                    if (((i - j) & 1) == 1) {
                        cways[i] = (cways[i] - comb[c][c - i + j] * pow[c - i + j][i]) % mod;
                        if (cways[i] < 0) cways[i] += mod;
                    } else {
                        cways[i] = (cways[i] + comb[c][c - i + j] * pow[c - i + j][i]) % mod;
                    }
                }
            }

vals = new long[m + 1];
            tr = new long[m + 1];
            for (int i = 1; i <= m; i++) {
                tr[i] = Utils.mod_exp(i, i - 2, mod) * ifact[i - 1] % mod * cways[i] % mod;
            }
            vals[0] = 1;
            f(0, m - 1);
            for (int i = 1; i <= n; i++)
                out.println(vals[i] * fact[i] % mod);
        }

public void f(int start, int end) {
            if (start == end) {
                if (start != 0) vals[start] = vals[start] * inv[start] % mod;
                return;
            }
            int mid = (start + end) / 2;
            f(start, mid);
            long[] x = Arrays.copyOfRange(vals, start, mid + 1);
            long[] rr = multiply(x, tr);
            for (int i = mid + 1; i <= end; i++)
                vals[i] = (vals[i] + rr[i - start] + mod) % mod;
            f(mid + 1, end);
        }

}

static class OutputWriter {
        private final PrintWriter writer;

public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

public void close() {
            writer.close();
        }

public void println(long i) {
            writer.println(i);
        }

}

static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

public InputReader(InputStream stream) {
            this.stream = stream;
        }

if (this.numChars <= 0) {
                        return -1;
                    }
                }

return this.buf[this.curChar++];
            }
        }

public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

int res = 0;

throw new InputMismatchException();
        }

public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

}

public static long mod_exp(long b, long e, long mod) {
            long res = 1;
            while (e > 0) {
                if ((e & 1) == 1)
                    res = (res * b) % mod;
                b = (b * b) % mod;
                e >>= 1;
            }
            return res;
        }

}

static class Factorials {
        public static long[][] getFIF(int max, int mod) {
            long[] fact = new long[max];
            long[] ifact = new long[max];
            long[] inv = new long[max];
            inv[1] = 1;
            for (int i = 2; i < max; i++) {
                inv[i] = (mod - mod / i) * inv[mod % i] % mod;
            }
            fact[0] = 1;
            ifact[0] = 1;
            for (int i = 1; i < max; i++) {
                fact[i] = fact[i - 1] * i % mod;
                ifact[i] = ifact[i - 1] * inv[i] % mod;
            }
            return new long[][]{fact, ifact, inv};
        }

}
}