P2150 Solution
首先两人选的数两两互质相当于两人的质因数集合无交。
先考虑 \(n\le 30\)：由于 \(30\) 内的质因只有 \(10\) 个，我们考虑状压 \(dp\)。
设 \(dp_{i,S1,S2}\) 表示考虑到第 \(i\) 个数，G 选了质因数集合 \(S1\),W 选了质因数集合 \(S2\) 的方案数。
刷表转移：
\[dp_{i,S1\cup k,S2}\gets dp_{i,S1\cup k,S2}+dp_{i-1,S1,S2}(k\cap S2=\varnothing) \]\[dp_{i,S1,S2\cup k}\gets dp_{i,S1,S2\cup k}+dp_{i-1,S1,S2}(k\cap S1=\varnothing) \]其中 \(k\) 表示第 \(i\) 个数的质因数集合。
这里可以滚掉第一维，复杂度 \(\mathcal O(2^{20}n)\)。
接下来是 \(n\le 500\)：
我们发现一个数 \(x\) 最多有一个 \(>\sqrt x\) 的大质因子（可能没有），那么 \(\le 500\) 的数就最多有一个 \(>22\) 的大质因子。考虑一开始先预处理出每个数的大质因子，剩下的小质因子状压处理。
剩下的小质因子只剩下了 \(8\) 个，也就是说我们的状态数只剩下了 \(2^8\)！
我们将所有数按照它的大质因子排序，这样相同大质因子的数就会在一个连续段中，这些数只能由一个人取。我们在每个连续段内进行dp：
设 \(dpG_{i,S1,S2}\) 考虑到第 \(i\) 个数，\(i\) 所在连续段的数由 G 取，G 选了小质因数集合 \(S1\),W 选了小质因数集合 \(S2\) 的方案数。\(dpW_{i,S1,S2}\) 同理，\(dp_{i,S1,S2}\) 的定义不变。
转移：
\[dpG_{i,S1\cup k,S2}\gets dpG_{i,S1\cup k,S2}+dpG_{i-1,S1,S2}(k\cap S2=\varnothing) \]\[dpW_{i,S1,S2\cup k}\gets dpW_{i,S1,S2\cup k}+dpW_{i-1,S1,S2}(k\cap S1=\varnothing) \]在每个连续段开头，我们把 \(dpG,dpW\) 都赋值为 \(dp\)；在每个连续段结尾，我们需要由 \(dpG,dpW\) 处理出 \(dp\)：
\[dp_{r,S1,S2}=dpG_{r,S1,S2}+dpW_{r,S1,S2}-dp_{l-1,S1,S2} \]其中 \(l,r\) 分别表示连续段的左右端点。减掉最后一项是因为两人都不选大质因子的情况算了两遍。
我们再把第一维都滚掉，最后复杂度就是 \(\mathcal O(2^{16}n)\)。
当然我们这里优化一下：由于 \(S1\cap S2=\varnothing\)，我们在枚举 \(S1,S2\) 的时候可以先枚举 \(S1\)，再枚举 \(S1\) 的补集的子集。这样复杂度是 \(\mathcal O(3^8n)\)的。
代码
\(\mathcal O(2^{16}n)\)
using namespace std;
const int N = 1 << 8 | 7;
const int inf = ~0u >> 2;
int pi[] = {0 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19};
struct data
{
int val,s;
int bf; // biggest factor
friend bool operator < (data a , data b)
{return a.bf < b.bf;}
void split()
{
int x = val;
for(int i = 1;i <= 8;i++)
if(x % pi[i] == 0)
{
s |= 1 << i - 1;
while(x % pi[i] == 0)
x /= pi[i];
}
if(x != 1)
bf = x;
}
}a[5005];
int n,p;
int dp[N][N];
int dpG[N][N],dpW[N][N];
int main()
{
cin >> n >> p;
for(int i = 1;i <= n - 1;i++)
a[i].val = i + 1,a[i].split();
sort(a + 1 , a + n);
dp[0][0] = 1;
a[0].bf = a[n].bf = 114514;
for(int i = 1;i <= n - 1;i++)
{
if(a[i].bf != a[i - 1].bf || !a[i].bf)
for(int s1 = 0;s1 < 256;s1++)
for(int s2 = 0;s2 < 256;s2++)
dpG[s1][s2] = dpW[s1][s2] = dp[s1][s2];
for(int s1 = 255;~s1;s1--)
for(int s2 = 255;~s2;s2--)
if( !(s1 & s2) )
{
if( !(s2 & a[i].s) )
dpG[s1 | a[i].s][s2] = ( dpG[s1 | a[i].s][s2] + dpG[s1][s2] ) % p;
if( !(s1 & a[i].s) )
dpW[s1][s2 | a[i].s] = ( dpW[s1][s2 | a[i].s] + dpW[s1][s2] ) % p;
}
if(a[i].bf != a[i + 1].bf || !a[i].bf)
for(int s1 = 0;s1 < 256;s1++)
for(int s2 = 0;s2 < 256;s2++)
dp[s1][s2] = (0ll + dpG[s1][s2] + dpW[s1][s2] - dp[s1][s2] + p) % p;
}
int ans = 0;
for(int s1 = 0;s1 < 256;s1++)
for(int s2 = 0;s2 < 256;s2++)
if( !(s1 & s2) )
ans = ( ans + dp[s1][s2] ) % p;
cout << ans << endl;
return 0;
}
\(\mathcal O(3^8n)\)
using namespace std;
const int N = 1 << 8 | 7;
const int inf = ~0u >> 2;
int pi[] = {0 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19};
struct data
{
int val,s;
int bf; // biggest factor
friend bool operator < (data a , data b)
{return a.bf < b.bf;}
void split()
{
int x = val;
for(int i = 1;i <= 8;i++)
if(x % pi[i] == 0)
{
s |= 1 << i - 1;
while(x % pi[i] == 0)
x /= pi[i];
}
if(x != 1)
bf = x;
}
}a[5005];
int n,p;
int dp[N][N];
int dpG[N][N],dpW[N][N];
int main()
{
cin >> n >> p;
for(int i = 1;i <= n - 1;i++)
a[i].val = i + 1,a[i].split();
sort(a + 1 , a + n);
dp[0][0] = 1;
a[0].bf = a[n].bf = 114514;
for(int i = 1;i <= n - 1;i++)
{
if(a[i].bf != a[i - 1].bf || !a[i].bf)
for(int s1 = 255,t = 0;~s1;s1--,t = ~s1 & 255)
for(int s2 = t;~s2;s2 = s2 ? s2 - 1 & t : -1)
dpG[s1][s2] = dpW[s1][s2] = dp[s1][s2];
for(int s1 = 255,t = 0;~s1;s1--,t = ~s1 & 255)
for(int s2 = t;~s2;s2 = s2 ? s2 - 1 & t : -1)
{
if( !(s2 & a[i].s) )
dpG[s1 | a[i].s][s2] = ( dpG[s1 | a[i].s][s2] + dpG[s1][s2] ) % p;
if( !(s1 & a[i].s) )
dpW[s1][s2 | a[i].s] = ( dpW[s1][s2 | a[i].s] + dpW[s1][s2] ) % p;
}
if(a[i].bf != a[i + 1].bf || !a[i].bf)
for(int s1 = 255,t = 0;~s1;s1--,t = ~s1 & 255)
for(int s2 = t;~s2;s2 = s2 ? s2 - 1 & t : -1)
dp[s1][s2] = (0ll + dpG[s1][s2] + dpW[s1][s2] - dp[s1][s2] + p) % p;
}
int ans = 0;
for(int s1 = 255,t = 0;~s1;s1--,t = ~s1 & 255)
for(int s2 = t;~s2;s2 = s2 ? s2 - 1 & t : -1)
ans = ( ans + dp[s1][s2] ) % p;
cout << ans << endl;
return 0;
}