BZOJ2004 HNOI2010公交线路（状压dp+矩阵快速幂）

　　由数据范围容易想到矩阵快速幂和状压。

　　显然若要满足一辆公交车的相邻站台差不超过p，则每相邻p个站台中每辆车至少经过一个站台。可以发现这既是必要的，也是充分的。

　　开始的时候所有车是相邻的。考虑每次把一辆公交车塞到前方第一个未到达的站台。这个时候公交车之间是没有区别的，因为只要保证每相邻p个站台每辆车都出现也即有k辆车就可以了。

　　于是设f[i][j]为i-p+1~i的车站停靠状况为j的方案数。并且表示i站台状况的这一位必为1，j中一共有k个1。于是状态数至多有C(9,4)=126种。转移比较显然，只要由这个状态开一辆车能到下个状态就可以了。

　　每次转移都是相同的，那么矩阵快速幂即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 30031

#define N 130

struct matrix

{

    int n,a[N][N];

    matrix operator *(const matrix&b) const

    {

        matrix c;c.n=n;

        for (int i=;i<n;i++)

            for (int j=;j<b.n;j++)

            c.a[i][j]=;

        for (int i=;i<n;i++)

            for (int j=;j<b.n;j++)

                for (int k=;k<b.n;k++)

                c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%P;

        return c;

    }

}f,d;

int n,k,p,id[N],m;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2004.in","r",stdin);

    freopen("bzoj2004.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read(),k=read(),p=read();

    for (int i=<<p-;i<(<<p);i++)

    {

        int t=i,cnt=;

        while (t) cnt+=t&,t>>=;

        if (cnt==k) id[m++]=i;

    }

    d.n=m;

    for (int i=;i<m;i++)

        for (int j=;j<m;j++)

        {

            int x=(id[j]&(<<p-)-)<<^id[i];

            if (x==(x&-x)) d.a[i][j]=;

        }

    f.n=;

    f.a[][m-]=;

    n-=k;

    while (n)

    {

        if (n&) f=f*d;

        n>>=;

        d=d*d;

    }

    cout<<f.a[][m-];

    return ;

}