自动搬运

查看原文

来自洛谷，原作者为

	luanyanjia 菜 -我ら是个と大に傻む逼なり-

搬运于2025-08-24 23:09:12，当前版本为作者最后更新于2025-02-02 21:32:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注意：本文中 $0$ 和 $1$ 全是反的，我读题也是这么读的，但不影响答案就不改了。

首先期望乘上总方案数，变成对任意 $h$ 序列，统计 $a$ 序列的方案数。

$h_i = 0$ 时，$a_i$ 可以变成任意大的数，所以一定不会影响答案。

先把 $a$ 序列变成它的异或差分，差分后的序列和原序列仍然一一对应。现在限制变成了不存在 $i,j$ 使得 $a_i = a_j$ 且 $h_i = h_{i-1} = h_{j} = h_{j-1} = 1$，然后 $a_1$ 随便填。

设 $f_{n,i}$ 为长为 $n$ 的 01 序列中有多少含有恰好 $i$ 对连续的 $1$。知道了 $f_i$ 那么答案就是 $\sum\limits_{i = 0}^{n-1}{f_i \binom{2^k}{i} (2^{k})^{n-i}}$。

要求 $f_{n,i}$，考虑朴素 DP：设 $g_{i,j,0/1}$ 为长为 $i$ 的序列中有 $j$ 对连续的 $1$，且最后一位是 $0$ 或 $1$ 的方案数。有：

$$g_{i,j,0} = g_{i-1,j,0} + g_{i-1,j,1}$$ $$g_{i,j,1} = g_{i-1,j,0} + g_{i-1,j-1,1}$$

直接暴力转移，复杂度 $O(n^2)$，能得 $60$ 到 $80$ 分。

其实我们只需要 $g_{n,i,0/1}$，考虑 $F_{i,0/1} = \sum\limits_{j = 0}^{\infty}{g_{i,j,0/1} x^{j}}$。上述转移用 $F$ 刻画就是：

$$F_{i,0} = F_{i-1,0} + F_{i-1,1}$$ $$F_{i,1} = F_{i-1,0} + xF_{i-1,1}$$

是不是很矩阵？可以用矩阵再刻画：

$$\begin{bmatrix} F_{n,0} & F_{n,1}\\0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1\\0 & 0 \end{bmatrix} {\begin{bmatrix} 1 & 1\\1 & x \end{bmatrix}}^{n-1} $$

后面就很明了啦。直接算显然爆炸，考虑插值。把 NTT 要用的单位根全都带进去算一遍，再逆回来就能得到 $f$ 数组，进而得到答案。时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
void rd(){}
template<typename T,typename... U> void rd(T &x,U&... arg){
	x=0;int f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
	x*=f;rd(arg...);
}
const int N=1<<21;
const int mod=998244353;
int n,k,maxn;
inline int KSM(int x,int n){
	int ans=1;
	while(n){
		if(n&1)ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;
		n>>=1;
	}
	return ans;
}
int rt[N+5],f[N+5],id[N+5];
inline void Init(int n){
	int k=__builtin_ctz(n);
	for(int i=1;i<n;i++){
		if(i&1)id[i]=id[i>>1]>>1|(1<<(k-1));
		else id[i]=id[i>>1]>>1;
	}
	rt[n/2]=1;
	int bas=KSM(3,(mod-1)/n);
	for(int i=n/2+1;i<n;i++)rt[i]=1ll*rt[i-1]*bas%mod;
	for(int i=n/2-1;i>=1;i--)rt[i]=rt[i*2];
}
inline void IDFT(int* a,int n){
	for(int i=0;i<n;i++)
		if(i<id[i])swap(a[i],a[id[i]]);
	for(int i=1;i<n;i<<=1){
		for(int j=0;j<n;j+=i*2){
			for(int k=0;k<i;k++){
				int x=a[j+k],y=a[i+j+k];
				a[j+k]=(x+1ll*y*rt[i+k]%mod)%mod;
				a[i+j+k]=(x+1ll*(mod-y)*rt[i+k]%mod)%mod;
			}
		}
	}
	reverse(a+1,a+n);
	int invn=KSM(n,mod-2);
	for(int i=0;i<n;i++)a[i]=1ll*a[i]*invn%mod;
}
struct Matrix{
	int m[2][2];
	Matrix(){memset(m,0,sizeof m);}
	Matrix(int _a,int _b,int _c,int _d){m[0][0]=_a,m[0][1]=_b,m[1][0]=_c,m[1][1]=_d;}
	int* operator[](int x){return m[x];}
	Matrix operator*(Matrix b){
		Matrix c;
		c[0][0]=(1ll*m[0][0]*b[0][0]+1ll*m[0][1]*b[1][0])%mod;
		c[0][1]=(1ll*m[0][0]*b[1][0]+1ll*m[0][1]*b[1][1])%mod;
		c[1][0]=(1ll*m[0][1]*b[0][0]+1ll*m[1][1]*b[1][0])%mod;
		c[1][1]=(1ll*m[0][1]*b[1][0]+1ll*m[1][1]*b[1][1])%mod;
		return c;
	}
};
inline Matrix KSM(Matrix x,int n){
	Matrix ans=Matrix(1,0,0,1);
	while(n){
		if(n&1)ans=ans*x;
		x=x*x;
		n>>=1;
	}return ans;
}
signed main(){
	rd(n,k);
	maxn=1;
	while(maxn<=n)maxn*=2;
	Init(maxn);
	int BAS=KSM(3,(mod-1)/maxn),now=1;
	for(int i=0;i<maxn;i++){
		Matrix bas=Matrix(1,1,0,0),m=Matrix(1,1,1,now);
		bas=bas*KSM(m,n-1);
		f[i]=(bas[0][0]+bas[0][1])%mod;
		now=1ll*now*BAS%mod;
	}
	IDFT(f,maxn);
	int ans=0;now=KSM(2,k),BAS=1;
	for(int i=0;i<n;i++){
		(ans+=1ll*f[i]*BAS%mod*KSM(KSM(2,k),n-i)%mod)%=mod;
		BAS=1ll*BAS*(now--)%mod;
	}
	printf("%lld\n",1ll*ans%mod*KSM(KSM(KSM(2,k),n),mod-2)%mod);
	return 0;
}