注意到每個(gè)路線相鄰車站的距離不超過K，也就是說我們可以對連續(xù)K個(gè)車站的狀態(tài)進(jìn)行狀壓。

然后狀壓DP一下，用矩陣快速冪加速運(yùn)算即可。

?

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm>#define MAXN 140 #define MOD 30031using namespace std;struct Matrix {int num[MAXN][MAXN];int n,m; //n*m大小矩陣void setOne(int a,int b){n=a,m=b;for(int i=1;i<=min(n,m);i++) num[i][i]=1;}Matrix() { memset(num,0,sizeof(num)); } }T,A,one;Matrix operator*(Matrix a,Matrix b) {Matrix c;c.n=a.n,c.m=b.m;for(int i=1;i<=c.n;i++)for(int j=1;j<=c.m;j++)for(int k=1;k<=a.m;k++)c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j])%MOD;return c; }Matrix fastPow(Matrix base,int pow) {Matrix ans;ans.setOne(base.n,base.m);while(pow){if(pow&1) ans=ans*base;base=base*base;pow>>=1;}return ans; }int calc(int x) //計(jì)算x的二進(jìn)制中1的個(gè)數(shù) {int sum=0;while(x){sum++;x-=x&(-x); //x去掉最后一個(gè)1 }return sum; }int n,k,p,goal; //goal是目標(biāo)狀態(tài)bool canConvert(int to,int from) //檢查狀態(tài)from能否一步轉(zhuǎn)移到狀態(tài)to {from=(from-(1<<(p-1)))<<1; //這一步相當(dāng)于把from向左推了一位，個(gè)位用0補(bǔ)齊int tmp=from^to; //tmp應(yīng)該只有一個(gè)1if(tmp==(tmp&(-tmp))) return true; //tmp只有一個(gè)1，則是合法的return false; //否則是不合法的 }int status[MAXN],top=0; //保存所有DP過程中可能出現(xiàn)的狀態(tài)的棧int main() {scanf("%d%d%d",&n,&k,&p);for(int S=(1<<(p-1));S<(1<<p);S++) //枚舉DP狀態(tài)S,S是合法狀態(tài)當(dāng)且僅當(dāng)S的二進(jìn)制中1的個(gè)數(shù)恰好為k {if(calc(S)==k){status[++top]=S;if(S==(1<<p)-1-((1<<(p-k))-1)) goal=top; //S是最終要達(dá)到的狀態(tài) }}for(int i=1;i<=top;i++)for(int j=1;j<=top;j++)if(canConvert(status[i],status[j]))T.num[i][j]=1;A.n=A.m=T.n=T.m=top;A.num[1][goal]=1;T=fastPow(T,n-k);A=A*T;printf("%d\n",A.num[1][goal]);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/lishiyao/p/6882236.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2004 公交线路(状压DP+矩阵快速幂)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。