嘟嘟嘟
昨天模拟T2 lba和dukelv都说和这题特别像（然而他俩还是没做出来hhhh），我今天一看，果不其然，大体思路都一样。
但自认为这题比模拟题要难一些，自己也是因为没有彻底理解浪debug了半天，导致费了很长时间。
当(n leqslant 30)时，因为质数只有最多10个，所以可以状压每一个数的质因数，令(dp[i][S_1][S_2])表示前(i)个数中，第一个人选的质因数组合是(S_1)，第二个人是(S_2)时的方案数，然后(O(n * 2 ^ {20}))暴力dp就OK了。
当(n leqslant 500)时，上述做法显然不行，但是小于等于(sqrt{500})的质数最多只有8个，而对于每一个数大于(sqrt{500})的质因数最多只有1个。所以我们可以把拥有同一个大质数的数放到一块儿，然后按这一堆里面只有一个人能选的规则进行dp。
那么上述转移方程就不好用了。所以建两个临时dp方程(f1[i][S_1][S_2], f2[i][S_1][S_2])分别表示只有第一个人和第二个人选的时候的方案数。对于当前的一个数的质因数情况(s)，$$f1[i][S_1 | s][S_2] += f1[i - 1][S_1][S_2] (s & S_2 = 0)$$$$f2[i][S_1][S_2 | s] += f2[i - 1][S_1][S_2] (s & S_1 = 0)$$因为(f_1)和(f_2)只会从内部转移，不会出现对方选的情况，也就符合这些数只能有一个人选的规则了。
然后我们在把这两个数组合并到原来的dp方程上：$$dp[i][S_1][S_2] = f1[m][S_1][S_2] + f1[m][S_1][S_2] - dp[i - 1][S_1][S_2]$$这个有点像树上两点的路径长，要减去lca的贡献。
很多题解都是把两种大质数和小质数何在一块写的，但是因为拿到模拟题我就是分开写的，所以这题我也分开了。
（第一维用滚动数组优化一下）
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 505;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
ll mod;
int n;
In ll inc(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
const int p[8] = {2, 3, 5, 7, 11, 13, 17, 19};
vector<int> v[maxn];
In void solve(int n)
{
int b = 0;
for(int i = 0; i < 8; ++i)
while(n % p[i] == 0) b |= (1 << i), n /= p[i];
v[n].push_back(b);
}
ll dp[2][(1 << 8) + 2][(1 << 8) + 2];
ll f1[2][(1 << 8) + 2][(1 << 8) + 2], f2[2][(1 << 8) + 2][(1 << 8) + 2];
int main()
{
//freopen("ha.out", "w", stdout);
n = read(), mod = read();
for(int i = 2; i <= n; ++i) solve(i);
dp[0][0][0] = 1;
int o = 1;
for(int i = 0; i < (int)v[1].size(); ++i, o ^= 1)
{
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k)
{
dp[o][j][k] = inc(dp[o][j][k], dp[o ^ 1][j][k]);
if(!(v[1][i] & j)) dp[o][j][k | v[1][i]] = inc(dp[o][j][k | v[1][i]], dp[o ^ 1][j][k]);
if(!(v[1][i] & k)) dp[o][j | v[1][i]][k] = inc(dp[o][j | v[1][i]][k], dp[o ^ 1][j][k]);
}
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k) dp[o ^ 1][j][k] = 0;
}
for(int i = 23; i <= n; ++i)
if(v[i].size())
{
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k)
{
f1[o][j][k] = f2[o][j][k] = dp[o ^ 1][j][k];
f1[o ^ 1][j][k] = f2[o ^ 1][j][k] = dp[o ^ 1][j][k];
}
int p = o;
for(int h = 0; h < (int)v[i].size(); ++h, p ^= 1)
{
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k)
{
if(!(v[i][h] & k)) f1[p][j | v[i][h]][k] = inc(f1[p][j | v[i][h]][k], f1[p ^ 1][j][k]);
if(!(v[i][h] & j)) f2[p][j][k | v[i][h]] = inc(f2[p][j][k | v[i][h]], f2[p ^ 1][j][k]);
}
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k)
f1[p ^ 1][j][k] = f1[p][j][k], f2[p ^ 1][j][k] = f2[p][j][k];
}
for(int j = 0; j < (1 << 8); ++j)
for(int k = 0; k < (1 << 8); ++k)
dp[o][j][k] = inc(inc(f1[p ^ 1][j][k], f2[p ^ 1][j][k]), mod - dp[o ^ 1][j][k]);
o ^= 1;
}
ll ans = 0;
for(int i = 0; i < (1 << 8); ++i)
for(int j = 0; j < (1 << 8); ++j)
if(!(i & j)) ans = inc(ans, dp[o ^ 1][i][j]);
write(ans), enter;
return 0;
}