Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.lang.reflect.Array;
- import java.util.*;
- public class Main {
- String fileName = "";
- boolean checkBit(int val, int bit) {
- return ((val >> bit) & 1) == 1;
- }
- long mod;
- long fastPow(long a, long p) {
- long ans = 1;
- while (p > 0) {
- if ((p & 1) > 0) {
- ans *= a;
- ans %= mod;
- }
- a *= a;
- a %= mod;
- p /= 2;
- }
- return ans;
- }
- class TaskB {
- int mask;
- int ways;
- TaskB(int mask, int ways) {
- this.mask = mask;
- this.ways = ways;
- }
- }
- ArrayList<Integer> g[];
- ArrayList<TaskB> list;
- void solve() throws IOException {
- int n = readInt();
- mod = readInt();
- long[] fact = new long[101];
- fact[0] = 1;
- for (int i = 1; i <= 100; i++) {
- fact[i] = fact[i - 1] * i % mod;
- }
- boolean[] primes = new boolean[101];
- Arrays.fill(primes, true);
- for (int i = 2; i <= 100; i++) {
- if (primes[i]) {
- for (int j = 2; j * i <= 100; j++) {
- primes[i * j] = false;
- }
- }
- }
- ArrayList<Integer> p = new ArrayList<>();
- for (int i = 1; i <= n; i++) {
- if (primes[i]) {
- p.add(i);
- }
- }
- int[][] dp = new int[1 << p.size()][2];
- int[] ans = new int[p.size()];
- int[] masks = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- for (int j = (i == 1 ? 0 : 1); j < p.size(); j++) {
- if (i % p.get(j) == 0) {
- masks[i] |= (1 << j);
- }
- }
- }
- ArrayDeque<Integer>[] queue = new ArrayDeque[2];
- for (int i = 0; i < 2; i++) {
- queue[i] = new ArrayDeque<>();
- }
- queue[0].add(0);
- dp[0][0] = 1;
- byte[] lastActiveLvl = new byte[1 << p.size()];
- Arrays.fill(lastActiveLvl, (byte) (-1));
- for (byte lvl = 0; lvl <= p.size(); lvl++) {
- while (!queue[lvl & 1].isEmpty()) {
- int currMask = queue[lvl & 1].poll();
- for (int nextValue = n; nextValue >= 1; nextValue--) {
- if ((currMask & masks[nextValue]) == 0) {
- int nextMask = (currMask | masks[nextValue]);
- if (lastActiveLvl[nextMask] != lvl) {
- lastActiveLvl[nextMask] = lvl;
- dp[nextMask][(lvl + 1)&1] = dp[currMask][lvl&1];
- ans[lvl] += dp[currMask][lvl&1];
- queue[(lvl + 1) & 1].add(nextMask);
- if (ans[lvl] >= mod) ans[lvl] -= mod;
- } else {
- dp[nextMask][1 & (lvl + 1)] += dp[currMask][lvl & 1];
- if (dp[nextMask][1 & (lvl + 1)] >= mod) dp[nextMask][(lvl + 1)&1] -= mod;
- ans[lvl] += dp[currMask][lvl & 1];
- if (ans[lvl] >= mod) ans[lvl] -= mod;
- }
- }
- }
- }
- }
- for (int lvl = 0; lvl < p.size(); lvl++) {
- out.print(((ans[lvl]) % mod) * fact[n - lvl - 1] % 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