题解

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=505,P=998244353,inv2=499122177,inv6=166374059;
int T,m,k,V,s[N][N],fac[N],ifac[N];
int add(int x,int y) {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y) {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y) {return 1llxy%P;}
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a);
return ans;
}
struct num{
int x,y;
num(int _x=0,int _y=0):x(_x),y(_y){}
friend num operator+(const num &a,const num &b) {return num(add(a.x,b.x),add(a.y,b.y));}
friend num operator-(const num &a,const num &b) {return num(dec(a.x,b.x),dec(a.y,b.y));}
friend num operator-(const num &a,int b) {return num(dec(a.x,b),a.y);}
friend num operator*(const num &a,int b) {return num(mul(a.x,b),mul(a.y,b));}
friend num operator*(const num &a,const num &b){
return num(add(mul(a.x,b.x),1llVmul(a.y,b.y)%P),add(mul(a.x,b.y),mul(a.y,b.x)));
}
friend num Inv(const num &a){
return num(a.x,P-a.y)power(dec(mul(a.x,a.x),1llVmul(a.y,a.y)%P),P-2);
}
friend num power(num a,ll b){
num ans=num(1,0);
for(;b;b>>=1,a=aa) if(b&1) ans=ans*a;
return ans;
}
}A,B,X,Y;
void prework(){
fac[0]=fac[1]=1;
for(int i=2;i<N;++i) fac[i]=mul(fac[i-1],i);
ifac[N-1]=power(fac[N-1],P-2);
for(int i=N-2;~i;--i) ifac[i]=mul(ifac[i+1],i+1);
s[0][0]=1;
for(int i=1;i<N;++i)
for(int j=1;j<N;++j)
s[i][j]=add(s[i-1][j-1],mul(i-1,s[i-1][j]));
}
int C(int n,int m) {return n<m?0:mul(fac[n],mul(ifac[m],ifac[n-m]));}
void init(){
if(m2){
V=5;
X=num(inv2,inv2),Y=num(inv2,P-inv2),A=Inv(num(0,1)),B=Inv(num(0,P-1));
}
else{
V=3;
X=num(2,1),Y=num(2,P-1),A=num(inv2,inv6),B=num(inv2,P-inv6);
}
}
ll l,r,L,R;
int solve(){
int ans=0;
for(int i=0;i<=k;++i){
int res=0,tmp=((k-i)&1)?(P-s[k][i]):s[k][i];
for(int j=0;j<=i;++j){
num val1=power(A,j)*power(B,i-j)*C(i,j),val2=power(X,j)*power(Y,i-j);
val2=(val2.x1&&val2.y0)?num((r-l+1)%P,0):(power(val2,r+1)-power(val2,l))Inv(val2-1);
res=add(res,(val1val2).x);
}
ans=add(ans,mul(res,tmp));
}
return mul(mul(ans,ifac[k]),power((R-L+1)%P,P-2));
}
int main(){
prework();
scanf("%d%d",&T,&m),init();
while(T--){
scanf("%lld%lld%d",&L,&R,&k);
(m2)?(l=L+1,r=R+1):(l=(L+1)/2,r=R/2);
printf("%d\n",solve());
}
return 0;
}