题面
分析
单源最短Hamilton路径的状压dp模板题。
\(dp[i][j]\)表示终点为\(j\),经过的点集状态为\(i\)的方案数。假设状态由\(k\)转移到\(j\)。当前计算\(dp[i][j]\),那么i->j的方案数等于\(i\)到达所有与\(j\)相连且不经过j的k点的方案数,即i->k->j。
因为1与任意数互质,故答案为所有非起点的满状态(全部点可达)之和,即
\[\sum_{i=1}^N dp[(1<<N)-1][i] \]Code
#include<iostream>
#include<cstdio>
#define ll long long
const int maxn = 21;
ll ans;
bool link[maxn][maxn];
ll dp[1 << maxn][maxn];
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
void init() {
for (int i = 0; i < 21; i++)
for (int j = 0; j < 21; j++)
if (gcd(i + 1, j + 1) == 1) link[i][j] = link[j][i] = 1;
}
int main() {
init();
dp[1][0] = 1;//s->s方案数为1
for (int state = 0; state < (1 << maxn); state++)
for (int j = 0; j < maxn; j++)//枚举终点i->k->j
if (state >> j & 1)
for (int k = 0; k < maxn; k++)
if ((state - (1 << j)) >> k & 1 && link[j][k])
dp[state][j] += dp[state - (1 << j)][k];
for (int i = 1; i < maxn; i++)
ans += dp[(1 << maxn) - 1][i];
printf("%lld", ans);
}
标签:int,ll,状压,蓝桥,state,maxn,2021,dp
From: https://www.cnblogs.com/MrWangnacl/p/16989745.html