Luogu 1357 花园

发现$m$很小，直接状压起来，可以处理出一开始的合法的状态。

对于每一个合法的状态，可以处理出它的转移方向，即在后面填一个$1$或者填一个$0$，反着处理比较方便。

考虑一下环的情况，在这题中有一个小$trick$就是我们从一个状态$s$开始转移，转移$n$轮到达$n + m$位的情况，这样子只要计算它转移回自身的方案数就一定是合法的。

这样子就可以写方程了。设$f_{i, s}$表示到第$i$位后$m$位是$s$的方案数，这样子有$f_{i, s} = \sum f_{i - 1, s'}$   $s'$可以转移到$s$。

到这里时间复杂度变成了$O((n + m) * 2^m*2^m)$，可以通过$80$分的数据。

发现这一个转移的式子是矩阵乘法的形式，那么对于两个可以转移的状态$s'$和$s$，直接把转移矩阵中$f$的$f_{s', s}$记为$1$。

时间复杂度变成了$O(2^{3m} * logn)$，可以通过全部的数据。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int M = ;

const int S =  << M;

const ll P = 1e9 + ;

int m, K, maxS;

ll n, ans = ;

bool ok[S];

inline int min(int x, int y) {

    return x > y ? y : x;

}

struct Matrix {

    int len, wid;

    ll s[S][S];

    inline void init() {

        memset(s, 0LL, sizeof(s));

        len = wid = ;

    }

    friend Matrix operator * (const Matrix u, const Matrix v) {

        Matrix res; res.init();

        for(int i = ; i < u.len; i++)

            for(int j = ; j < v.wid; j++)

                for(int k = ; k < u.wid; k++)

                    res.s[i][j] = (u.s[i][k] * v.s[k][j] % P + res.s[i][j]) % P;

        res.len = u.len, res.wid = v.wid;

        return res;

    }

    inline Matrix pow(ll y) {

        Matrix res, x = *this; res.init();

        res.len = x.len, res.wid = x.wid;

        for(int i = ; i < min(res.len, res.wid); i++) res.s[i][i] = 1LL;

        for(; y > ; y >>= ) {

            if(y & ) res = res * x;

            x = x * x;

        }

        return res;

    }

} f;

int main() {

    scanf("%lld%d%d", &n, &m, &K);

    maxS =  << m;

    for(int i = ; i < maxS; i++) {

        int cnt = ;

        for(int tmp = i; tmp > ; cnt += (tmp & ), tmp >>= );

        if(cnt <= K) ok[i] = ;

    }

    f.init(), f.len = f.wid = maxS;

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

        if(ok[i]) {

            f.s[i >> ][i] = ;

            f.s[(i >> ) + ( << (m - ))][i] = ;

        }

    f = f.pow(n);

    Matrix now;

    for(int i = ; i < maxS; i++) {

        if(!ok[i]) continue;

        now.init(); now.len = , now.wid = maxS, now.s[][i] = 1LL;

        now = now * f;

        (ans += now.s[][i]) %= P;

    }

    printf("%lld\n", ans);

    return ;

}