【51nod1683】最短路

124 阅读 0 评论 82 点赞

我是靠谱客的博主踏实糖豆，最近开发中收集的这篇文章主要介绍【51nod1683】最短路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

原题链接
lyk有一个01矩阵，它一开始在(1,1)处，它想走到(n,m)，不幸的是它被剥夺了向左走的能力，也就是说，若lyk处于(i,j)，那么每一次lyk只能走向(i+1,j),(i,j+1),(i-1,j)三个地方，它所耗费的时间为它走过的路径中1的数量。它想知道从(1,1)走到(n,m)的最短路是多少。

但是这个问题十分的简单，lyk并不屑知道。

现在问题来了，lyk不想告诉你01矩阵是啥，它想知道的是从(1,1)走到(n,m)最短路为k的概率。

因此你需要输出的是当n+m行，第i行表示最短路为i-1的概率。

由于要输出小数点十分麻烦，因此你只需要输出概率*2^(n*m)后对p取模后的答案就行了。

Solution

其实就是求最短路为 k(0≤k≤n+m) k ( 0 ≤ k ≤ n + m ) 的方案数。先考虑朴素做法，需要每列同时考虑，但 (n+m)n ( n + m ) n 状态数过于庞大。
因为不能往左走，所以每一列上下相邻两个的最短路至多差1。
注意到 n≤6 n ≤ 6 ，可以设 fi,j,s f i , j , s 表示第 i i 列，第一行的最短路为 $j$ ， s s 是个三进制状态表示该列从第二行开始，每个格子上面格子的差。
转移时要算下一列的最短路，可以预处理。

时间复杂度为 $o (2^{n} 3^{n - 1} n m)$

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef long long ll;
const int N=120;
ll f[N][N][N<<3];
ll g[N<<3][1<<6][2];
int z[7],d[7],r[7],w[7];
int mo;
ll an[N];
int main()
{
int n,m;
scanf("%d %d %d",&n,&m,&mo);
z[0]=1;
fo(i,1,n) z[i]=z[i-1]*3;
fo(s1,0,z[n-1]-1){
d[1]=0;
fo(i,1,n-1){
int t=s1/z[i-1]%3-1;
d[i+1]=d[i]+t;
}
fo(s2,0,(1<<n)-1){
fo(i,1,n) w[i]=((s2&(1<<i-1))>0),r[i]=d[i]+w[i];
fo(i,2,n) r[i]=min(r[i],r[i-1]+w[i]);
fd(i,n-1,1) r[i]=min(r[i],r[i+1]+w[i]);
g[s1][s2][0]=r[1];
fo(i,2,n) g[s1][s2][1]+=(r[i]-r[i-1]+1)*z[i-2];
}
}
memset(d,0,sizeof(d));
fo(s,0,(1<<n)-1){
fo(i,1,n)
d[i]=d[i-1]+((s&(1<<i-1))>0);
int t=0;
fo(i,2,n) t+=(d[i]-d[i-1]+1)*z[i-2];
f[1][d[1]][t]++;
}
fo(i,1,m-1){
fo(j,0,i)
fo(s,0,z[n-1]-1){
if(!f[i][j][s]) continue;
fo(x,0,(1<<n)-1){
int t1=g[s][x][0]+j,t2=g[s][x][1];
f[i+1][t1][t2]+=f[i][j][s];
f[i+1][t1][t2]>=mo?f[i+1][t1][t2]-=mo:0;
}
}
}
fo(j,0,m)
fo(s,0,z[n-1]-1){
if(!f[m][j][s]) continue;
d[1]=j;
fo(i,1,n-1){
int t=s/z[i-1]%3-1;
d[i+1]=d[i]+t;
}
if(d[n]<0) continue;
an[d[n]]+=f[m][j][s];
an[d[n]]>=mo?an[d[n]]-=mo:0;
}
fo(i,0,n+m-1) printf("%lldn",an[i]);
}