出题人你具体数学看多了吧

· · 题解

读完题：这不就是个多米诺骨牌。。。

我们先求出 k=1 时的通项公式，这会方便后面求解。

对于 m=2 的情况，设 f_n 表示长度为 n 的答案，可以发现最后的位置要么放竖着的牌，要么放横着的牌，而后面的情况是递归的，因此列出递归式 f_n=f_{n-1}+f_{n-2} 以及初始情况 f_1=1,f_2=2。因此得到通项公式

f_n=\mathrm{fib}_ {n+1}=\dfrac{5+\sqrt 5}{10}\cdot\left(\dfrac{1+\sqrt 5}{2}\right)^n+\dfrac{5-\sqrt 5}{10}\cdot\left(\dfrac{1-\sqrt 5}{2}\right)^n

对于 m=3 的情况，我们可以使用生成函数的思想，设 U_n 表示长为 n 的完美覆盖答案、V_n 为长为 n、抠去右下角位置的完美覆盖方案。那么显然有边界条件

U_0=1,U_1=0,V_0=0,V_1=1

考虑建立递归关系，容易得到

\begin{cases} U_n=2V_{n-1}+U_{n-2}\\ V_n=U_{n-1}+V_{n-2} \end{cases}

联立解生成函数我们可以得到

U(z)=\dfrac{1-z^2}{1-4z^2+z^4},V(z)=\dfrac{z}{1-4z^2+z^4}

解出 U_n：

U_{2n}=\dfrac{3+\sqrt 3}{6}(2+\sqrt 3)^n+\dfrac{3-\sqrt 3}{6}(2-\sqrt 3)^n

我们观察到上面的式子都有形式 a_n=A\alpha^n+B\beta^n 的形式，因此我们将这个一般形式带入求值公式中。

欲求的答案为

\dfrac1{r-l+1}\sum_{i=l}^r\dbinom{a_i}k

化简求和式可以得到

\begin{aligned} \sum_{i=l}^r\dbinom{a_i}k&=\dfrac1{k!}\sum_{i=l}^ra_i^{\underline k}\\ &=\dfrac1{k!}\sum_{i=l}^r\sum_{j=0}^k{k\brack j}(-1)^{k-j}a_i^j\\ &=\dfrac1{k!}\sum_{j=0}^k{k\brack j}(-1)^{k-j}\sum_{i=l}^r\sum_{p=0}^j\dbinom jpA^pB^{j-p}\alpha^{pi}\beta^{(j-p)^i}\\ &=\dfrac1{k!}\sum_{j=0}^k{k\brack j}(-1)^{k-j}\sum_{p=0}^j\dbinom jpA^pB^{j-p}\sum_{i=l}^r(\alpha^{p}\beta^{j-p})^i \end{aligned}

此时对 i 求和的那一维是等比数列求和，可以直接计算。

观察到通项公式内带有大量 \sqrt 5、\sqrt 3 一类在模 998244353 意义下不存在的值，因此直接扩域即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define mod 998244353
#define N 550
il ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
ll i_square;
struct complex {
    ll re,im;
    complex() {re=im=0;}
    complex(ll _re,ll _im) {re=_re,im=_im;}
};
il complex operator +(complex a,complex b) {return complex((a.re+b.re)%mod,(a.im+b.im)%mod);}
il complex operator -(complex a) {return complex((mod-a.re)%mod,(mod-a.im)%mod);}
il complex operator -(complex a,complex b) {return a+(-b);}
il complex operator *(complex a,complex b) {return complex((a.re*b.re%mod+i_square*a.im*b.im%mod)%mod,(a.im*b.re%mod+a.re*b.im%mod)%mod);}
il complex operator *(complex a,ll b) {return complex(a.re*b%mod,a.im*b%mod);}
il complex operator *(ll b,complex a) {return complex(a.re*b%mod,a.im*b%mod);}
il complex Conj(complex a) {a.im=(mod-a.im)%mod;return a;}
il ll qpow(ll a,ll b) {ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
il complex qpow(complex a,ll b) {
    complex ans(1,0);
    for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;return ans;
}
ll C[N][N],S[N][N],fac[N],t,m;
complex A,B,alpha,beta;
il void pre_init(int m) {
    if(m==2) {
        i_square=5;
        A=complex(qpow(2,mod-2),qpow(10,mod-2)),B=Conj(A);
        alpha=complex(qpow(2,mod-2),qpow(2,mod-2)),beta=Conj(alpha);
    }
    else {
        i_square=3;
        A=complex(qpow(2,mod-2),qpow(6,mod-2)),B=Conj(A);
        alpha=complex(2,1),beta=Conj(alpha);
    }
}
il void init_CS(int n) {
    C[0][0]=1;for(int i=1;i<=n;i++) C[i][0]=1;
    S[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=i;j++) {
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
            S[i][j]=((i-1)*S[i-1][j]+S[i-1][j-1])%mod;
        }
    }
    fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
}
il complex Inv(complex a) {
    return Conj(a)*qpow((a.re*a.re%mod-i_square*a.im*a.im%mod+mod)%mod,mod-2);
}
il complex Add(complex bas,ll n) {
    if(bas.re==1&&bas.im==0) {return complex(n%mod,0);}
    complex tmp=qpow(bas,n+1)-complex(1,0);
    return tmp*Inv(bas-complex(1,0));
}
il void mian() {
    ll l=read(),r=read(),k=read();
    complex ans(0,0);
    for(int j=0;j<=k;j++) {
        for(int p=0;p<=j;p++) {
            complex now=C[j][p]*qpow(A,p)*qpow(B,j-p),bas=qpow(alpha,p)*qpow(beta,j-p);
            complex sum;
            if(m==2) sum=Add(bas,r)-Add(bas,(l-1));
            else sum=Add(bas,r/2)-Add(bas,(l-1)/2);
            if((k-j)%2==0) ans=ans+S[k][j]*now*sum;
            else ans=ans-S[k][j]*now*sum;
        }
    }
    ans=ans*qpow(fac[k],mod-2);
    printf("%lld\n",ans.re*qpow((r-l+1)%mod,mod-2)%mod);
}
int main() {
    t=read(),m=read();
    pre_init(m);
    init_CS(510);
    while(t--) mian();
    return 0;
}

UPD on 2024.10.28：公式里 (-1)^{k-j} 忘写了，正确的公式是

n^{\underline k}=\sum_{i=0}^k{k\brack i}(-1)^{k-i}n^i