結果
問題 | No.986 Present |
ユーザー |
|
提出日時 | 2020-02-11 15:24:46 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,620 ms / 2,000 ms |
コード長 | 11,060 bytes |
コンパイル時間 | 4,376 ms |
コンパイル使用メモリ | 90,796 KB |
実行使用メモリ | 86,112 KB |
最終ジャッジ日時 | 2024-10-01 07:55:23 |
合計ジャッジ時間 | 26,941 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
package contest200211;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.Arrays;import java.util.InputMismatchException;import java.util.Queue;public class E3 {InputStream is;PrintWriter out;String INPUT = "";void solve(){int n = ni(), m = ni();long A = pow(2, n, mod);out.print(A + " ");long B = 1;long I = 1;for(long i = 0;i < n;i++) {B = B * (pow(2, n, mod) - pow(2, i, mod) + mod) % mod;}for(int i = 1;i <= n;i++) {I = I * i % mod;}B = B * invl(I, mod) % mod;if(B < 0)B += mod;// long[] h = new long[m-n+2];// h[0] = 1;// for(int i = 0;i <= n;i++) {// long q = pow(2, i, mod);// for(int j = 1;j < h.length;j++) {// h[j] += h[j-1] * q;// h[j] %= mod;// }// }Queue<long[]> q = new ArrayDeque<>();for(int i = 0;i <= n;i++) {q.add(new long[] {1, mod-pow(2, i, mod)});}while(q.size() > 1) {long[] a = q.poll();long[] b = q.poll();q.add(mul(a, b, a.length+b.length-1));}long[] h = Arrays.copyOf(q.poll(), m-n+2);h = inv(h);B = B * h[m-n] % mod;out.print(B + " ");out.println(h[m-n]);}public static int mod = 998244353;public static int G = 3;public static long[] mul(long[] a, long[] b){return Arrays.copyOf(convoluteSimply(a, b, mod, G), a.length+b.length-1);}public static long[] mul(long[] a, long[] b, int lim){return Arrays.copyOf(convoluteSimply(a, b, mod, G), lim);}public static long[] mulnaive(long[] a, long[] b){long[] c = new long[a.length+b.length-1];long big = 8L*mod*mod;for(int i = 0;i < a.length;i++){for(int j = 0;j < b.length;j++){c[i+j] += a[i]*b[j];if(c[i+j] >= big)c[i+j] -= big;}}for(int i = 0;i < c.length;i++)c[i] %= mod;return c;}public static long[] mulnaive(long[] a, long[] b, int lim){long[] c = new long[lim];long big = 8L*mod*mod;for(int i = 0;i < a.length;i++){for(int j = 0;j < b.length && i+j < lim;j++){c[i+j] += a[i]*b[j];if(c[i+j] >= big)c[i+j] -= big;}}for(int i = 0;i < c.length;i++)c[i] %= mod;return c;}public static long[] mul_(long[] a, long k){for(int i = 0;i < a.length;i++)a[i] = a[i] * k % mod;return a;}public static long[] mul(long[] a, long k){a = Arrays.copyOf(a, a.length);for(int i = 0;i < a.length;i++)a[i] = a[i] * k % mod;return a;}public static long[] add(long[] a, long[] b){long[] c = new long[Math.max(a.length, b.length)];for(int i = 0;i < a.length;i++)c[i] += a[i];for(int i = 0;i < b.length;i++)c[i] += b[i];for(int i = 0;i < c.length;i++)if(c[i] >= mod)c[i] -= mod;return c;}public static long[] add(long[] a, long[] b, int lim){long[] c = new long[lim];for(int i = 0;i < a.length && i < lim;i++)c[i] += a[i];for(int i = 0;i < b.length && i < lim;i++)c[i] += b[i];for(int i = 0;i < c.length;i++)if(c[i] >= mod)c[i] -= mod;return c;}public static long[] sub(long[] a, long[] b){long[] c = new long[Math.max(a.length, b.length)];for(int i = 0;i < a.length;i++)c[i] += a[i];for(int i = 0;i < b.length;i++)c[i] -= b[i];for(int i = 0;i < c.length;i++)if(c[i] < 0)c[i] += mod;return c;}public static long[] sub(long[] a, long[] b, int lim){long[] c = new long[lim];for(int i = 0;i < a.length && i < lim;i++)c[i] += a[i];for(int i = 0;i < b.length && i < lim;i++)c[i] -= b[i];for(int i = 0;i < c.length;i++)if(c[i] < 0)c[i] += mod;return c;}// F_{t+1}(x) = -F_t(x)^2*P(x) + 2F_t(x)// if want p-destructive, comment out flipping p just before returning.public static long[] inv(long[] p){int n = p.length;long[] f = {invl(p[0], mod)};for(int i = 0;i < p.length;i++){if(p[i] == 0)continue;p[i] = mod-p[i];}for(int i = 1;i < 2*n;i*=2){long[] f2 = mul(f, f, Math.min(n, 2*i));long[] f2p = mul(f2, Arrays.copyOf(p, i), Math.min(n, 2*i));for(int j = 0;j < f.length;j++){f2p[j] += 2L*f[j];if(f2p[j] >= mod)f2p[j] -= mod;if(f2p[j] >= mod)f2p[j] -= mod;}f = f2p;}for(int i = 0;i < p.length;i++){if(p[i] == 0)continue;p[i] = mod-p[i];}return f;}public static final int[] NTTPrimes = {1053818881, 1051721729, 1045430273, 1012924417, 1007681537, 1004535809, 998244353, 985661441, 976224257,975175681};public static final int[] NTTPrimitiveRoots = {7, 6, 3, 5, 3, 3, 3, 3, 3, 17};// public static final int[] NTTPrimes = {1012924417, 1004535809, 998244353, 985661441, 975175681, 962592769, 950009857, 943718401, 935329793,924844033};// public static final int[] NTTPrimitiveRoots = {5, 3, 3, 3, 17, 7, 7, 7, 3, 5};public static long[] convoluteSimply(long[] a, long[] b, int P, int g){int m = Math.max(2, Integer.highestOneBit(Math.max(a.length, b.length)-1)<<2);long[] fa = nttmb(a, m, false, P, g);long[] fb = a == b ? fa : nttmb(b, m, false, P, g);for(int i = 0;i < m;i++){fa[i] = fa[i]*fb[i]%P;}return nttmb(fa, m, true, P, g);}// static int[] wws = new int[270000]; // outer faster// Modifed Montgomery + Barrettprivate static long[] nttmb(long[] src, int n, boolean inverse, int P, int g){long[] dst = Arrays.copyOf(src, n);int h = Integer.numberOfTrailingZeros(n);long K = Integer.highestOneBit(P)<<1;int H = Long.numberOfTrailingZeros(K)*2;long M = K*K/P;int[] wws = new int[1<<h-1];long dw = inverse ? pow(g, P-1-(P-1)/n, P) : pow(g, (P-1)/n, P);long w = (1L<<32)%P;for(int k = 0;k < 1<<h-1;k++){wws[k] = (int)w;w = modh(w*dw, M, H, P);}long J = invl(P, 1L<<32);for(int i = 0;i < h;i++){for(int j = 0;j < 1<<i;j++){for(int k = 0, s = j<<h-i, t = s|1<<h-i-1;k < 1<<h-i-1;k++,s++,t++){long u = (dst[s] - dst[t] + 2*P)*wws[k];dst[s] += dst[t];if(dst[s] >= 2*P)dst[s] -= 2*P;// long Q = (u&(1L<<32)-1)*J&(1L<<32)-1;long Q = (u<<32)*J>>>32;dst[t] = (u>>>32)-(Q*P>>>32)+P;}}if(i < h-1){for(int k = 0;k < 1<<h-i-2;k++)wws[k] = wws[k*2];}}for(int i = 0;i < n;i++){if(dst[i] >= P)dst[i] -= P;}for(int i = 0;i < n;i++){int rev = Integer.reverse(i)>>>-h;if(i < rev){long d = dst[i]; dst[i] = dst[rev]; dst[rev] = d;}}if(inverse){long in = invl(n, P);for(int i = 0;i < n;i++)dst[i] = modh(dst[i]*in, M, H, P);}return dst;}static final long mask = (1L<<31)-1;public static long modh(long a, long M, int h, int mod){long r = a-((M*(a&mask)>>>31)+M*(a>>>31)>>>h-31)*mod;return r < mod ? r : r-mod;}public static int[][] enumFIF(int n, int mod) {int[] f = new int[n + 1];int[] invf = new int[n + 1];f[0] = 1;for (int i = 1; i <= n; i++) {f[i] = (int) ((long) f[i - 1] * i % mod);}long a = f[n];long b = mod;long p = 1, q = 0;while (b > 0) {long c = a / b;long d;d = a;a = b;b = d % b;d = p;p = q;q = d - c * q;}invf[n] = (int) (p < 0 ? p + mod : p);for (int i = n - 1; i >= 0; i--) {invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);}return new int[][] { f, invf };}public static long C(int n, int r, int mod, int[][] fif) {if (n < 0 || r < 0 || r > n)return 0;return (long) fif[0][n] * fif[1][r] % mod * fif[1][n - r] % mod;}public static long invl(long a, long mod) {long b = mod;long p = 1, q = 0;while (b > 0) {long c = a / b;long d;d = a;a = b;b = d % b;d = p;p = q;q = d - c * q;}return p < 0 ? p + mod : p;}int rank(int[] a){int n = a.length;for(int i = 0;i < n;i++) {int[] b = new int[n-1];int p = 0;for(int j = 0;j < n;j++) {if(j == i)continue;b[p++] = a[i];}if(span(b) == span(a)) {return rank(b);}}return n;}long span(int[] a){long dp = 1;for(int v : a) {for(int j = 0;j < 64;j++) {if(dp<<~j<0) {dp |= 1L<<(j^v);}}}return dp;}public static long pow(long a, long n, long mod) {// a %= mod;long ret = 1;int x = 63 - Long.numberOfLeadingZeros(n);for (; x >= 0; x--) {ret = ret * ret % mod;if (n << 63 - x < 0)ret = ret * a % mod;}return ret;}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}public static void main(String[] args) throws Exception { new E3().run(); }private byte[] inbuf = new byte[1024];public int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private char[][] nm(int n, int m) {char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m) {int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int ni() { return (int)nl(); }private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}