P11658 「FAOI-R5」波特检测 题解
luanyanjia
·
·
题解
注意：本文中 0 和 1 全是反的，我读题也是这么读的，但不影响答案就不改了。
首先期望乘上总方案数，变成对任意 h 序列，统计 a 序列的方案数。
先把 $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)$。
```cpp
#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;
}
```