题解：P5320 [BJOI2019] 勘破神机

· · 题解

upd on 2026/4/28：修改了一下 \LaTeX 公式。

题解区的阅读门槛都有点高，来篇适合中国宝宝体质的题解。

想要阅读本文，你需要有：

以下正文。

我们从总的 N 个方案中选出 k 个，本质是求 \binom{N}{k} \bmod 998,244,353。我们需要确定 N 关于 n 的函数。

基本递推式

对于 m=2

考虑这部分是斐波那契数列的经典结论。

设方案数为 f_n，有

f_n=\begin{cases}1,&n=1\\2,&n=2\\f_{n-1}+f_{n-2},& n > 2\end{cases}

感性理解就是考虑最后一列两个格子是横放还是竖放。

:::success[特征方程介绍，可跳过]

这个东西的通项公式怎么求呢？我们先忽略初值，假设 f 是一个等比数列，则有

q^2-q-1=0

这是一个一元二次方程，可以解出它的两个根，不难发现均符合条件。进而地，设两个公比为 q_1,q_2，我们发现

f_n=k_1q_1^n+k_2q_2^n

也满足给定递推公式，并且由给定的初始项，我们可以用待定系数法解出 k_1,k_2。

由上，我们将求解“公比”的方程定义为特征方程，将求出的“公比”定义为特征根。

:::

我们求解特征方程 x^2-x-1=0 得到两个特征根

x_1=\dfrac{1+\sqrt 5}{2}, x_2=\dfrac{1-\sqrt 5}{2}

利用待定系数法代入初值，得到通项公式

f_n=c_1x_1^n+c_2x_2^n

其中 c_1=\dfrac{5+\sqrt5}{10},c_2=\dfrac{5-\sqrt5}{10}。

对于 m=3

如果 n 是奇数，显然 3n \equiv 1 \pmod 2，可知无法填满。

如果 n 是偶数，设 n=2m，令 h_m 表示 3 \times 2m 的方案数，考虑如何递推。我们定义“不可拆分块”表示不存在竖直切口的填充方案。对于 3 \times 2 显然所有 3 种方案都是不可拆分块；对于 3 \times 4 的不可拆分块共 2 种：

\begin{bmatrix} 1&0&0&2 \\ 1&3&3&2 \\ 4&4&5&5\end{bmatrix}

及其上下翻转。我们注意到，对于 3 \times 2k(k \ge 2) 的不可分拆块总是只有 2 种，构造方法同 k=2 时。由此我们得到，

h_m=3h_{m-1}+2h_{m-2}+\dots+2h_0

我们利用简单的错位相减知识，可以得到：

\begin{aligned}h_{m-1}&=3h_{m-2}+2h_{m-3}+\dots+2h_0 \\ h_m-h_{m-1}&=3h_{m-1}-h_{m-2} \\ h_m &=4h_{m-1}-h_{m-2}\end{aligned}

求解特征方程 x^2-4x+1=0 得到

x_1=2+\sqrt3,x_2=2-\sqrt3

同理得到通项公式：

h_m=c_1x_1^m+c_2x_2^m

其中 c_1=\dfrac{3+\sqrt3}{6},c_2=\dfrac{3-\sqrt3}{6}。

有了基本递推式后，我们需要快速求解 [l,r] 区间内的答案之和，这就要求我们对和式进行化简。

和式化简

对于 m=2

考虑组合数与下降幂的转化：

\binom{x}{k} = \dfrac{x^{\underline k}}{k!} = \dfrac{1}{k!}\sum\limits_{i=0}^k s(k,i)x^i

其中 s(k,i) 表示第一类斯特林数。

:::success[关于第一类斯特林数及本公式推导，可跳过] 证明：

x^{\underline n} = \sum\limits_{i=0}^n s(n,i)x^i

以下推导用到 s(n,m) 的性质：

s(n+1,m)=s(n,m-1)-n\cdot s(n,m)

考虑数学归纳法，当 k=0 时易得左右两边都是 1：

x^{\underline 0}=s(0,0)x^0=1

假设当 k=n 时等式成立，那么当 k=n+1 时：

\begin{aligned}x^{\underline {n+1}}&=x^{\underline n} \cdot (x-n)\\&=(x-n)\sum\limits_{i=0}^n s(n,i)x^i \\&=\sum\limits_{i=0}^n s(n,i)x^{i+1} - n\sum\limits_{i=0}^n s(n,i) x^i\end{aligned}

我们观察 x^i 项的系数，正是 s(n,i-1)-n\cdot s(n,i)，代入第一类斯特林数的性质即证。

说了这么多，第一类斯特林数（这里是有编号的）到底是什么呢？其实你也不用关心，因为下面代码中允许你 \mathcal O(k^2) 地预处理出来，所以你只需要知道有这么个式子即可。 :::

我们把 x=c_1x_1^n+c_2x_2^n 代入，并利用二项式定理展开：

(c_1x_1^n+c_2x_2^n)^i = \sum\limits_{j=0}^i\binom{i}{j} c_1^jc_2^{i-j}(x_1^jx_2^{i-j})^n

