Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.StringTokenizer;
- public class Main {
- String fileName = "";
- long mod;
- boolean checkBit(int value, int bit) {
- return ((value >> bit) & 1) == 1;
- }
- void solve() throws IOException {
- int n = readInt();
- mod = readInt();
- ArrayList<Integer> littlePrimes = new ArrayList<>();
- for (int i = 1; i <= Math.min(50, n); i++) {
- boolean flag = true;
- for (int j = 2; j * j <= i; j++) {
- if (i % j == 0) {
- flag = false;
- break;
- }
- }
- if (flag) {
- littlePrimes.add(i);
- }
- }
- ArrayList<Integer> bigPrimes = new ArrayList<>();
- for (int i = 50; i <= n; i++) {
- boolean flag = true;
- for (int j = 2; j * j <= i; j++) {
- if (i % j == 0) {
- flag = false;
- break;
- }
- }
- if (flag) {
- bigPrimes.add(i);
- }
- }
- ArrayList<Integer> valuesWithoutBigPrimes = new ArrayList<>();
- for (int i = 1; i <= n; i++) {
- boolean flag = true;
- for (int bigPrime : bigPrimes) {
- if (i % bigPrime == 0) {
- flag = false;
- break;
- }
- }
- if (flag)
- valuesWithoutBigPrimes.add(i);
- }
- int maskSize = littlePrimes.size();
- int[] masks = new int[101];
- for (int i = 0; i <= 100; i++) {
- for (int j = (i == 1 ? 0 : 1); j < maskSize; j++) {
- if (i % littlePrimes.get(j) == 0) {
- masks[i] |= (1 << j);
- }
- }
- }
- int[][] dp = new int[2][1 << maskSize];
- dp[0][0] = 1;
- long[] ans = new long[littlePrimes.size() + bigPrimes.size() + 1];
- ans[0] = 1;
- for (int lvl = 0; lvl < maskSize; lvl++) {
- Arrays.fill(dp[(lvl + 1) & 1], 0);
- for (int currentMask = 0; currentMask < (1 << maskSize); currentMask++) {
- for (int nextValue : valuesWithoutBigPrimes) {
- if ((masks[nextValue] & currentMask) == 0) {
- int nextMask = (masks[nextValue] | currentMask);
- dp[(lvl + 1) & 1][nextMask] += dp[lvl & 1][currentMask];
- ans[lvl + 1] += dp[lvl & 1][currentMask];
- if (dp[(lvl + 1) & 1][nextMask] >= mod) dp[(lvl + 1) & 1][nextMask] -= mod;
- if (ans[lvl + 1] >= mod) ans[lvl + 1] -= mod;
- }
- }
- }
- }
- int quantityOfBigPrimes = bigPrimes.size();
- long[] fact = new long[101];
- fact[0] = 1;
- for (int i = 1; i <= 100; i++) {
- fact[i] = fact[i - 1] * i % mod;
- }
- long [][] C = new long[202][202];
- for(int i = 0; i <= n; i++){
- C[i][0] = C[i][i] = 1;
- for(int j = 1; j <= i; j++){
- C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
- }
- }
- for (int i = ans.length - 1; i > 0; i--) {
- for (int j = 1; j <= quantityOfBigPrimes && i - j >= 0; j++) {
- long nextResult = ans[i - j] % mod;
- for (int k = 0; k < j; k++) {
- nextResult *= quantityOfBigPrimes - k;
- nextResult %= mod;
- }
- nextResult *= C[i][j];
- ans[i] += nextResult % mod;
- ans[i] %= mod;
- }
- }
- for (int i = 1; i < ans.length; i++) {
- out.print(fact[n - i] * ans[i] % mod + "\n");
- }
- }
- public static void main(String[] args) throws NumberFormatException, IOException {
- new Main().run();
- }
- void run() throws NumberFormatException, IOException {
- solve();
- out.close();
- }
- BufferedReader in;
- PrintWriter out;
- StringTokenizer tok;
- String delim = " ";
- Main() throws FileNotFoundException {
- if (fileName.isEmpty()) {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- } else {
- in = new BufferedReader(new FileReader(fileName + ".in"));
- out = new PrintWriter(fileName + ".out");
- }
- tok = new StringTokenizer("");
- }
- String readLine() throws IOException {
- return in.readLine();
- }
- String readString() throws IOException {
- while (!tok.hasMoreTokens()) {
- String nextLine = readLine();
- if (null == nextLine) {
- return null;
- }
- tok = new StringTokenizer(nextLine);
- }
- return tok.nextToken(delim);
- }
- int readInt() throws NumberFormatException, IOException {
- return Integer.parseInt(readString());
- }
- long readLong() throws NumberFormatException, IOException {
- return Long.parseLong(readString());
- }
- int[] readIntArray(int n) throws NumberFormatException, IOException {
- int[] a = new int[n];
- for (int i = 0; i < n; ++i) {
- a[i] = readInt();
- }
- return a;
- }
- double readDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(readString());
- }
- void sortIntArray(int[] a) {
- Integer[] arr = new Integer[a.length];
- for (int i = 0; i < a.length; i++) {
- arr[i] = a[i];
- }
- Arrays.sort(arr);
- for (int i = 0; i < a.length; i++) {
- a[i] = arr[i];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement