bzoj2004公交线路——DP+矩阵加速递推

题目：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 ;

}

巴特西

bzoj2004公交线路——DP+矩阵加速递推

最新文章

热门文章