Contest Duration: - (local time) (130 minutes) Back to Home

Submission #6386008

Source Code Expand

Copy
```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
*
* @author Egor Kulikov (egor@egork.net)
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
OutputWriter out = new OutputWriter(outputStream);
solver.solve(1, in, out);
out.close();
}

public void solve(int testNumber, InputReader in, OutputWriter out) {
PrimeFastFourierTransform fft = new PrimeFastFourierTransform(MiscUtils.MODF);
long[] res = new long[n + 1];
long[] revFac = IntegerUtils.generateReverseFactorials(n + 1, MiscUtils.MODF);
for (int i = 0; i <= n; i++) {
res[i] = (n + 1 - i) * revFac[i] % MiscUtils.MODF;
}
long[] ans1 = new long[n + 1];
fft.power(ans1, res, m);
long[] ans = new long[n + 1];
long[] next = new long[n + 1];
ans[0] = 1;
long[] ansNext = new long[n + 1];
for (int i = 0; (1 << i) <= m; i++) {
if ((m >> i & 1) == 1) {
fft.multiply(ansNext, ans, res, n + 1);
long[] temp = ans;
ans = ansNext;
ansNext = temp;
}
fft.multiply(next, res, res, n + 1);
long[] temp = res;
res = next;
next = temp;
}
for (int i = 0; i <= n; i++) {
answer += ans[i] * revFac[n - i] % MiscUtils.MODF;
}
}

}

private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

this.stream = stream;
}

if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}

while (isSpaceChar(c)) {
}
int sgn = 1;
if (c == '-') {
sgn = -1;
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
} while (!isSpaceChar(c));
return res * sgn;
}

public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return isWhitespace(c);
}

public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);

}

}

static class IntegerUtils {
private static long _x;
private static long _y;

public static long trueMod(long a, long b) {
a %= b;
a += b;
a %= b;
return a;
}

public static long factorial(int n, long mod) {
long result = 1;
for (int i = 2; i <= n; i++) {
result = result * i % mod;
}
return result % mod;
}

public static long power(long base, long exponent, long mod) {
if (base >= mod) {
base %= mod;
}
if (exponent == 0) {
return 1 % mod;
}
long result = power(base, exponent >> 1, mod);
result = result * result % mod;
if ((exponent & 1) != 0) {
result = result * base % mod;
}
return result;
}

public static long reverse(long number, long modulo) {
extGcd(number, modulo);
return trueMod(_x, modulo);
}

private static long extGcd(long a, long b) {
if (a == 0) {
_x = 0;
_y = 1;
return b;
}
long d = extGcd(b % a, a);
long nx = _y - (b / a) * _x;
_y = _x;
_x = nx;
return d;
}

public static long[] generateReverse(int upTo, long module) {
long[] result = new long[upTo];
if (upTo > 1) {
result[1] = 1;
}
for (int i = 2; i < upTo; i++) {
result[i] = (module - module / i * result[((int) (module % i))] % module) % module;
}
return result;
}

public static long[] generateReverseFactorials(int upTo, long module) {
long[] result = generateReverse(upTo, module);
if (upTo > 0) {
result[0] = 1;
}
for (int i = 1; i < upTo; i++) {
result[i] = result[i] * result[i - 1] % module;
}
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 printLine(long i) {
writer.println(i);
}

}

static class PrimeFastFourierTransform {
private final long MOD;
private final long root;
private final long reverseRoot;
private int rootPower;
private long[] aa;
private long[] bb;

public PrimeFastFourierTransform(long MOD) {
this.MOD = MOD;
rootPower = 1;
int pw = 0;
while ((MOD - 1) % (2 * rootPower) == 0) {
rootPower *= 2;
pw++;
}
for (int i = 2; ; i++) {
if (IntegerUtils.power(i, IntegerUtils.power(2, pw - 1, MOD - 1), MOD) != 1 &&
IntegerUtils.power(i, IntegerUtils.power(2, pw, MOD - 1), MOD) == 1) {
root = i;
reverseRoot = IntegerUtils.reverse(i, MOD);
break;
}
}
}

public void multiply(long[] result, long[] first, long[] second, int length) {
int resultSize = Integer.highestOneBit(result.length - 1) << 2;
resultSize = Math.max(resultSize, 4);
if (aa == null || aa.length < resultSize) {
aa = new long[resultSize];
bb = new long[resultSize];
}
Arrays.fill(aa, 0, resultSize, 0);
Arrays.fill(bb, 0, resultSize, 0);
for (int i = 0; i < length; i++) {
aa[i] = first[i];
}
for (int i = 0; i < length; i++) {
bb[i] = second[i];
}
fft(aa, false, resultSize);
if (first == second) {
System.arraycopy(aa, 0, bb, 0, resultSize);
} else {
fft(bb, false, resultSize);
}
for (int i = 0; i < resultSize; i++) {
aa[i] *= bb[i];
aa[i] %= MOD;
}
fft(aa, true, resultSize);
for (int i = 0; i < result.length; i++) {
result[i] = aa[i] % MOD;
}

}

public void power(long[] result, long[] arg, long exponent) {
int resultSize = Integer.highestOneBit(result.length - 1) << 2;
resultSize = Math.max(resultSize, 4);
if (aa == null || aa.length < resultSize) {
aa = new long[resultSize];
bb = new long[resultSize];
}
Arrays.fill(aa, 0, resultSize, 0);
for (int i = 0; i < result.length; i++) {
aa[i] = arg[i];
}
fft(aa, false, resultSize);
for (int i = 0; i < resultSize; i++) {
aa[i] = IntegerUtils.power(aa[i], exponent, MOD);
}
fft(aa, true, resultSize);
long delta = IntegerUtils.reverse(IntegerUtils.power(resultSize, exponent - 2, MOD), MOD);
for (int i = 0; i < resultSize; i++) {
aa[i] = aa[i] * delta % MOD;
}
for (int i = 0; i < result.length; i++) {
result[i] = aa[i] % MOD;
}
}

private void fft(long[] array, boolean invert, int size) {
for (int i = 1, j = 0; i < size; ++i) {
int bit = size >> 1;
for (; j >= bit; bit >>= 1) {
j -= bit;
}
j += bit;
if (i < j) {
long temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}

for (int len = 2; len <= size; len <<= 1) {
long wlen = invert ? reverseRoot : root;
for (int i = len; i < rootPower; i <<= 1) {
wlen = wlen * wlen % MOD;
}
int half = len >> 1;
for (int i = 0; i < size; i += len) {
long w = 1;
for (int j = 0; j < half; ++j) {
long u = array[i + j], v = array[i + j + half] * w % MOD;
array[i + j] = u + v < MOD ? u + v : u + v - MOD;
array[i + j + half] = u - v >= 0 ? u - v : u - v + MOD;
w = w * wlen % MOD;
}
}
}
if (invert) {
long reverseSize = IntegerUtils.reverse(size, MOD);
for (int i = 0; i < size; ++i) {
array[i] = array[i] * reverseSize % MOD;
}
}
}

}

static class MiscUtils {
public static final int MODF = 998244353;

}
}

```

#### Submission Info

Submission Time 2019-07-14 23:39:46+0900 F - Two Histograms Egor Java8 (OpenJDK 1.8.0) 0 11876 Byte RE 2109 ms 311788 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1800
Status
 AC × 3 TLE × 1
 AC × 8 WA × 1 TLE × 8 RE × 3
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt, s4.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt TLE 2109 ms 64180 KB
02.txt TLE 2105 ms 68116 KB
03.txt TLE 2108 ms 75820 KB
04.txt TLE 2109 ms 74036 KB
05.txt AC 69 ms 18004 KB
06.txt RE 1314 ms 311788 KB
07.txt RE 497 ms 280788 KB
08.txt AC 69 ms 16724 KB
09.txt AC 69 ms 17748 KB
10.txt RE 503 ms 284116 KB
11.txt AC 70 ms 18644 KB
12.txt WA 252 ms 19784 KB
13.txt TLE 2105 ms 65100 KB
14.txt TLE 2104 ms 48228 KB
15.txt AC 70 ms 20564 KB
16.txt TLE 2105 ms 62024 KB
s1.txt AC 71 ms 20308 KB
s2.txt AC 70 ms 21460 KB
s3.txt AC 71 ms 18516 KB
s4.txt TLE 2105 ms 63560 KB