텍스트 비교

두 텍스트 파일의 차이점을 찾아보세요

실시간 편집

변경 없는 행 숨기기

줄바꿈 비활성화

레이아웃

비교 단위

구문 강조

Diffchecker Desktop 가장 안전하게 Diffchecker를 사용하는 방법. 데스크톱 앱을 사용하면 비교 데이터가 외부로 전송되지 않습니다!데스크톱 앱 받기

Untitled diff

생성일 9년 전비교 결과 만료 없음

10 삭제

행
총
삭제

글자
총
삭제

이 기능을 계속 사용하려면 업그레이드해 주세요 Diffchecker Pro 요금제 보기

218 행

86 추가

행
총
추가

글자
총
추가

이 기능을 계속 사용하려면 업그레이드해 주세요 Diffchecker Pro 요금제 보기

289 행

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

}

저장된 비교 결과

원본

파일 열기

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

}
}

수정본

파일 열기

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

}
}