題目

發現\(n\)比較大，但是\(k,p\)都很小，考慮矩乘使得復雜度傾斜一下

發現所有車的最大間隔都是\(p\)，還保證\(k<p\)，于是我們可以考慮壓下最后\(p\)位的情況

于是設\(dp[i][S]\)表示目前最遠的車來到了\(i\)位置，最后\(p\)為是否有車的狀態是\(S\)，\(0\)表示沒車，\(1\)表示有車

轉移的話我們就使得某一輛車提前就好了，注意如果\(i-p+1\)有車的話，提前的只能是這輛車了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define re register const int M=1024; const int mod=30031; struct mat{int a[255][255];}a; int n,K,P,sz; int id[M],to[M]; inline mat operator*(mat a,mat b) {mat c;for(re int i=0;i<sz;i++)for(re int j=0;j<sz;j++) c.a[i][j]=0;for(re int k=0;k<sz;k++)for(re int i=0;i<sz;i++)for(re int j=0;j<sz;j++) {c.a[i][j]+=a.a[i][k]*b.a[k][j];if(c.a[i][j]>mod) c.a[i][j]%=mod;}return c; } mat ksm(int b) {mat S=a;b--;while(b) {if(b&1) S=S*a;b>>=1;a=a*a;}return S; } void dfs(int t,int s,int num) {if(t==P+1) {if(num==K) id[sz]=s,to[s]=sz++;return;}dfs(t+1,s,num);dfs(t+1,s|(1<<(t-1)),num+1); } int main() {scanf("%d%d%d",&n,&K,&P);dfs(1,0,0);for(re int i=0;i<sz;i++) {int now=id[i];for(re int j=0;j<P;j++)if(now>>j&1) {if((now>>(P-1)&1)&&j!=P-1) continue; a.a[to[(now^(1<<j))<<1|1]][i]++;}}int k=(1<<K)-1;mat ans=ksm(n-K);printf("%d\n",ans.a[to[k]][to[k]]);return 0; }

轉載于:https://www.cnblogs.com/asuldb/p/10569910.html

總結

以上是生活随笔為你收集整理的[HNOI2010]公交线路的全部內容，希望文章能夠幫你解決所遇到的問題。

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