牛客练习赛27-F 计数 (状压DP + 矩阵快速幂)

牛客练习赛27-F
题意：见上。
$m$小考虑状压，$n$大考虑矩阵优化
$dp(i,j)$为合法$i$转移到合法$j$状态的方案数，其中状态是当前位置为$i$, 区间$[i-m+1,i]$填$3, 7$情况，判断一下就可以构造转移矩阵，然后发现转移可以看做Floyd的联通矩阵，题面就要求某个点开始的环的个数。
那么矩阵快速幂一下，再加上对角线的值即可(加上每个点出发环的个数)

另外可以用常规DP方法做，快速幂次数就进行$n-m$次，之后将末尾和前面check一下即可

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 998244353;

    LL n, m, p;

    struct mat {
        LL a[32][32];
        mat() {ms(a, 0);}
    } f, tr;

    mat mul(mat a, mat b) {
        mat ret;
        for (LL i = 0; i <= p; ++i) {
            for (LL j = 0; j <= p; ++j) {
                for (LL k = 0; k <= p; ++k) {
                    (ret.a[i][j] += a.a[i][k] * b.a[k][j] % MO) %= MO;
                }
            }
        }
        return ret;
    }
    mat ksm(mat a, LL b) {
        int fl = 0;
        mat bs = a, ans;
        while (b) {
            if (b & 1) {
                if (!fl) fl = 1, ans = bs;
                else ans = mul(ans, bs);
            }
            bs = mul(bs, bs);
            b >>= 1; 
        }
        return ans;
    }
    LL get(LL x) {LL ret = 0; while (x) ++ret, x &= (x - 1); return ret;} 

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m;
        p = (1 << m) - 1;
        for (LL S = 0; S <= p; ++S) if (get(S) <= m / 2) {
            tr.a[S][((S << 1) & p)] = 1;
            if (get(((S << 1) & p) | 1) <= m / 2) tr.a[S][((S << 1) & p) | 1] = 1;
        }
        tr = ksm(tr, n);
        LL ans = 0;
        for (LL S = 0; S <= p; ++S) (ans += tr.a[S][S]) %= MO;
        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
2 2
3 3
4 3 
*/