小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距 离均为1km。 作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路： 1.设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。 2.每个车站必须被一辆且仅一辆公交车经过（始发站和 终点站也算被经过）。 3.公交车只能从编号较小的站台驶往编号较大的站台。 4.一辆公交车经过的相邻两个 站台间距离不得超过Pkm。 在最终设计线路之前，小Z想知道有多少种满足要求的方案。由于答案可能很大，你只 需求出答案对30031取模的结果。
仅一行包含三个正整数N K P，分别表示公交车站数，公交车数，相邻站台的距离限制。 N<=10^9，1<P<=10，K<N，1<K<=P
仅包含一个整数，表示满足要求的方案数对30031取模的结果。
样例一：10 3 3
样例二：5 2 3
样例三：10 2 4
1
3
81
【样例说明】
样例一的可行方案如下： (1,4,7,10)，(2,5,8)，(3,6,9)
样例二的可行方案如下： (1,3,5)，(2,4) (1,3,4)，(2,5) (1,4)，(2,3,5)
P<=10 , K <=8
emm这个题还是有难度的。 我想到的第一版dp为\(f[i][st']+=f[i-1][st]\) f[i][st]中的st为八进制p位数，表示哪些公交车经过 (i-p+1) 到 i 这连续p个站台 由于公交车相邻两者站台间距离不超过p，所以st中应出现所有公交车。 转移时注意st'与st必须满足st的后p-1位与st'的前p-1位相同。
这样是正确的。但显然时间空间都承受不了。
考虑原先的dp有哪些东西是不必要的。 注意到我们转移的时候，从st到st'，并没有用到经过某一站台的公交车编号是多少，只关心st与st'是否合法（即是否出现所有公交车）以及是否可以成功转移。 那么把st变为一个二进制p位数，其中某x位上的1代表有一个公交车在这p个站台中最后经过的站台为x 只要st中有k个1，且最后一位为1便是合法的。 从st到st'，只要st的后p-1位与st'的前p-1位至多有一位不同便可以成功转移。
但这样状态为\(2^p\)，仍有点多。
不过可以发现满足条件的st必须有k个1且最后一位为1，这样状态数就减为了 \(C_{p-1}^{k-1}\)，最多也就二百多。 之后就可以矩阵快速幂了。
细节还是有的，二进制位运算的地方要注意一些。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define P 30031 using namespace std; const int SZ=260; int tot; struct matrix{ int a[SZ][SZ]; matrix() { memset(a,0,sizeof(a)); } void init() { for(int i=0;i<tot;i++) a[i][i]=1; } matrix operator * (const matrix &b) const{ matrix c; for(int i=0;i<tot;i++) for(int j=0;j<tot;j++) for(int k=0;k<tot;k++) (c.a[i][j]+=a[i][k]*b.a[k][j])%=P; return c; } matrix operator *= (const matrix &b) { return *this=*this*b; } }; matrix Pow_mod(matrix x,int y){ matrix ret; ret.init(); while(y){ if(y&1) ret*=x; x*=x; y>>=1; } return ret; } int n,p,k; int num[1030]; int cal(int x){ int ret=0; while(x){ ret+=(x&1); x>>=1; } return ret; } void getnum(){ for(int i=0;i<(1<<p);i++) if(cal(i)==k && (i&1)==1) num[tot++]=i; } bool check(int x,int y){ if((y&1)==0) return false; int z=(x%(1<<(p-1)))^(y>>1); return z==(z&(-z)); } int main() { scanf("%d%d%d",&n,&k,&p); getnum(); matrix a,b; for(int i=0;i<tot;i++) for(int j=0;j<tot;j++) if(check(num[i],num[j])) a.a[i][j]++; b.a[0][0]=1; a=Pow_mod(a,n-k); /**/ b=b*a; printf("%d\n",b.a[0][0]); return 0; }转载于:https://www.cnblogs.com/lindalee/p/8543224.html
