Advertisement
999ms

Untitled

Apr 21st, 2019
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.41 KB | None | 0 0
  1. import java.io.*;
  2. import java.lang.reflect.Array;
  3. import java.util.*;
  4.  
  5. public class Main {
  6.  
  7.     String fileName = "";
  8.  
  9.     boolean checkBit(int val, int bit) {
  10.         return ((val >> bit) & 1) == 1;
  11.     }
  12.  
  13.     long mod;
  14.  
  15.     long fastPow(long a, long p) {
  16.         long ans = 1;
  17.         while (p > 0) {
  18.             if ((p & 1) > 0) {
  19.                 ans *= a;
  20.                 ans %= mod;
  21.             }
  22.             a *= a;
  23.             a %= mod;
  24.             p /= 2;
  25.         }
  26.         return ans;
  27.     }
  28.  
  29.     class TaskB {
  30.         int mask;
  31.         int ways;
  32.  
  33.         TaskB(int mask, int ways) {
  34.             this.mask = mask;
  35.             this.ways = ways;
  36.         }
  37.     }
  38.  
  39.     ArrayList<Integer> g[];
  40.     ArrayList<TaskB> list;
  41.  
  42.     void solve() throws IOException {
  43.         int n = readInt();
  44.         mod = readInt();
  45.  
  46.         long[] fact = new long[101];
  47.         fact[0] = 1;
  48.         for (int i = 1; i <= 100; i++) {
  49.             fact[i] = fact[i - 1] * i % mod;
  50.         }
  51.         boolean[] primes = new boolean[101];
  52.         Arrays.fill(primes, true);
  53.         for (int i = 2; i <= 100; i++) {
  54.             if (primes[i]) {
  55.                 for (int j = 2; j * i <= 100; j++) {
  56.                     primes[i * j] = false;
  57.                 }
  58.             }
  59.         }
  60.         ArrayList<Integer> p = new ArrayList<>();
  61.         for (int i = 1; i <= n; i++) {
  62.             if (primes[i]) {
  63.                 p.add(i);
  64.             }
  65.         }
  66.         int[][] dp = new int[1 << p.size()][2];
  67.         int[] ans = new int[p.size()];
  68.         int[] masks = new int[n + 1];
  69.         for (int i = 1; i <= n; i++) {
  70.             for (int j = (i == 1 ? 0 : 1); j < p.size(); j++) {
  71.                 if (i % p.get(j) == 0) {
  72.                     masks[i] |= (1 << j);
  73.                 }
  74.             }
  75.         }
  76.  
  77.         ArrayDeque<Integer>[] queue = new ArrayDeque[2];
  78.         for (int i = 0; i < 2; i++) {
  79.             queue[i] = new ArrayDeque<>();
  80.         }
  81.         queue[0].add(0);
  82.         dp[0][0] = 1;
  83.         byte[] lastActiveLvl = new byte[1 << p.size()];
  84.         Arrays.fill(lastActiveLvl, (byte) (-1));
  85.  
  86.         for (byte lvl = 0; lvl <= p.size(); lvl++) {
  87.             while (!queue[lvl & 1].isEmpty()) {
  88.                 int currMask = queue[lvl & 1].poll();
  89.                 for (int nextValue = n; nextValue >= 1; nextValue--) {
  90.                     if ((currMask & masks[nextValue]) == 0) {
  91.                         int nextMask = (currMask | masks[nextValue]);
  92.                         if (lastActiveLvl[nextMask] != lvl) {
  93.                             lastActiveLvl[nextMask] = lvl;
  94.                             dp[nextMask][(lvl + 1)&1] = dp[currMask][lvl&1];
  95.                             ans[lvl] += dp[currMask][lvl&1];
  96.                             queue[(lvl + 1) & 1].add(nextMask);
  97.                             if (ans[lvl] >= mod) ans[lvl] -= mod;
  98.                         } else {
  99.                             dp[nextMask][1 & (lvl + 1)] += dp[currMask][lvl & 1];
  100.                             if (dp[nextMask][1 & (lvl + 1)] >= mod) dp[nextMask][(lvl + 1)&1] -= mod;
  101.                             ans[lvl] += dp[currMask][lvl & 1];
  102.                             if (ans[lvl] >= mod) ans[lvl] -= mod;
  103.                         }
  104.                     }
  105.                 }
  106.             }
  107.         }
  108.  
  109.         for (int lvl = 0; lvl < p.size(); lvl++) {
  110.             out.print(((ans[lvl]) % mod) * fact[n - lvl - 1] % mod + "\n");
  111.         }
  112.  
  113.     }
  114.  
  115.     public static void main(String[] args) throws NumberFormatException, IOException {
  116.         new Main().run();
  117.     }
  118.  
  119.     void run() throws NumberFormatException, IOException {
  120.         solve();
  121.         out.close();
  122.     }
  123.  
  124.     BufferedReader in;
  125.     PrintWriter out;
  126.  
  127.     StringTokenizer tok;
  128.     String delim = " ";
  129.  
  130.     Main() throws FileNotFoundException {
  131.         if (fileName.isEmpty()) {
  132.             in = new BufferedReader(new InputStreamReader(System.in));
  133.             out = new PrintWriter(System.out);
  134.         } else {
  135.             in = new BufferedReader(new FileReader(fileName + ".in"));
  136.             out = new PrintWriter(fileName + ".out");
  137.         }
  138.         tok = new StringTokenizer("");
  139.     }
  140.  
  141.     String readLine() throws IOException {
  142.         return in.readLine();
  143.     }
  144.  
  145.     String readString() throws IOException {
  146.         while (!tok.hasMoreTokens()) {
  147.             String nextLine = readLine();
  148.             if (null == nextLine) {
  149.                 return null;
  150.             }
  151.  
  152.             tok = new StringTokenizer(nextLine);
  153.         }
  154.         return tok.nextToken(delim);
  155.     }
  156.  
  157.     int readInt() throws NumberFormatException, IOException {
  158.         return Integer.parseInt(readString());
  159.     }
  160.  
  161.     long readLong() throws NumberFormatException, IOException {
  162.         return Long.parseLong(readString());
  163.     }
  164.  
  165.     int[] readIntArray(int n) throws NumberFormatException, IOException {
  166.         int[] a = new int[n];
  167.         for (int i = 0; i < n; ++i) {
  168.             a[i] = readInt();
  169.         }
  170.         return a;
  171.     }
  172.  
  173.     double readDouble() throws NumberFormatException, IOException {
  174.         return Double.parseDouble(readString());
  175.     }
  176.  
  177.     void sortIntArray(int[] a) {
  178.         Integer[] arr = new Integer[a.length];
  179.         for (int i = 0; i < a.length; i++) {
  180.             arr[i] = a[i];
  181.         }
  182.         Arrays.sort(arr);
  183.         for (int i = 0; i < a.length; i++) {
  184.             a[i] = arr[i];
  185.         }
  186.     }
  187. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement