fork(5) download
copy 
  1. import java.io.*;
  2. import java.math.*;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.     static int MOD = 998244353;
  7.  
  8.     int[][] permutations;
  9.     long[] generators;
  10.  
  11.     void transform(long[] a, int oper) {
  12.         int n = a.length;
  13.         int k = 31 - Integer.numberOfLeadingZeros(n);
  14.         long[] backup = new long[n];
  15.         for (int i = 0; i < n; ++ i) {
  16.             backup[i] = a[permutations[k][i]];
  17.         }
  18.         for (int i = 0; i < n; ++ i) {
  19.             a[i] = backup[i];
  20.         }
  21.         for (int d = 0; 1 << d < n; ++ d) {
  22.             int m = 1 << d, m2 = m << 1;
  23.             long g = generators[d + 1];
  24.             if (oper == -1) {
  25.                 g = inverse(g);
  26.             }
  27.             for (int i = 0; i < n; i += m2) {
  28.                 long unit = 1;
  29.                 for (int j = 0; j < m; ++ j) {
  30.                     long p1 = a[i + j + m];
  31.                     long p2 = a[i + j];
  32.                     long t = unit * p1 % MOD;
  33.                     p1 = p2 + MOD - t;
  34.                     if (p1 >= MOD) {
  35.                         p1 -= MOD;
  36.                     }
  37.                     p2 += t;
  38.                     if (p2 >= MOD) {
  39.                         p2 -= MOD;
  40.                     }
  41.                     unit = unit * g % MOD;
  42.                     a[i + j + m] = p1;
  43.                     a[i + j] = p2;
  44.                 }
  45.             }
  46.         }
  47.     }
  48.  
  49.     long[] weights, ways;
  50.     long[][] buffers;
  51.  
  52.     long[] copyOf(long[] array, int size, int actualSize) {
  53.         long[] newArray = new long[actualSize];
  54.         for (int i = 0; i < size; ++ i) {
  55.             newArray[i] = array[i];
  56.         }
  57.         return newArray;
  58.     }
  59.  
  60.     void solve(int l, int r) {
  61.         if (r - l > 1) {
  62.             int m = l + r >> 1;
  63.             solve(l, m);
  64.             long[] newWays = new long[r - l << 1];
  65.             for (int i = l; i < m; ++ i) {
  66.                 newWays[i - l] = ways[i];
  67.             }
  68.             transform(newWays, 1);
  69.             long[] newWays2 = copyOf(ways, r - l, r - l << 1);
  70.             transform(newWays2, 1);
  71.             int k = 31 - Integer.numberOfLeadingZeros(r - l);
  72.             long[] product = new long[r - l << 1];
  73.             for (int i = 0; i < r - l << 1; ++ i) {
  74.                 product[i] = newWays[i] * newWays2[i] % MOD * buffers[k][i] % MOD;
  75.             }
  76.             transform(product, -1);
  77.             long t = inverse(1 << k + 1);
  78.             for (int i = m; i < r; ++ i) {
  79.                 long p = product[i - l] * t % MOD;
  80.                 if (r - l <= l) {
  81.                     p += p;
  82.                     if (p >= MOD) {
  83.                         p -= MOD;
  84.                     }
  85.                 }
  86.                 ways[i] += p;
  87.                 if (ways[i] >= MOD) {
  88.                     ways[i] -= MOD;
  89.                 }
  90.             }
  91.             solve(m, r);
  92.         }
  93.     }
  94.  
  95.     long inverse(long a) {
  96.         return a == 1 ? 1 : (MOD - MOD / a) * inverse(MOD % a) % MOD;
  97.     }
  98.  
  99.     public void run() {
  100.         generators = new long[20];
  101.         generators[19] = 363395222;
  102.         for (int i = 18; i >= 0; -- i) {
  103.             generators[i] = generators[i + 1] * generators[i + 1] % MOD;
  104.         }
  105.         try {
  106.             int m = reader.nextInt();
  107.             int n = reader.nextInt();
  108.             int k = 32 - Integer.numberOfLeadingZeros(n);
  109.             weights = new long[1 << k];
  110.             for (int i = 0; i < m; ++ i) {
  111.                 int c = reader.nextInt();
  112.                 if (c < 1 << k) {
  113.                     weights[c] = 1;
  114.                 }
  115.             }
  116.             permutations = new int[k + 2][];
  117.             for (int _ = 0; _ <= k + 1; ++ _) {
  118.                 int nn = 1 << _;
  119.                 int[] p = permutations[_] = new int[nn];
  120.                 for (int i = 0; i < nn; ++ i) {
  121.                     p[i] = i;
  122.                 }
  123.                 for (int i = 1, j = 0; i < nn - 1; ++ i) {
  124.                     int s = nn;
  125.                     do {
  126.                         j ^= s >>= 1;
  127.                     } while ((~j & s) > 0);
  128.                     if (i < j) {
  129.                         int t = p[i];
  130.                         p[i] = p[j];
  131.                         p[j] = t;
  132.                     }
  133.                 }
  134.             }
  135.             buffers = new long[k + 1][];
  136.             for (int i = 0; i <= k; ++ i) {
  137.                 buffers[i] = new long[1 << i + 1];
  138.                 for (int j = 0; j < 1 << i; ++ j) {
  139.                     buffers[i][j] = weights[j];
  140.                 }
  141.                 transform(buffers[i], 1);
  142.             }
  143.             ways = new long[1 << k];
  144.             ways[0] = 1;
  145.             solve(0, 1 << k);
  146.             for (int i = 1; i <= n; ++ i) {
  147.                 writer.println(ways[i]);
  148.             }
  149.         } catch (IOException ex) {
  150.         }
  151.         writer.close();
  152.     }
  153.  
  154.     Main() {
  155.         reader = new InputReader(System.in);
  156.         writer = new PrintWriter(System.out);
  157.     }
  158.  
  159.     public static void main(String[] args) {
  160.         new Main().run();
  161.     }
  162.  
  163.     private void debug(Object...os) {
  164.         System.err.println(Arrays.deepToString(os));
  165.     }
  166.  
  167.     private InputReader reader;
  168.     private PrintWriter writer;
  169. }
  170.  
  171. class InputReader {
  172.     InputReader(InputStream in) {
  173.         reader    = new BufferedReader(new InputStreamReader(in));
  174.         //try {
  175.         //    reader    = new BufferedReader(new FileReader(new File("sample.in")));
  176.         //} catch (FileNotFoundException ex) {
  177.         //}
  178.         tokenizer = new StringTokenizer("");
  179.     }
  180.  
  181.     private String next() throws IOException {
  182.         while (!tokenizer.hasMoreTokens()) {
  183.             tokenizer = new StringTokenizer(reader.readLine());
  184.         }
  185.         return tokenizer.nextToken();
  186.     }
  187.  
  188.     public Integer nextInt() throws IOException {
  189.         return Integer.parseInt(next());
  190.     }
  191.  
  192.     private BufferedReader  reader;
  193.     private StringTokenizer tokenizer;
  194. }
  195.  
Runtime error #stdin #stdout #stderr 0.06s 381184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
	at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
	at InputReader.next(Main.java:183)
	at InputReader.nextInt(Main.java:189)
	at Main.run(Main.java:106)
	at Main.main(Main.java:160)
https://ideone.com/BNaVHv
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!