T1 jump
考虑 \(dp\)，记录两条路径中相邻的位置，以及用过的 \(A\) 的次数差。
考虑 \(A\) 的种类数不会很多，根据裴蜀定理，合法的解一定是一个特解加上若干 \(lcm(A,B)\)，考虑把 \(A,B,n\) 都除以 \(gcd(A,B)\)，因为这些点不可能跳到。那么\(lcm(A,B)=A*B\)，也就是说，暴力的复杂度是 \(O(nB\frac{n}{AB})=O(n^2/A)\)
T2 graph
考虑没有 \(l,r\) 的情况。
考虑一个暴力，\(f_{t,i}\) 表示跳了 \(t\) 步位于位置 \(i\) 的路径条数，可以发现，如果往后跳 \(m\) 步，那么 \(f_{t,i}\) 对 \(f_{t+m,j}\) 的贡献系数为 $1+[i=j] $ 。
这也就是说，如果每次跳 \(m\) 步，任意时刻全局只有一个时刻和别的不一样，
最后的 \(n\% m\) 步可以考虑一个数跳任意步可以到的数(不取模)是一段区间，那么取模之后就是连续的了，贡献可以 \(O(1)\) 计算。
接下来考虑有 \([l,r]\) 的情况，这等价于：对于每个 \(x\)，先算出走 \(x\) 步到每个点的方案数，然后保留点位于 \([l,r]\) 的方案数，在以这个为初始值乘上到终点的路径数。
我们把这个过程分成前半部分和后半部分，前半部分可以用先暴力跳\(x\% m\) 步，再跳 \(x/m\) 个 \(m\)。
根据上面的过程可以得知，跳完 \(x\%m\) 步之后，方案数一定是，某一段区间和其他不一样。并且跳 \(x/m\) 不改变这个区间，且这个区间是什么只和 \(x\% m\) 有关。
在跳到 \(x\) 之后，\(dp\) 数组会被 \([l,r]\) 划分成最多三个区间 \([l_i,r_i]\) 满足每个区间内的 \(dp\) 值是相等的。接着，我们每次跳 \(m\) 步，特殊区间是不变的，最后的若干步暴力跳。
我们考虑枚举 \(x\%m\)，然后对于被划分出来的每个区间 \([l_i,r_i]\) 单独计算答案。
记录 \(f[i][2]\) 表示考虑了前\(i\) 步，是否已经走到 \(x\) 的方案数，以及 \(add\) 表示已经走到 \(x\) 的所有方案的特殊区间比普通区间的增量的和。
可以用矩阵乘法计算，复杂度 \(O(Tm4^3\log n)\)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,l,r,s,t;
const int mod = 998244353;
int Ans[4],Mat[4][4],Tmp[4][4];
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return (x+y>=mod?x+y-mod:x+y);}
inline int sub(int x,int y){return (x-y<0?x-y+mod:x-y);}
void Mul1()
{
for(int k=0;k<4;k++)
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
Tmp[i][j]=(Tmp[i][j]+1ll*Mat[i][k]*Mat[k][j]%mod)%mod;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
Mat[i][j]=Tmp[i][j],Tmp[i][j]=0;
}
void Mul2()
{
for(int k=0;k<4;k++)
for(int j=0;j<4;j++)
Tmp[0][j]=(Tmp[0][j]+1ll*Ans[k]*Mat[k][j]%mod)%mod;
for(int k=0;k<4;k++)
Ans[k]=Tmp[0][k],Tmp[0][k]=0;
}
void Pow(int K)
{
while(K)
{
if(K&1)Mul2();
Mul1();
K>>=1;
}
}
//K:[Odd,New,Add,1] [1, len, 1, 0]->[Odd,New,Add,1]
// [0, 1, 0 0]
// [0, len, 1 0]
// [K*len,0?K*len,0?K,1]
int calc(int ql,int qr,int D,int M,int t)
{
LL L=((LL)ql<<D),R=((LL)qr<<D)+(1ll<<D)-1;
LL res=R/M+(R%M>=t);
if(L)
{
L--;
res-=L/M+(L%M>=t);
}
return res%mod;
}
int ans=0;
void gener(int M,int ql,int qr,int L,int B,int K,int opt,int rem)
{
//printf("gener(%d,%d,%d,%d)\n",ql,qr,L,B);
L=(L%mod+mod)%mod;
int len=((qr-ql+1)%mod+mod)%mod;
K=(K%mod+mod)%mod;
//2^m-1,li-ri+1,r-l+1,opt
Ans[0]=B; Ans[1]=0; Ans[2]=add(B,mul(K,opt)); Ans[3]=1;
Mat[0][0]=M+1; Mat[0][1]=0; Mat[0][2]=M+1; Mat[0][3]=0;
Mat[1][0]=0; Mat[1][1]=M+1; Mat[1][2]=0; Mat[1][3]=0;
Mat[2][0]=0; Mat[2][1]=len; Mat[2][2]=1; Mat[2][3]=0;
Mat[3][0]=mul(K,L); Mat[3][1]=0; Mat[3][2]=mul(K,L); Mat[3][3]=1;
if(opt==1) Mat[3][2]=add(Mat[3][2],K);
Pow(rem/m);
rem%=m;
//cout<<Ans[1]<<' '<<Ans[2]<<endl;
ans=(ans+1ll*Ans[1]*calc(0,M-1,rem,M,t)%mod)%mod;
ans=(ans+1ll*Ans[2]*calc(ql,qr,rem,M,t)%mod)%mod;
}
void solve()
{
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&l,&r);
ans=0;
int M = (1<<m)-1;
int res=0;
for(int R=0;R<m&&R<=n;R++)
{
LL vl=((LL)s<<R),vr=vl+(1ll<<R)-1;
int W=(vr/M-vl/M+mod)%mod;
//printf("vl=%d,vr=%d\n",vl,vr);
if(vl%M<=vr%M)
{
int ql=vl%M,qr=vr%M;
if(l<ql) gener(M,l,min(ql-1,r),qr-ql+1,W,1,0,n-R);
if(r>qr) gener(M,max(qr+1,l),r,qr-ql+1,W,1,0,n-R);
if(r>=ql&&l<=qr) gener(M,max(ql,l),min(qr,r),qr-ql+1,W,1,1,n-R);
}
else if(vr%M+1<=vl%M-1)
{
int ql=vr%M+1,qr=vl%M-1;
if(l<ql) gener(M,l,min(ql-1,r),qr-ql+1,W,-1,0,n-R);
if(r>qr) gener(M,max(qr+1,l),r,qr-ql+1,W,-1,0,n-R);
if(r>=ql&&l<=qr) gener(M,max(ql,l),min(qr,r),qr-ql+1,W,-1,1,n-R);
}
else gener(M,l,r,M,0,W,1,n-R);
//cout<<R<<' '<<ans<<endl;
}
printf("%d\n",ans);
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}