鞍山热身赛的题，也是去年多校原题
题目大意：
求n个数的排列中满足相邻两个数互质的排列的数量并取模
当时的思路就是状压dp.. dp[i][state] state用二进制记录某个数是否被取走，i 表示当前序列末尾的数字
然后gcd状态转移
可是n是28，算了一下有几亿个状态。。没法做。。
回来之后找了题解发现可以用数学方法优化，于是搞了半天终于ac了
首先在这个问题中：
两个数是否互质只与他们的质因数有关，所以质因数相同的数是等价的，称作此问题的等价类
质因数找到这些等价类，并得到每个类中的数的数量是很容易的。。
所以只需要对这些等价类进行处理，最后对每个等价类再乘以数量的排列数就可以得到答案了。
不过此时有了数量，就不能用二进制状压了，应该采用哈希来状压。
研究了一会发现哈希状压和二进制状压差不多，只不过把基数从(1+1)^n变成了 (num[1]+1)*(num[2]+1)....也是很好理解的
这些状态处理完，发现对于n=28只有 5600000个状态了，等价类数是17 所以复杂度是17*5600000
一交MLE了。由于取模最大30000，把数组改为short，中间结果int防溢出，不爆内存了。
然后时限30s，以为可以过，结果又T了。。
于是又想了一会，发现17，19，23这三个数与其他任意一个数的互质。。所以他们与 1 是等价的
加了这个优化以后复杂度下降到约为 14*1800000
8800ms AC...
代码如下
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int prime[]={,,,,,,,,};
const int np=;
int state[];
int g[][];
int vi[];
int num[];
int base[];
short dp[][];
bool ok[];
int n,m,ns,st;
void ini()
{
scanf("%d%d",&n,&m);
memset(g,,sizeof(g));
memset(vi,,sizeof(vi));
memset(num,,sizeof(num));
ns=;
state[++ns]=;
num[ns]=;
for(int i=;i<=n;i++)
{
st=;
if(ok[i])
{
num[]++;
continue;
}
for(int j=;j<np;j++)
{
if(i%prime[j]==)
{
st|=(<<j);
}
}
if(!vi[st])
{
state[++ns]=st;
num[ns]=;
vi[st]=ns;
}
else
{
num[vi[st]]++;
}
}
for(int i=;i<=ns;i++)
{
for(int j=;j<=ns;j++)
{
if((state[i]&state[j])==)
g[i][j]=;
}
}
base[]=;
st=;
for(int i=;i<=ns;i++)
{
base[i+]=base[i]*(num[i]+);
st+=base[i]*num[i];
}
}
int getnum(int i,int x)
{
int res=(x%base[i+])/(base[i]);
return res;
}
int getstate(int i,int num)
{
return num*base[i];
}
void dfs(int t,int x)
{
if(t==)
{
dp[x][]=;
return ;
}
if(dp[x][t]!=-)
return;
dp[x][t]=;
for(int i=;i<=ns;i++)
{
if(g[x][i]&&getnum(i,t)>=)
{
dfs(t-base[i],i);
dp[x][t]=((int)dp[x][t]+dp[i][t-base[i]])%m;
}
}
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int T;
scanf("%d",&T);
memset(ok,,sizeof(ok));
ok[]=;
ok[]=;
ok[]=;
while(T--)
{
ini();
memset(dp,-,sizeof(dp));
int ans=;
for(int i=;i<=ns;i++)
{
dfs(st-base[i],i);
ans=((int)ans+dp[i][st-base[i]])%m;
}
for(int i=;i<=ns;i++)
{
while(num[i]>)
{
ans=((int)ans*num[i])%m;
num[i]--;
}
}
printf("%d\n",ans);
}
}