我们把求和符号 \sum\limits_{n=l}^r 写到最内层整理算式，有

\sum\limits_{i=0}^k s(k,i) \sum\limits_{j=0}^i \binom{i}{j}c_1^jc_2^{i-j} \sum\limits_{n=l}^r (x_1^jx_2^{i-j})^n

注意到最后一项是一个等比数列求和，套用公式法：

对于 m=3

大致同理，但注意到 n \equiv 1 \pmod 2 时式子没有贡献。因此，我们需要将区间 [l,r] 映射到 [\lceil\dfrac{l}{2} \rceil, \lfloor \dfrac{r}{2}\rfloor]，对偶数项求和，有

\sum\limits_{i=0}^ks(k,i)\sum\limits_{j=0}^i\binom{i}{j}c_1^jc_2^{i-j}\sum\limits_{n=l'}^{r'}\left((x_1^jx_2^{i-j})^2 \right)^n

容易注意到最后还是一个等比数列，类似求解即可。

扩域

到这里我们就做完了……吗？

实际你会发现，我们的 c 是带有 \sqrt 5 和 \sqrt 3 的，但我们却要在 \bmod \,998,244,353 意义下运算。同时，我们注意到 5,3 在 \bmod \, 998,244,353 意义下不存在整数平方根。

我们类比复数，构建一个代数扩域 \mathbb Z_p[\sqrt D]。

:::success[浅论“扩域”] 对于数学知识比较薄弱的同学，这里看不懂也没有关系，只需要知道我们把数的规模从整数拓展到了“整数与给定根式的加减乘除”的规模即可。

而对于数学知识较强的同学，我们注意到集合 \mathbb Z_p[\sqrt D]=\{x \mid x = a+b\sqrt D,a,b \in \mathbb Z\}(D \in \mathbb R_+) 关于四则运算具有封闭性。这就是说，

\forall a,b \in \mathbb Z_p[\sqrt D],\\(a+b),(a-b),(a \times b),(a \div b) \in \mathbb Z_p[\sqrt D]

我们称这样的集合为“数域”（仅考虑数的范围）。容易类比到复数域。实际上，有理数域、实数域、复数域都是常见的域。但是整数环缺少乘法逆元（比如 \dfrac{5}{7} \notin \mathbb Z）从而不是域。 :::

我们将所有运算符表示为 a+b\sqrt D 的形式，乘法、逆元（除法）类似复数共轭：

\dfrac{1}{a+b\sqrt D}=\dfrac{a-b\sqrt D}{a^2-b^2D}

这下我们真的做完了，时间复杂度为 \mathcal O(Tk^2 \log n)，同时空间复杂度为 \mathcal O(k^2)。

如果你有决心写这道题的话，代码应当是不难的。

:::success[code]

ll D;
struct field{
    ll r,i;
    field(ll r=0,ll i=0):r(r%mod),i(i%mod){
        if(this->r<0)this->r+=mod;
        if(this->i<0)this->i+=mod;
    }
    field operator+(const field&o)const{return field(r+o.r,i+o.i);}
    field operator-(const field&o)const{return field(r-o.r,i-o.i);}
    field operator*(const field&o)const{
        return field(r*o.r+i*o.i%mod*D,r*o.i+i*o.r);
    }
    field operator*(ll val)const{return field(r*val,i*val);}
    field invv()const{
        ll low=(r*r%mod-i*i%mod*D%mod+mod)%mod;low=inv(low);
        return field{r*low,(mod-i)*low};
    }
    field operator/(const field&o)const{return*this*o.invv();}
};
field qp(field a,ll b){
    field ret(1,0);
    for(;b;b>>=1,a=a*a)
        if(b&1)ret=ret*a;
    return ret;
}
field sumup(field x,ll l,ll r){
    if(x.r==1&&x.i==0)return field((r-l+1)%mod,0);
    field upp=qp(x,l)-qp(x,r+1),low=field(1,0)-x;
    return upp/low;
}

D=(m==2)?5:3;
field x1,x2,c1,c2;
if(m==2){
    ll i2=inv(2),i10=inv(10);
    x1=field(i2,i2),x2=field(i2,mod-i2);
    c1=field(5*i10,i10),c2=field(5*i10,mod-i10);
}else{
    ll i6=inv(6);
    x1=field(2,1),x2=field(2,mod-1);
    c1=field(3*i6,i6),c2=field(3*i6,mod-i6);
}
while(T--){
    ll l,r;int k;
    cin>>l>>r>>k;
    ll len=(r-l+1)%mod;
    if(m==3)l=(l+1)/2,r/=2;
    field tot(0,0);
    if(l>r){cout<<"0\n";continue;}
    for(int i=0;i<=k;i++){
        field tmp(0,0);
        for(int j=0;j<=i;j++){
            field x=qp(x1,j)*qp(x2,i-j);
            field Kp=qp(c1,j)*qp(c2,i-j)*c[i][j];
            tmp=tmp+Kp*sumup(x,l,r);
        }
        tot=tot+tmp*s[k][i];
    }
    cout<<tot.r*inv(fac[k])%mod*inv(len)%mod<<'\n';
}

:::