Luogu

LOJ

分析

显然二合一，先考虑 $m=2$ 的情况。

可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求
$$
\frac{1}{r-l+1}\sum_{n=l}^r{f_n\choose k}
$$
把组合数改成下降幂的形式
$$
\frac{1}{k!(r-l+1)}\sum_{n=l}^rf_n\!^{\underline{k}}
$$
用第一类斯特林数将下降幂展开
$$
\frac{1}{k!(r-l+1)}\sum_{n=l}^r\sum_{i=0}^k(-1)^{k-j}\begin{bmatrix}k\\i\end{bmatrix}f_n\!^i
$$
令 $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}},\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$，则 $f_n=A\alpha^n+B\beta^n$，代入并变形得到
$$
\frac{1}{k!(r-l+1)}\sum_{i=0}^k(-1)^{k-i}\begin{bmatrix}k\\i\end{bmatrix}\sum_{j=0}^i{i\choose j}A^iB^{i-j}\sum_{n=l}^r\alpha^{nj}\beta^{n(i-j)}
$$
后面的东西可以等比数列求和（注意特判公比为 $1$ 的情况），那么就可以 $\mathcal{O}(k^2\log p)$ 算了。

然而有一个问题是模 $998244353$ 意义下不存在 $\sqrt{5}$，所以需要扩域，即把每个数写成 $x+y\sqrt{5}$ 的形式运算。

再考虑 $m=3$ 的情况，通过一些推导可以知道
$$
g_{2n}=4g_{2(n-1)}-g_{2(n-2)}
$$
为了方便把下标除以 $2$ 同时令 $l\gets\lceil\frac{l}{2}\rceil,r\gets\lfloor\frac{r}{2}\rfloor$，可以解得
$$
g_n=\frac{3+\sqrt{3}}{6}(2+\sqrt{3})^n+\frac{3-\sqrt{3}}{6}(2-\sqrt{3})^n
$$
用同样的方法扩域计算即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=501+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int fac[N],C[N][N],S[N][N];

void init(int n) {
    for (int i=fac[0]=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for (int i=C[0][0]=1;i<=n;++i)
        for (int j=C[i][0]=1;j<=n;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    for (int i=S[0][0]=1;i<=n;++i)
        for (int j=1;j<=i;++j) S[i][j]=(S[i-1][j-1]+1ll*(i-1)*S[i-1][j])%mod;
}

namespace task2 {
    struct H { // x + y\sqrt{5}
        int x,y;
        H(int x_=0,int y_=0): x(x_),y(y_) {}
        H conj() { return H(x,mod-y); }
    };
    H operator +(H a,H b) { return H((a.x+b.x)%mod,(a.y+b.y)%mod); }
    H operator -(H a,H b) { return H((a.x-b.x+mod)%mod,(a.y-b.y+mod)%mod); }
    H operator *(H a,H b) { return H((1ll*a.x*b.x+5ll*a.y*b.y)%mod,(1ll*a.x*b.y+1ll*a.y*b.x)%mod); }
    H operator /(H a,H b) { return H((1ll*a.x*b.x+998244348ll*a.y%mod*b.y)%mod,(1ll*a.y*b.x+998244352ll*a.x%mod*b.y)%mod)*::qpow((1ll*b.x*b.x+998244348ll*b.y%mod*b.y)%mod,mod-2); }
    H qpow(H a,ll b) { H c(1,0);
        for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
        return c;
    }

    int calc(ll l,ll r,int k) {
        H A=H(0,1)/5,B=A.conj(),a=H(1,1)/2,b=a.conj(),res(0,0);
        for (int i=0;i<=k;++i)
            for (int j=0;j<=i;++j) {
                H q=qpow(a,j)*qpow(b,i-j);
                if (q.x==1&&!q.y) res=res+H((k-i)&1?mod-1:1)*S[k][i]*C[i][j]*qpow(A,j)*qpow(B,i-j)*((r-l+1)%mod);
                else res=res+H((k-i)&1?mod-1:1)*S[k][i]*C[i][j]*qpow(A,j)*qpow(B,i-j)*(qpow(q,r+1)-qpow(q,l))/(q-1);
            }
        return 1ll*res.x*::qpow(fac[k],mod-2)%mod;
    }
}

namespace task3 {
    struct H { // x + y\sqrt{3}
        int x,y;
        H(int x_=0,int y_=0): x(x_),y(y_) {}
        H conj() { return H(x,mod-y); }
    };
    H operator +(H a,H b) { return H((a.x+b.x)%mod,(a.y+b.y)%mod); }
    H operator -(H a,H b) { return H((a.x-b.x+mod)%mod,(a.y-b.y+mod)%mod); }
    H operator *(H a,H b) { return H((1ll*a.x*b.x+3ll*a.y*b.y)%mod,(1ll*a.x*b.y+1ll*a.y*b.x)%mod); }
    H operator /(H a,H b) { return H((1ll*a.x*b.x+998244350ll*a.y%mod*b.y)%mod,(1ll*a.y*b.x+998244352ll*a.x%mod*b.y)%mod)*::qpow((1ll*b.x*b.x+998244350ll*b.y%mod*b.y)%mod,mod-2); }
    H qpow(H a,ll b) { H c(1,0);
        for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
        return c;
    }

    int calc(ll l,ll r,int k) {
        H A=H(3,1)/6,B=A.conj(),a=H(2,1),b=a.conj(),res(0,0);
        for (int i=0;i<=k;++i)
            for (int j=0;j<=i;++j) {
                H q=qpow(a,j)*qpow(b,i-j);
                if (q.x==1&&!q.y) res=res+H((k-i)&1?mod-1:1)*S[k][i]*C[i][j]*qpow(A,j)*qpow(B,i-j)*((r-l+1)%mod);
                else res=res+H((k-i)&1?mod-1:1)*S[k][i]*C[i][j]*qpow(A,j)*qpow(B,i-j)*(qpow(q,r+1)-qpow(q,l))/(q-1);
            }
        return 1ll*res.x*::qpow(fac[k],mod-2)%mod;
    }
}

int main() {
    init(501);
    int T=read(),op=read();
    while (T--) {
        ll l=read(),r=read(); int k=read();
        if (op==2) printf("%d\n",1ll*task2::calc(l+1,r+1,k)*qpow((r-l+1)%mod,mod-2)%mod);
        else printf("%d\n",1ll*task3::calc((l+1)/2,r/2,k)*qpow((r-l+1)%mod,mod-2)%mod);
    }
    return 0;
}