题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2004
求方案数,想到DP;
因为两个站间距离<=p,所以每p个站中所有车一定都会停靠至少一次,借此设计状态为p个站的停靠状态;
状压一下,1表示有车,0表示没有车,每个状态只有k个1;
这样就可以转移了,后一个状态可以是前一个中的一辆车移动了过来,状态数+=前一个状态;
但这样没有规律,同一个状态中不同的1出现的顺序不同,会导致出现重复;
所以需要人为规定一个顺序,这里设计为p位中最后一位一定为1,也就是最新的站上一定有车,规定了一个状态中的1一定是从前往后一个一个出现这样的顺序,从而避免了重复;
这样规定同时也确保了每个站最后一定都被停靠过;
于是每个状态完全只由上一个状态得来,而每个状态能从哪些状态转移过来也是固定的,所以可以使用矩阵快速幂加速递推;
设初始值ans.a[1][1]=1,表示一开始是前k个车站上有车;
最后输出也是ans.a[1][1],只有后k位上有车这个状态是合法的。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,p,mod=,f[],ct;
struct Matrix{
int a[][];
Matrix operator * (const Matrix &y) const
{
Matrix x;
memset(x.a,,sizeof x.a);
for(int i=;i<=ct;i++)
for(int k=;k<=ct;k++)
for(int j=;j<=ct;j++)
(x.a[i][j]+=a[i][k]*y.a[k][j])%=mod;
return x;
}
}s,ans;
int calc(int x)
{
int s=;
while(x){s++;x-=(x&-x);}
return s;
}
void init()
{
int tt=(<<p)-;
for(int i=;i<=tt;i++)
if(calc(i)==k&&(i&)==)f[++ct]=i; for(int i=;i<=ct;i++)
for(int j=;j<=ct;j++)
if(calc((f[i]<<)&f[j])==k-)
s.a[j][i]=;
}
int main()
{
scanf("%d%d%d",&n,&k,&p);
init();
int t=n-k;
ans.a[][]=;
while(t)
{
if(t&)ans=s*ans;
s=s*s;
t>>=;
}
printf("%d",ans.a[][]%mod);
return ;
}