Description

为了庆祝 NOI 的成功开幕, 主办方为大家准备了一场寿司晚宴. 小 G 和小 W 作为参加 NOI 的选手, 也被邀请参加了寿司晚宴.

在晚宴上, 主办方为大家提供了 \(n - 1\) 种不同的寿司, 编号 \(1, 2, 3, \ldots, n-1\), 其中第 \(i\) 种寿司的美味度为 \(i+1\) (即寿司的美味度为从 \(2\) 到 \(n\)) .

现在小 G 和小 W 希望每人选一些寿司种类来品尝, 他们规定一种品尝方案为不和谐的当且仅当: 小 G 品尝的寿司种类中存在一种美味度为 \(x\) 的寿司, 小 W 品尝的寿司中存在一种 美味度为 \(y\) 的寿司, 而 \(x\) 与 \(y\) 不互质.

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案 (对给定的正整数 \(p\) 取模). 注意一个人可以不吃任何寿司.

Input

输入文件的第 \(1\) 行包含 \(2\) 个正整数 \(n, p\), 中间用单个空格隔开, 表示共有 \(n\) 种寿司, 最终和谐的方案数要对 \(p\) 取模.

Output

输出一行包含 \(1\) 个整数, 表示所求的方案模 \(p\) 的结果.

Sample Input

3 10000

Sample Output

9

Data Range

对于所有的数据, 满足:\(2 \leq n \leq 500, 0 \lt p \leq 10^9\)

Explanation

这道题首先想一下发现可以直接搞出状压 DP 因为本来 \((1, n)\) 以内就没有多少个质数对吧......

但是这样想虽然接近正解但是还是错的.

为什么呢? 因为这样存在状压里面还是会强行 MLE, 因为状态实在太多了.

但是我们发现太大的质数本来就没有多少, 而且可以强行被拆出来单独考虑, 所以我们就不把大质数放在状态里面了, 单独再开一个维度保存.

按照最大的不可以被分解的质因子排一下序, 然后得出来的都是按照最糟糕的那个因子考虑 的元素.

由此, 我们就可以考虑这个大质数到底应该分给谁了.

很显然这个状态压缩可以给满分~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define per(_var,_begin,_end) for(int _var=_begin;_var>=_end;_var--)
using namespace std;
typedef long long lli;
const int maxn = 510, maxm = 1<<8;

struct srtr {
    lli a; // State / binary representation of small primes
    lli p; // Largest (remaining) prime factor
}; bool operator < (srtr a, srtr b) {
    return a.p < b.p;
}

int primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
srtr factor(int x)
{
    int a = 0, x_ = x;
    for (int i = 0; i < 8; i++) {
        int v = primes[i];
        while (x % v == 0) {
            x /= v;
            a |= (1 << i);
        }
    }
    srtr ret; ret.a = a, ret.p = x;
    return ret;
}

int n;
lli modr;
srtr arr[maxn];

lli dp[maxn][maxn][2],
    f[maxn][maxn]; // Practically a buffer

int main(int argc, char** argv)
{
    scanf("%d%lld", &n, &modr);
    // Pre-processing factors of all numbers
    for (int i = 2; i <= n; i++)
        arr[i] = factor(i);
    sort(arr + 2, arr + n + 1);
    // Dynamic programming.
    f[0][0] = 1;
    for (int i = 2; i <= n; i++) {
        // Assigning datum
        if (i == 2 || arr[i].p == 1 || arr[i].p != arr[i-1].p)
            per(j, maxm, 0) per(k, maxm, 0)
                dp[j][k][0] = dp[j][k][1] = f[j][k];
        // Modifying from previous stati
        per(j, maxm, 0) per(k, maxm, 0) {
            if ((arr[i].a & k) == 0) // Can assign to left
                dp[j | arr[i].a][k][0] = (dp[j | arr[i].a][k][0] + dp[j][k][0]) % modr;
            if ((arr[i].a & j) == 0) // Can assign to right
                dp[j][k | arr[i].a][1] = (dp[j][k | arr[i].a][1] + dp[j][k][1]) % modr;
        }
        // Copying to f[][] array
        if (i == n || arr[i].p == 1 || arr[i].p != arr[i+1].p)
            per(j, maxm, 0) per(k, maxm, 0)
                f[j][k] = (dp[j][k][0] + dp[j][k][1] - f[j][k] + modr) % modr;
    }
    // Flush DP results to buffer
    lli res = 0;
    rep(i, 0, maxm) rep(j, 0, maxm)
        if ((i & j) == 0)
            res = (res + f[i][j] + modr) % modr;
    // Output
    printf("%lld\n", res);
    return 0;
}