Comparar texto

Encontre a diferença entre dois arquivos de texto

Editor live

Recolher inalteradas

Sem quebra de linha

Layout

Nível de detalhe

Realce de sintaxe

Diffchecker Desktop A maneira mais segura de usar o Diffchecker. Obtenha o aplicativo Diffchecker Desktop: seus diffs nunca saem do seu computador!Obter Desktop

Untitled diff

Criado há 9 anosO diff nunca expira

10 remoções

Linhas
Total
Removido

Caracteres
Total
Removido

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

218 linhas

86 adições

Linhas
Total
Adicionado

Caracteres
Total
Adicionado

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

289 linhas

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};

}

Diferenças salvas

Texto original

Abrir arquivo

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 alterado

Abrir arquivo

/**
 * 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};
        }

}
}