蓝桥杯教学楼
作者:
九折_5
,
2023-05-23 17:54:37
,
所有人可见
,
阅读 63
//思路是用二进制来表示状态,1表示走过的,0表示没有走过
//用二维数组进行dp dp[i][j]表示在i状态下,最后到达的教学楼为j时的方案数
//进行检测:第一,是否i状态中含有j,第二,如果含有j的情况下,便利所有与j相连的点,并且这个点出现在i状态中
//转移方程为dp[i][j]+=dp[i-(1<<j)][k] 表示经过k到达的j
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e4;
int h[N],e[N],ne[N],idx;
int p[22][22];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int gcd(int a,int b){
return b?gcd(b,a%b):b;
}
int dp[1<<22][22];
int main(){
for(int i=1;i<=21;i++){
for(int j=i+1;j<=21;j++){
if(gcd(i,j)==1){
p[i-1][j-1]=1;
p[j-1][i-1]=1;
}
}
}
dp[1][0]=1;
int n=1<<21;
for(int i=1;i<n;i++){
for(int j=0;j<21;j++){
if((i>>j&1)==0){
continue;
}
else{
for(int k=0;k<21;k++){
if(p[k][j]&&(i>>k&1)){
dp[i][j]+=dp[i-(1<<k)][k];
}
}
}
}
}
ll res=0;
for(int i=0;i<21;i++){
res+=dp[n-1][i];
}
cout<<res;
return 0;
}