JZOJ 4250. 【五校联考7day1附加题】路径
题目
Description
A国有 n n n个城市，编号为 1 1 1到 n n n，任意两个城市之间有一条路。shlw闲得没事干想周游A国，及从城市 1 1 1出发，经过且仅经过除城市 1 1 1外的每个城市 1 1 1次（城市 1 1 1两次），最后回到城市 1 1 1。由于shlw很傻，他只愿意走一定长度，多了少了都不干，现在他想知道一共有多少种方案可供选择。
Input
第一行为两个整数
n
，
l
n，l
n，l，分别为城市数和路程总长。
之后
n
n
n行，每行
n
n
n个整数，其中第
i
i
i行第
j
j
j列为
A
i
,
j
A_{i,j}
Ai,j，满足
A
i
,
i
=
0
,
A
i
,
j
=
A
j
,
i
A_{i,i}=0,A_{i,j}=A_{j,i}
Ai,i=0,Ai,j=Aj,i.
Output
输出共一行，为总方案数。
Sample Input
3 6
0 1 3
1 0 2
3 2 0
Sample Output
2
Data Constraint
对于30%，
1
≤
n
≤
10
1≤n≤10
1≤n≤10.
对于另外30%，
1
≤
n
≤
14
，
1
≤
l
≤
30
1≤n≤14，1≤l≤30
1≤n≤14，1≤l≤30.
对于100%，
1
≤
n
≤
14
，
1
≤
A
i
,
j
≤
1
0
8
，
1
≤
l
≤
2
∗
1
0
9
1≤n≤14，1≤A_{i,j}≤10^8，1≤l≤2*10^9
1≤n≤14，1≤Ai,j≤108，1≤l≤2∗109.
悄悄告诉你：数据的答案都很大，反正直接输
0
0
0是没分的，但都在int范围内。
为了降低题目难度，
A
i
,
j
A_{i,j}
Ai,j的种类数不会太多
题解
-
看到数据限制的最后一行我什么都不想说。。。
-
这句话能说明什么我现在都不清楚。。。
-
进入正题，
-
第一档的部分分可以暴力DFS解决，
-
第二档的部分分可以状压DP解决，
-
第三档呢？
-
也能像第二档一样状压DP吗？
-
乍一看好像是可以的，怎么记录路径长度和呢？
-
GG了，此方法不可做——
-
DFS吗？直接这么做似乎最大时间复杂度 O ( n ! ) = 14 ! = 87178291200 ≈ 8.7 ∗ 1 0 10 O(n!)=14!=87178291200≈8.7*10^{10} O(n!)=14!=87178291200≈8.7∗1010，显然超时，
-
有一种神奇的搜索叫做折半搜索！！！
-
顾名思义，把要搜索的东西给折半，
-
主要过程如下：
-
前一半，DFS找出从 1 1 1出发经过的一半的点得到的状态，记录下它和对应的方案数。
-
状态包括到达的点 k k k，经过了点的状态 s s s（状态压缩，不包括 1 1 1），路径长度和 s u m sum sum.
-
这些用哈希表存下来，对于相同的 k , s , s u m k,s,sum k,s,sum，不需重复记录，只要给对应的方案数 + 1 +1 +1.
-
后一半，同样使用DFS找出从 1 1 1出发经过一半的点得到的状态，不需记录，
-
状态包括到达的点 k k k，经过了点的状态 s s s（状态压缩，不包括 1 1 1），路径长度和 s u m sum sum.
-
此时，到哈希表里找到和这个状态对应的（能组成一条完整的路线的）状态，
-
直接查找 ( k , s , s u m ) (k,s,sum) (k,s,sum)？
-
当然不是！（难道两条完全相同的路径能组成一条符合题目条件的回路吗？）
-
第一维，查找的是 k k k，对应走到的当然要是相同的点。
-
第二维，查找的是 2 n − 1 − s − 1 + 2 k − 1 2^n-1-s-1+2^{k-1} 2n−1−s−1+2k−1， 2 n − 1 2^n-1 2n−1是包括每个点的压缩后的状态， − s -s −s是减去了当前经过的点压缩后的状态， − 1 -1 −1是减去点 1 1 1的状态， + 2 k − 1 +2^{k-1} +2k−1是加回当前点的状态。
-
第三维，查找的是 l − s u m l-sum l−sum，因为两半的路径和要等于 l l l。
-
所以后一半到哈希表里查找 ( k , 2 n − 1 − s − 1 + 2 k − 1 , l − s u m ) (k,2^n-1-s-1+2^{k-1},l-sum) (k,2n−1−s−1+2k−1,l−sum)，找到则加上对应的方案数。
代码
#include<cstdio>
#include<cstring>
using namespace std;
#define md 9999997
#define LL long long
int n,len;
int dis[15][15],e[15],bz[15];
LL ans=0;
struct
{
int k,s,sum;
LL tot;
}hs[20000010];
void hash(LL k,LL s,LL sum)
{
LL x=k*s%md*sum%md;
int ok=0;
while(hs[x].k)
{
if(hs[x].k==k&&hs[x].s==s&&hs[x].sum==sum)
{
hs[x].tot++;
ok=1;
break;
}
x++;
if(x>20000000) x=0;
}
if(!ok) hs[x].k=k,hs[x].s=s,hs[x].sum=sum,hs[x].tot=1;
}
void find(LL k,LL s,LL sum)
{
LL x=k*s%md*sum%md;
while(hs[x].k)
{
if(hs[x].k==k&&hs[x].s==s&&hs[x].sum==sum)
{
ans+=hs[x].tot;
break;
}
x++;
if(x>20000000) x=0;
}
}
int ss=0;
void dfs(int k,int x,int s,int sum,int z)
{
if(x>z) hash(k,s,sum),ss++;
else
{
for(int i=2;i<=n;i++) if(!bz[i])
{
bz[i]=1;
if(sum+dis[k][i]<=len) dfs(i,x+1,s+e[i-1],sum+dis[k][i],z);
bz[i]=0;
}
}
}
void dfs1(int k,int x,int s,int sum,int z)
{
if(x>z) find(k,e[n]-s-2+e[k-1],len-sum);
else
{
for(int i=2;i<=n;i++) if(!bz[i])
{
bz[i]=1;
if(sum+dis[k][i]<=len) dfs1(i,x+1,s+e[i-1],sum+dis[k][i],z);
bz[i]=0;
}
}
}
int main()
{
int i,j;
scanf("%d%d",&n,&len);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) scanf("%d",&dis[i][j]);
e[0]=1;
for(i=1;i<=14;i++) e[i]=e[i-1]*2;
if(n%2==0)
{
dfs(1,1,0,0,n/2);
dfs1(1,1,0,0,n/2);
}
else
{
dfs(1,1,0,0,n/2);
dfs1(1,1,0,0,n/2+1);
}
printf("%lld",ans);
return 0;
}