出题人题解 | #计数#

原题解链接：https://ac.nowcoder.com/discuss/149984

首先可以装压dp

令$f(i,j)f(i,j)$表示由合法状态i转移到合法状态$jj$的方案数

对于合法的状态我们可以$dfsdfs$出来

对于状态转移间连边,发现对于状态之间的转移是一个有向图,

那么题目就抽象成了对于一个有向图,求从任意点出发，转移$nn$次的形成的环的总数

这个显然可以$floyedfloyed$转移的

那么只需要对于状态的邻接矩阵进行做$nn$次方,然后对于每个点出发的状态方案计数,也就是对矩阵对角线上的值求和

// luogu-judger-enable-o2
#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm>   
#define LL long long 
const int mod = 998244353; 
LL n,m,k,S; 
const int maxs = (1 << 5) + 7; 
struct Matrix {
    LL a[maxs][maxs]; 	
    Matrix(){memset(a,0,sizeof a); } 
    Matrix operator * (const Matrix & x) const { 
        Matrix ret; 
        for(int k = 0;k <= S;++ k) 
            for(int i = 0;i <= S;++ i) 
                for(int j = 0;j <= S;++ j) 
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * x.a[k][j]) % mod; 
        return ret; 
    } 
} t,ans; 
bool can[maxs]; 
void connect(int s,int num) { 
    can[s] = 1;int pre = s >> 1; 
    t.a[pre][s] = 1; 
    if(num == k && !(s & 1)) return; 
    t.a[pre | (1 << (m - 1))][s] = 1; 	 
} 
void dfs(int x,int num,int s) { 
    if(x == m + 1) {connect(s,num);return;} 
    dfs(x + 1,num,s); 
    if(num < k) dfs(x + 1,num + 1,s | (1 << (x - 1))) ; 
} 
void qpow() { 
    for(int i = 0;i <= S;++ i) ans.a[i][i] = 1; 
    for(;n;n >>= 1,t = t * t) 
        if(n & 1) ans = ans * t; 
} 
int main()  { 
    /*for(int test = 1; test <= 10; test++) {
        char s1[10] , in[10] = ".in", s1name[10] = "a";
        char s2[10] , out[10] = ".out", s2name[10] = "a";
     	sprintf(s1, "%d", test); strcat(s1, in); strcat(s1name, s1);
     	sprintf(s2, "%d", test); strcat(s2, out);strcat(s2name, s2);
        freopen(s1name, "r", stdin);
        freopen(s2name, "w", stdout); */
       memset(can,0,sizeof can); memset(t.a,0,sizeof t.a); memset(ans.a,0,sizeof ans.a); 
    	scanf("%lld%lld",&n,&m); 
    	k = m / 2; 
    	S = (1 << m) - 1; 
    	dfs(1,0,0); 
   	 	qpow(); 
    	LL Ans = 0; 
    	for(int i = 0;i <= S;++ i) if(can[i])Ans = (Ans + ans.a[i][i]) % mod; 
    	printf("%lld\n",Ans); 
    
    //} 	return 0;
}