【题目描述】城市有N个公交车站，排列在一条长为N-1公里的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1公里。按以下规则设计线路：1．设共有K辆公交车，则1到K号车站作为始发站，N-K+1到N号车站作为终点站。2．每个车站必须被一辆且仅一辆公交车经停（始发站和终点站也算被经停）。3．公交车只能从编号较小的车站驶向编号较大的车站。4．一辆公交车经停的相邻两个车站间的距离不得超过P公里。注意“经停”是指经过并停车，因经过不一定会停车，故经停与经过是两个不同的概念。现在想知道有多少种满足要求的方案。只需求出答案对30031取模的结果。【输入格式】只有一行，其中包含用空格隔开的三个正整数N，K，P，分别表示公交车站数，公交车数，一辆公交车经停的相邻两个车站间的最大距离。【输出格式】仅包含一个整数，表示满足要求的方案数对30031取模的结果。
【输入输出样例】input output样例一：10 33 1样例二：5 23 3样例三：10 24 81样例解释：样例一满足要求的方案只有1种，即：(1,4,7,10)，(2,5,8)，(3,6,9)。样例二满足要求的方案有3种，即：(1,3,5)，(2,4)；(1,3,4)，(2,5)和(1,4)，(2,3,5)。【数据规模】40%的数据满足N≤1000。100%的数据满足1<N<10^9，1<P≤10，K<N，1<K≤P
计数dp蒟蒻先给各位大神跪烂。
看到这个题的第一感觉就是没法下手（搜索没法骗分啊啊啊啊啊啊~~~~~）。
仔细看了看数据规模，发现了p和k的值都很小，感觉这肯定是一个重要条件。
经过分析以后，发现题目要求每个站都必须有公交车经停一次，如果与当前站的距离大于了p，且没有被经停，那么这个站就再也没有机会被经停了。
所以我们可以定义一个状态f[i][State]表示i以及之前的所有站都被经停，state表示i后面p个站哪些地方停了车。（并且保证i站有车停）
每次转移只考虑第i个站的公交车往哪里开就行了。
光是这样还不能通过此题，还要用矩阵快速幂来优化。
具体细节见标程：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int LIM=1<<11;const int MOD=30031;const int MAXN=140;int n,K,p;int State[MAXN],Cnt[LIM];int cnt,_,tmp;struct MATRIX{ int n,m; int Matrix[MAXN][MAXN]; MATRIX(){ memset(Matrix,0,sizeof(Matrix)); }};MATRIX r,Ans;bool Check(int x){ int Ret=0; while(x){ x-=x&-x; Ret++; } return Ret==K;}MATRIX Mult(MATRIX a,MATRIX b){ MATRIX Ret; Ret.n=a.n; Ret.m=b.m; for(int i=1;i<=a.n;i++) for(int j=1;j<=b.m;j++) for(int k=1;k<=a.m;k++) Ret.Matrix[i][j]=(Ret.Matrix[i][j]+a.Matrix[i][k]*b.Matrix[k][j])%MOD; return Ret;}int main(){ scanf("%d%d%d",&n,&K,&p); _=(1<<p)-1; tmp=1<<(p-1);//保证最高位是1 for(int i=0;i<tmp;i++) if(Check(tmp+i)){ State[++cnt]=tmp+i; Cnt[tmp+i]=cnt; } int t; r.n=cnt; r.m=cnt; for(int i=1;i<=cnt;i++){ t=_&(State[i]<<1); for(int j=1;j<=p;j++) if(!((t>>(j-1))&1)&&(t+(1<<j-1))>=tmp) r.Matrix[i][Cnt[t+(1<<j-1)]]++; } t=Cnt[((1<<K)-1)<<(p-K)]; Ans.Matrix[1][t]=1,Ans.n=1; Ans.m=cnt; n-=K; while(n){ if(n&1) Ans=Mult(Ans,r); n>>=1; r=Mult(r,r); } printf("%d",Ans.Matrix[1][t]); return 0;}
转载于:https://www.cnblogs.com/Return-0/archive/2013/03/18/2965460.html
相关资源：数据结构—成绩单生成器