难度：省选/NOI-

题目描述

        小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2≤N≤1015)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2≤M≤5,M≤N)个花圃中有不超过K(1≤K<M)个C形的花圃，其余花圃均为P形的花圃。
        例如，N=10,M=5,K=3。则
        CCPCPPPPCC 是一种不符合规则的花圃；
        CCPPPPCPCP 是一种符合规则的花圃。
        请帮小L求出符合规则的花园种数Mod 1000000007
        现请您编写一个程序解决此题。

输入输出格式

输入格式：

        一行，三个数N,M,K。

输出格式：

        花园种数Mod 1000000007

输入输出样例

Sample input#1

10 5 3

Sample output#1

458

Sample input#2

6 2 1

Sample output#2

18

题解

        一道让人头秃的计数题，考察图论、矩阵快速幂。
        注意到m和k都很小，十分有利于状态压缩，可以用一个二进制数表示花园的种类序列。比如对于题目中给出的CCPPPPCPCP序列，可以写成：1100001010。
        在样例一下，m=5，发现上面给出的例子便是样例一的一个合法解，将它拆成若干个长度为5的连续子序列，得到：11000、10000、00001、00010、00101、01010，由于是环，故还有后面的部分：10101、01011、10110、01100。这里每一个子序列都是合法的，易知它们的种类是有限的，这样总的序列可以看做是这些子序列的一个排列。
        容易发现这些序列有很明确的后继关系：后一个序列总是前一个序列去掉最高位再在末尾加上0或1得到的。将每一个合法子序列看作节点，这种后继关系看作有向边，可以建立一个图。那么要求的序列就是这个图上的一条路。
        题目要求是环也不影响做法。在上文给出的01序列的最后补充一个11000，这样序列首尾相同，将它们首尾连接得到的一定是一个合法的环。因此题目等价于求图上所有边数为n的回路数量，这是因为回路与要求的环有着一一对应的关系。
        如何求长度固定的回路条数便成问题的重点，这里需要邻接矩阵来完成这项操作。有一个基本事实：

设一个图的邻接矩阵为S，则Sn中第i行第j列的元素表示节点i到节点j长度为n的路的数量。

        这个结论很重要，它是求路数量问题的一个重要解法原理。
        由于图的规模很小，邻接矩阵空间占用不大，因此可以对矩阵求n次幂，从而找到路的数量。求幂当然选择矩阵快速幂，而回路怎么找呢？回路可以看作节点i到节点i本身的路，也就是主对角线上的元素，求完幂后将主对角线上的元素加起来再取模就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>

#define MOD 1000000007
using namespace std;
int m, k, cnt = 0;
long long n;
int to1[100], to2[100];

struct Matrix {
    long long op[100][100] = {0};

    void operator*=(Matrix x) {
        long long temp[100][100] = {0};
        for (int i = 1; i <= cnt; i++) {
            for (int j = 1; j <= cnt; j++) {
                for (int k = 1; k <= cnt; k++)temp[i][j] += op[i][k] * x.op[k][j], temp[i][j] %= MOD;
            }
        }
        for (int i = 1; i <= cnt; i++) {
            for (int j = 1; j <= cnt; j++)op[i][j] = temp[i][j];
        }
    }
};

inline int check(int x) {
    int ans = 0;
    while (x > 0) {
        if ((x & 1) > 0)ans++;
        x >>= 1;
    }
    return ans;
}


int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < (1 << m); i++) {
        int tp = check(i);
        if (tp <= k)cnt++, to1[cnt] = i, to2[i] = cnt;//构造双向映射
    }
    Matrix sta, E;
    for (int i = 1; i <= cnt; i++) {
        int temp = (to1[i] & ((1 << (m - 1)) - 1)) << 1;//去首并左移
        if (check(temp) == k)sta.op[i][to2[temp]] = 1;//填邻接矩阵
        else sta.op[i][to2[temp]] = sta.op[i][to2[temp + 1]] = 1;
    }
    for (int i = 1; i <= cnt; i++)E.op[i][i] = 1;//单位阵
    while (n > 0) {//矩阵快速幂
        if ((n & 1) > 0)E *= sta;
        sta *= sta;
        n >>= 1;
    }
    long long ans0 = 0;
    for (int i = 1; i <= cnt; i++)ans0 += E.op[i][i], ans0 %= MOD;//对角线求和取模
    cout << ans0;
    return 0;
}