题意：f[i],g[i]分别表示用1*2的骨牌铺2*n和3*n网格的方案数，求ΣC(f(i),k)和ΣC(g(i),k)，对998244353取模，其中l<=i<=r，1<=l<=r<=1e18
题解：显然打表发现f[i]为斐波那契数列，g[2i+1]=0,g[2i]=4g[2i-2]-g[2i-4]。
然后考虑m=2的斐波那契部分：k是给定的，仅需求斐波那契数列的下降幂，然后可以用第一类斯特林数去转换，然后求斐波那契数列的幂之和，假设斐波那契数列的两个特征根为a,b，则f(n,k)=(An-Bn)k/(√5)k，然后可以用二项式定理展开，但模数太差是998244353，所以要扩域。其实这道题是一道原题，原题链接：CF717A
m=3，因为也是二阶递推式，所以解法是一样的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=,mod=;
int c[N][N],s[N][N];
int qpow(int a,ll b)
{
int ret=;
while(b)
{
if(b&)ret=1ll*ret*a%mod;
a=1ll*a*a%mod,b>>=;
}
return ret;
}
struct num{
int a,b,c;
num operator+(num x){return (num){(a+x.a)%mod,(b+x.b)%mod,c};}
num operator-(num x){return (num){(a-x.a+mod)%mod,(b-x.b+mod)%mod,c};}
num operator*(num x)
{return (num){(1ll*a*x.a+1ll*c*b%mod*x.b)%mod,(1ll*a*x.b+1ll*b*x.a)%mod,c};}
num inv()
{
int f=qpow((1ll*a*a-1ll*b*b%mod*c%mod+mod)%mod,mod-);
return (num){1ll*a*f%mod,1ll*(mod-b)*f%mod,c};
}
bool operator==(num x){return a==x.a&&b==x.b&&c==x.c;}
num operator/(num x){return (*this)*x.inv();}
};
num qpow(num a,ll b)
{
num ret=(num){,,a.c};
while(b)
{
if(b&)ret=ret*a;
a=a*a,b>>=;
}
return ret;
}
int F(ll n,int k)
{
if(!k)return n%mod;
n++;
num ans=(num){,,},A=(num){,,}/(num){,,},B=(num){,mod-,}/(num){,,};
num x=(num){,,},y=(num){,,};
for(int j=;j<=k;j++)y=y*B;
for(int j=;j<=k;j++)
{
int ret=c[k][j];
if(k-j&)ret=(mod-ret)%mod;
num t=x*y;
if(t==(num){,,})ans=ans+(num){n%mod*ret%mod,,};
else ans=ans+(num){ret,,}*(qpow(t,n+)-t)/(t-(num){,,});
x=x*A,y=y/B;
}
for(int j=;j<=k;j++)ans=ans/(num){,,};
return (ans.a+mod-)%mod;
}
int calf(ll n,int k)
{
if(!n)return ;
int ret=,sum;
for(int j=;j<=k;j++)
sum=1ll*F(n,j)*s[k][j]%mod,ret=(k-j&)?(ret-sum+mod)%mod:(ret+sum)%mod;
for(int i=;i<=k;i++)ret=1ll*ret*qpow(i,mod-)%mod;
return ret;
}
int G(ll n,int k)
{
if(!k)return n%mod;
num ans=(num){,,},x1=(num){,,},x2=(num){,mod-,};
num A=(num){,,},B=(num){,mod-,},x=(num){,,},y=x,a=x,b=x;
for(int j=;j<=k;j++)y=y*x2,b=b*B;
for(int j=;j<=k;j++)
{
int ret=c[k][j];
num t=x*y;
if(t==(num){,,})ans=ans+a*b*(num){n%mod*ret%mod,,};
else ans=ans+(num){ret,,}*a*b*(qpow(t,n+)-t)/(t-(num){,,});
x=x*x1,y=y/x2,a=a*A;b=b/B;
}
for(int j=;j<=k;j++)ans=ans/(num){,,};
return ans.a;
}
int calg(ll n,int k)
{
if(!n)return ;
n/=;
int ret=,sum;
for(int j=;j<=k;j++)
sum=1ll*G(n,j)*s[k][j]%mod,ret=(k-j&)?(ret-sum+mod)%mod:(ret+sum)%mod;
for(int i=;i<=k;i++)ret=1ll*ret*qpow(i,mod-)%mod;
return ret;
}
int main()
{
for(int i=;i<=;i++)
{
c[i][]=;
for(int j=;j<=i;j++)c[i][j]=(c[i-][j]+c[i-][j-])%mod;
}
s[][]=;
for(int i=;i<=;i++)
for(int j=;j<=i;j++)
s[i][j]=(s[i-][j-]+1ll*(i-)*s[i-][j])%mod;
int T,m;scanf("%d%d",&T,&m);
while(T--)
{
ll l,r;int k;cin>>l>>r>>k;
int ans=m==?(calf(r,k)-calf(l-,k)+mod)%mod:(calg(r,k)-calg(l-,k)+mod)%mod;
ans=1ll*ans*qpow((r-l+)%mod,mod-)%mod;
printf("%d\n",ans);
}
}