感觉状态极差啊，今天居然爆零了
主要是以下原因：
1.又是T1看错题肝了两个小时，发现题意理解错误瞬间心态爆炸
2.T2交错了文件名
3.T3暴力子任务和正解（假的）混在一起，输出了两个答案
都想为自己刷个赞，调不出代码是水平不够，但是这样真的让人无话可说，幸好这只是模拟赛
T1：
题意：给出一个集合，要求把这个集合分成两部分，使得一个集合中的任意一个元素都与对面集合的全部元素都互质
我不知道我为什么会写炸这样的傻X题。。。
显然暴力就是$O(n^2)$枚举，暴力判断gcd是否为1，如果不为1说明要放在一个集合里，并查集维护一下联通块的个数就好，答案就是$s^{联通块的个数}-2$（-2是因为不能出现空集）
考虑优化这个过程
我们枚举质因数，用类似邻接链表的方法把它的倍数连在一起，这样就形成了若干联通块，dfs计算联通块的个数统计答案就好了
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxa=1e6+10,mod=1e9+7;
int t,n,last[maxa],ans;
bool vis[maxn];
vector<int> g[maxn];
int pcnt,prime[maxa],minp[maxa];
bool prm[maxa];
inline void init(){
for(int i=2;i<maxa;++i){
if(!prm[i]){
prime[++pcnt]=i;
minp[i]=i;
}
for(int j=1;j<=pcnt&&i*prime[j]<maxa;++j){
prm[i*prime[j]]=true;
minp[i*prime[j]]=prime[j];
if(i%prime[j]==0)
break;
}
}
}
void dfs(int pos){
vis[pos]=true;
for(int i=0;i<g[pos].size();++i)
if(!vis[g[pos][i]])
dfs(g[pos][i]);
}
int main(){
// freopen("x.in","r",stdin);
// freopen("x.out","w",stdout);
init();
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=pcnt;++i)
last[prime[i]]=0;
for(int i=1,x;i<=n;++i){
vis[i]=false;
g[i].clear();
scanf("%d",&x);
while(x>1){
int fac=minp[x];
while(x%fac==0)
x/=fac;
if(last[fac]){
g[i].push_back(last[fac]);
g[last[fac]].push_back(i);
}
last[fac]=i;
}
}
ans=1;
for(int i=1;i<=n;++i)
if(!vis[i])
ans=ans*2%mod,dfs(i);
printf("%d
",(ans+mod-2)%mod);
}
return 0;
}
T2：
老实说现在让我再写一次我不会写，因为是看标程才勉强理解的（神奇的bitset啊）
据出题人大大说，暴力是这么写的，dp[i][j][bit]表示从i到j是否存在一条表示可以表示为bit的边。（注意到前导0，办法和昨天那题是一样的，或上1<<len就好，len是路径的长度）
然后我们要优化这个暴力，出题人大大还说了，meet in the middle，我们长度为d的路径拆分成d2=d/2,d1=d-d2两段，注意到d1>=d2
然后我们用bitset搞一波就好
具体看代码注释吧
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<bitset>
using namespace std;
const int N=90+15;
const int maxn=1<<20/2+1;
int n,m,d;
bitset <N> g0[N],g1[N],dp[maxn],f[maxn];
inline int read()
{
char ch=getchar();
int s=0,f=1;
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*f;
}
int main()
{
// freopen("y.in","r",stdin);
// freopen("y.out","w",stdout);
n=read();m=read();d=read();
for (int i=1,u,v,c;i<=m;i++)
{
u=read();v=read();c=read();
if (c) {g1[u][v]=g1[v][u]=true;}
else {g0[u][v]=g0[v][u]=true;}
}
int d2=d/2,d1=d-d2;
for (int u=n;u>=1;u--)
{
for (int i=0;i<maxn;i++) dp[i].reset();
dp[1][u]=true;//以u为结尾状态是否存在，最开始的1是为了避免前导0
for (int x=1;x<1<<d1;x++)
for (int y=1;y<=n;y++)
if (dp[x][y])
{
dp[x<<1]|=g0[y];
dp[x<<1|1]|=g1[y];
}
for (int x=0;x<1<<d1;x++)//一个由u拓展的状态以任何一个结尾都说明以u开头的这个状态是存在的
f[x][u]=dp[1<<d1|x].any();//f数组是以u为开头的状态是否存在
}
int ans=0;
for (int i=0;i<1<<d1;i++)
for (int j=0;j<1<<d2;j++)//最后的dp数组状态都是由1为开头拓展而来的
if ((dp[1<<d2|j]&f[i]).any()) ans++;//有任意一个接上就可以累计答案
printf("%d
",ans);
return 0;
}
T3：
待填