【蓝桥杯】回路计数

116 阅读 0 评论 77 点赞

我是靠谱客的博主刻苦棒球，最近开发中收集的这篇文章主要介绍【蓝桥杯】回路计数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述
蓝桥学院由 2121 栋教学楼组成，教学楼编号 11 到 2121。对于两栋教学楼 aa 和 bb，当 aa 和 bb 互质时，aa 和 bb 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个 ii，小蓝在两个访问方法中访问完教学楼 ii 后访问了不同的教学楼。

运行限制
最大运行时间：1s
最大运行内存: 128M

状压DP
构造状态 $f [i] [j]$ 表示以第 $i$ 栋建筑为结尾，状态为 $j$ 的方案数
状态 $j$ 用一个 $21$ 位的二进制来表示某一栋教学楼是否被走过
考虑 $f [i] [j]$ 从哪些状态转移过来，显然是于 $i$ 相邻的边且 $i$ 没有被走过的状态

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long f[25][1 << 22];
int map[25][25];

int gcd(int a,int b){
    while(a % b != 0){
        int m = a % b;
        a = b;
        b = m;
    }
    return b;
}

int main(){
    int n = 21;
    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++)
            if(gcd(i,j) == 1){
                map[i][j] = 1;
                map[j][i] = 1;
            }
    memset(f,0,sizeof(f));
    f[1][1 << (n - 1)] = 1;
    int start = 1 << (n - 1);
    int last = (1 << n) - 1;
    for(int state = start; state <= last; state ++)
        for(int i = 1; i <= n; i ++){
            if((state >> n - i) & 1 == 0) continue;
            int pre_state = state & (~(1 << (n - i)));
            for(int j = 1; j <= n; j ++)
                if(map[j][i] && (pre_state >> (n - j)) & 1) f[i][state] += f[j][pre_state];
        }
    long long ans = 0;
    for(int i = 1; i <= n; i ++)
        ans += f[i][last];
    cout<<ans;
    return 0;
}