【BZOJ2004】公交線路（動態規劃，狀態壓縮，矩陣快速冪）

題面

BZOJ

題解

看到\(k,p\)這么小
不難想到狀態壓縮
看到\(n\)這么大，不難想到矩陣快速冪

那么，我們來考慮樸素的\(dp\)
設\(f[i][j]\)表示當前位置為\(i\)，前面的\(P\)個位置的狀態為\(j\)
其中，狀態的含義是某個公交線路最后的停靠站
如果是最后的停靠站就是\(1\)，否則是\(0\)

那么，任意狀態中只存在\(k\)個\(1\)
并且表示\(i\)的二進制位一定是\(1\)
所以狀態相當于最多只會有\(120\)個左右

考慮轉移，
每次相當于從原來的狀態中，
把一個\(1\)放到了當前位置
其他的依次向左挪一個位置
那么，如果兩個狀態之間滿足這個關系，就可以轉移

我們發現轉移之和后面的\(j\)有關
所以矩陣快速冪就行了

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define ll long long #define RG register #define MOD 30031 inline int read() {RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t; } int n,K,P; int zt[1<<11],ss,mp[1<<11]; struct Dalao {int s[150][150];void init(){memset(s,0,sizeof(s));}void pre(){init();for(int i=1;i<=ss;++i)s[i][i]=1;} }zsy; Dalao operator*(Dalao a,Dalao b) {Dalao ret;ret.init();for(int i=1;i<=ss;++i)for(int j=1;j<=ss;++j)for(int k=1;k<=ss;++k)ret.s[i][j]=(ret.s[i][j]+a.s[i][k]*b.s[k][j]%MOD)%MOD;return ret; } Dalao fpow(Dalao a,int b) {Dalao s;s.pre();while(b){if(b&1)s=s*a;a=a*a;b>>=1;}return s; } int ws(int x){int ret=0;while(x)++ret,x-=x&(-x);return ret;} bool check(int a,int b) {if(ws((a<<1)&b)!=K-1)return false;return true; } int main() {n=read();K=read();P=read();for(int i=0;i<(1<<P);++i)if((i&1)&&ws(i)==K)zt[++ss]=i;for(int i=1;i<=ss;++i)for(int j=1;j<=ss;++j)if(check(zt[i],zt[j]))zsy.s[j][i]=1;zsy=fpow(zsy,n-K);printf("%d\n",zsy.s[1][1]);return 0; }

轉載于:https://www.cnblogs.com/cjyyb/p/8434235.html

總結

以上是生活随笔為你收集整理的【BZOJ2004】公交线路（动态规划，状态压缩，矩阵快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。