题面：https://www.cnblogs.com/Juve/articles/11606834.html
x：
并差集，把不能分到两个集合里的元素和并到一起，设连通块个数为cnt，则答案为：$2^cnt-2$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<vector>
#define re register
#define int long long
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+7;
int n,a[MAXN],T,ans,num;
inline int gcd(re int a,re int b){
return b==0?a:gcd(b,a%b);
}
inline int q_pow(re int a,re int b,re int p){
re int res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int fa[MAXN];
inline int find(re int x){
return fa[x]=(fa[x]==x?x:find(fa[x]));
}
vector<int>v[MAXN*10];
int prime[MAXN*10],vis[MAXN*10],tot=0,pri[MAXN*10];
void get_prime(int N){
vis[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]) prime[++tot]=i,pri[i]=tot;
for(int j=1;j<=tot&&i*prime[j]<=N;j++){
vis[i*prime[j]]=1;
if(!(i%prime[j])) break;
}
}
}
inline void divi(re int x,re int pos){
for(re int i=1;i<=tot&&prime[i]*prime[i]<=x;++i){
if(x%prime[i]==0){
v[i].push_back(pos);
while(x%prime[i]==0) x/=prime[i];
}
}
if(x>1) v[pri[x]].push_back(pos);
}
int maxx=0;
signed main(){
get_prime(1e6);
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
ans=num=maxx=0;
for(re int i=1;i<=n;++i){
fa[i]=i;
scanf("%lld",&a[i]);
divi(a[i],i);
maxx=max(maxx,a[i]);
}
for(int i=1;i<=tot&&prime[i]<=maxx;++i){
int N=v[i].size();
if(N==0) continue;
int p=find(v[i][0]);
for(int j=1;j<N;++j){
int q=find(v[i][j]);
if(p!=q) fa[q]=p;
}
v[i].clear();
}
for(int i=1;i<=n;++i){
if(fa[i]==i) ++num;
}
printf("%lld\n",((q_pow(2,num,mod)-2)%mod+mod)%mod);
}
return 0;
}
y：
定义dp：f[i][j][k]表示走了i步，当前点是j，状态为k的一个bool数组，表示是否有该状态存在
为节省空间我们分两部分转移，这样第一维只有$\frac{d}{2}$，第三维只有$2^{\frac{d}{2}}$，
初始状态：$f1[0][1][0]=1,f2[0][i][0]=1(i \in n)$，
我们用连通性转移，最后统计答案是把两个dp数组的状态和在一起
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=95;
int n,m,d,len1,len2,ans=0;
bool cal1[13][MAXN][(1<<13)+5],cal2[13][MAXN][(1<<13)+5];
vector< pair<int,int> >mp[MAXN];
signed main(){
scanf("%d%d%d",&n,&m,&d);
len1=d/2,len2=d-len1;
cal1[0][1][0]=1;
for(int i=1;i<=n;++i) cal2[0][i][0]=1;
for(int i=1,u,v,c;i<=m;++i){
scanf("%d%d%d",&u,&v,&c);
mp[u].push_back(make_pair(v,c));
mp[v].push_back(make_pair(u,c));
}
for(int i=0;i<len1;++i){
int s=(1<<i);
for(int j=0;j<s;++j)
for(int k=1;k<=n;++k){
int N=mp[k].size();
for(int p=0;p<N;++p)
cal1[i+1][mp[k][p].first][(j<<1)+mp[k][p].second]|=cal1[i][k][j];
}
}
for(int i=0;i<len2;++i){
int s=(1<<i);
for(int j=0;j<s;++j)
for(int k=1;k<=n;++k){
int N=mp[k].size();
for(int p=0;p<N;++p)
cal2[i+1][mp[k][p].first][(j<<1)+mp[k][p].second]|=cal2[i][k][j];
}
}
for(int i=0;i<(1<<d);++i)
for(int j=1;j<=n;++j)
if(cal1[len1][j][i>>len2]&&cal2[len2][j][i&((1<<len2)-1)]){
++ans;
break;
}
printf("%d\n",ans);
return 0;
}
z：
全机房没几个作出来的，只能放标算了，去题面里找
原文：https://www.cnblogs.com/Juve/p/11606844.html