BZOJ 2004 Bus 公交线路 解题报告

2004: [Hnoi2010]Bus 公交线路

Time Limit: 20 Sec  Memory Limit: 259 MB

Description

小Z所在的城市有N个公交车站，排列在一条长(N-1)km的直线上，从左到右依次编号为1到N，相邻公交车站间的距离均为1km。 作为公交车线路的规划者，小Z调查了市民的需求，决定按下述规则设计线路：

1.设共K辆公交车，则1到K号站作为始发站，N-K+1到N号台作为终点站。

2.每个车站必须被一辆且仅一辆公交车经过（始发站和终点站也算被经过）。 

3.公交车只能从编号较小的站台驶往编号较大的站台。 

4.一辆公交车经过的相邻两个

站台间距离不得超过Pkm。 在最终设计线路之前，小Z想知道有多少种满足要求的方案。由于答案可能很大，你只需求出答案对30031取模的结果。

Input

仅一行包含三个正整数N K P，分别表示公交车站数，公交车数，相邻站台的距离限制。

N<=10⁹，1<P<=10，K <=8，K<N，1<K<=P

Output

仅包含一个整数，表示满足要求的方案数对30031取模的结果。

Sample Input

Input1:

10 3 3

Input2:

5 2 3

Input3:

10 2 4

Sample Output

Output1:

1

Output2:

3

Output3:

81

HINT

样例一的可行方案如下： (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) 

Description

根据K和P的范围容易想到要使用状态压缩，再根据N的范围，容易想到矩阵快速幂。既然一辆公交车经停的两个站台间的距离不会超过P km，我们可以考虑将到了分成若干个长度为P的片段，作为若干状态。为了方便，我们认为公交车的移动是分别进行的，即一辆车到站后，另一辆车才会移动。我们用最前方的公交车的位置区分阶段，用状态压缩表示从最前方的车开始，向后P km的公交车停靠情况。显然，任何一个状态i的最高位，即p-1位是1，i中1的个数（记为count1(i)）等于K。i中的0的含义是有公交车曾经停靠过该位置，之后离开了，这样任何一辆公交车若想移动，就必须移动到下一个状态的最高位，由于状态的长度是P，这种移动一定可以实现。

不难看出，我们为了方便状压，令公交车的位置强制对齐在一个长度为P的范围内，我们可以证明，这种对齐不会遗漏情况。

【证明】假设当最前方的公交车位于位置i时，最后方的公交车位于位置j，且i-j>P，令位于位置j的公交车继续前进，到达的新位置是k，根据题意k-j<=P，且k位置原本没有公交车停靠。对于位置k原本的空缺，产生途径有二：该位置一直没有公交车停靠，该位置曾被公交车停靠，但停靠的公交车已离开。对于途径一，j位置的公交车来到k位置后即转换成了满足原命题的状态，该不符合原命题的状态可以看作两个符合原命题的状态间转移的中间状态；对于途径二，该转移与题意矛盾。因此，这种对齐没有遗漏情况。

黑色数字为站台的绝对位置，白色数字为公交车的编号，棕色为初始状态，黄色为终状态，红色为合法中间状态，橙色为非法中间状态，左侧和右侧的转移方式等价。

接下来我们需要确定两个状态之间是否可以转移，对于状态i和j，若状态i可以向状态j转移当且仅当count1((j<<1)^i)==2。以K=2，P=3为例，状态101可以转移为110，因为1100与0101只有两位不同；反之状态101不能转移为101。

注意到，状态的数量最多为C(9,4)=126，而不是2¹⁰个，我们可以考虑为状态编号，用detail数组存放每个编号对应的状态。

Code

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

const int mod = 30031;

inline void read(int &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

inline void read(long long &x)

{

    x = 0; char ch = getchar(); bool f = 0;

    while (ch>'9' || ch<'0') { if (ch == '-')f = 1; ch = getchar(); }

    while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }

    if (f)x = -x;

}

int ndetail = 0;

struct matrix

{

    int data[126][126];

    int size;

    matrix operator*(const matrix &b)const

    {

        matrix c;

        for (int i = 0; i<ndetail; i++)

        {

            for (int j = 0; j<ndetail; j++)

            {

                c.data[i][j] = 0;

                for (int k = 0; k<ndetail; k++)

                {

                   c.data[i][j] += data[i][k] * b.data[k][j];

                   c.data[i][j] %= mod;

                }

            }

        }

        return c;

    }

};

matrix pow(matrix a, int b)

{

    matrix m = a, ans;

    memset(ans.data, 0, sizeof(ans.data));

    for (int i = 0; i<ndetail; i++)

    {

        ans.data[i][i] = 1;

    }

    while (b)

    {

        if (b & 1)ans = ans*m;

        m = m*m;

        b >>= 1;

    }

    return ans;

}

int count1(int x)

{

    int ans = 0;

    while (x) { if (x & 1)ans++; x >>= 1; }

    return ans;

}

int detail[126];

matrix dp;

int main()

{

    int n, p, k;

    read(n); read(k); read(p);

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

    {

        if (count1(i) == k)

        {

            detail[ndetail++] = i;

        }

    }

    for (int i = 0; i<ndetail; i++)

    {

        for (int j = 0; j<ndetail; j++)

        {

            //from i to j

            if (count1((detail[j] << 1) ^ detail[i]) == 2)dp.data[i][j] = 1;

        }

    }

    dp = pow(dp, n - k);

    cout << dp.data[ndetail - 1][ndetail - 1];

    return 0;

}