Advertisement
999ms

Task B

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