[難題題解] [BZOJ1875] [SDOI2009] HH去散步
題目H有個一成不變的習慣，喜歡飯後百步走。所謂百步走，就是散步，就是在一定的時間 內，走過一定的距離。 但是同時HH又是個喜歡變化的人，所以他不會立刻沿著剛剛走來的路走回。 又因為HH是個喜歡變化的人，所以他每天走過的路徑都不完全一樣，他想知道他究竟有多 少種散步的方法。 現在給你學校的地圖（假設每條路的長度都是一樣的都是1），問長度為t，從給定地 點A走到給定地點B共有多少條符合條件的路徑.
對於100%的數據，$N ≤ 20，M ≤ 60，t ≤ 2^{30}，0 ≤ A,B $
題解
既然n<=20，考慮開個鄰接矩陣$table$存圖
先考慮暴力，設$dp[i][j]$表示還需走i段路,當前走到了j這個點
易得$dp[i][j]=sum(dp[i+1][k]*table[j][k])+1$
然後無腦dfs即可
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int table[21][21],dp[21][11],n,a,b;
void dfs(int id,int from,int t)
{
//if(dp[id][from]) return;
if(!t)
{
dp[id][t]+=(id==b);
return;
}
for(int i=0;i<n;i++)
{
if(!table[id][i]||from==i) continue;
dfs(i,id,t-1);
dp[id][t]+=table[id][i]*dp[i][t-1];
dp[id][t]%=45989;
}
}
int main()
{
int m,t;
cin>>n>>m>>t>>a>>b;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
table[a][b]=++table[b][a];
}
dfs(a,0,t);
cout<<dp[b][0];
}
發現i這一維可以滾動掉，然後我們發現這個方程的轉移是固定不變
即，對於同一個j，都是同一批k來更新它。
那麼，我們可以先處理一個另一個鄰接矩陣$table2[k][i][j]$表示i在走了k步後到達j的方案書.
回憶floyd的過程，我們可以用類似的方法不斷用$table2[k-1][i][j]$計算出新的$table2[k][i][j]$
然後發現其實這就是矩陣乘法，於是這個過程可以用矩陣快速冪來加速。
這其實是一個很常見的圖論dp trick,當然，這個是要在點數小到可以用鄰接矩陣時才能用的
void mulit(int arr1[][130],int arr2[][130],int size)
{
memset(temp,0,sizeof(temp));
for(int i=1;i<=size;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<=cnt;k++)
{
temp[i][j]+=arr1[i][k]*arr2[k][j]%mod;
temp[i][j]%=mod;
}
}
}
memcpy(arr1,temp,sizeof(temp));
}
void qpow(int t)
{
for(int i=1;i<=cnt;i++) res[i][i]=1;
while(t)
{
if(t&1) mulit(res,table2,cnt);
mulit(table2,table2,cnt);
t>>=1;
}
}
然而題目要求我們不能立刻走回頭路，處理起來比較麻煩
所以我們把邊當成點，把相連的邊「連接」
另外，為了區分出邊的方向，我們把每條邊拆成兩條（分別兩個方向）
然後按照上述的方法處理出$table2[t][i][j]$
最後枚舉一遍從起點發出的邊，統計這些邊到達終點的方案數，輸出即可
程式碼
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int table2[130][130],n,a,b,cnt,from[130],to[130],head[130],nxt[130];
int res[130][130];
#define connect(a,b) table2[a][b]=1
#define mod 45989
int temp[130][130];
void mulit(int arr1[][130],int arr2[][130],int size)
{
memset(temp,0,sizeof(temp));
for(int i=1;i<=size;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<=cnt;k++)
{
temp[i][j]+=arr1[i][k]*arr2[k][j]%mod;
temp[i][j]%=mod;
}
}
}
memcpy(arr1,temp,sizeof(temp));
}
void qpow(int t)
{
for(int i=1;i<=cnt;i++) res[i][i]=1;
while(t)
{
if(t&1) mulit(res,table2,cnt);
mulit(table2,table2,cnt);
t>>=1;
}
}
void link(int x,int y)
{
from[++cnt]=x,to[cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int main()
{
int m,t;
cin>>n>>m>>t>>a>>b;
a++,b++;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
link(x,y);
link(y,x);
}
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
if(((i&1)&&j==i+1)||((i&1)==0&&j==i-1)) continue;
if(to[i]==from[j]) connect(i,j);
//if(from[i]==to[j]) connect(j,i);
}
}
/*for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++) cout<<table2[i][j]<<" ";
cout<<endl;
}*/
qpow(t-1);
int ans=0;
for(int l=head[a];l;l=nxt[l])
for(int i=1;i<=cnt;i++)
if(to[i]==b) ans+=res[l][i],ans%=mod;
cout<<ans;
}
