题目链接
解析
我们先分析 (m=2) 的情况。不难发现 (F(n,k)={f_nchoose k}) ，其中 (f_n) 表示斐波那契数列第 (n+1) 项。由于 (nchoose x) 展开之后实际上是一个关于 (x) 的 (n) 次多项式，不妨设 (i) 次项系数为 (a_i)（可以通过暴力展开成下降幂计算），并将斐波那契数列的通项公式带入，我们可以化简得到：
[egin{align}
sum_{i=l}^rF(i,k) &= sum_{i=0}^k a_isum_{d=l+1}^{r+1}f_d^i\
&=sum_{i=0}^k a_isum_{d=l+1}^{r+1}[frac{1}{sqrt{5}}(frac{1+sqrt{5}}{2})^d-frac{1}{sqrt{5}}(frac{1-sqrt{5}}{2})^d]^i\
&=sum_{i=0}^kfrac{a_i}{(sqrt{5})^i}sum_{d=l+1}^{r+1}sum_{j=0}^i{ichoose j}(frac{1+sqrt{5}}{2})^{dj}(frac{1-sqrt{5}}{2})^{d(i-j)}(-1)^{i-j}\
&=sum_{i=0}^kfrac{a_i}{(sqrt{5})^i}sum_{j=0}^i{ichoose j}(-1)^{i-j}sum_{d=l+1}^{r+1}(frac{1+sqrt{5}}{2})^{dj}(frac{1-sqrt{5}}{2})^{d(i-j)}
end{align}
]
最后面一部分是一个等比数列求和，直接计算即可。
再来看 (m=3) 的情况。当 (n) 为奇数时无解；当 (n) 为偶数时可以得到递推式：(g_n=4g_{n-1}-g_{n-2})，其中 (g_n) 表示长度为 (2n) 时的方案数。我们可以计算出它的通项公式：
[g_n=frac{3+sqrt{3}}{6}(2+sqrt{3})^n+frac{3-sqrt{3}}{6}(2-sqrt{3})^n
]
然后就可以用上面一样的方法解决这个问题了。要注意的是无理数取模是没有意义的，因此我们需要将每一个数都表示成 (a+bsqrt{i}) 的形式，然后就可以对 (a) 和 (b) 进行取模运算了。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 503
using namespace std;
const int mod=998244353;
int T,m,l,r,k,fac,i,j,c[N][N],a[N],tmp[N];
struct node{
int a,b,i;
node(){}
node(int _a,int _b,int _i){
a=_a;b=_b;i=_i;
}
};
int poww(int a,int b)
{
int ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
node operator + (node a,node b)
{
a.a=(a.a+b.a)%mod;
a.b=(a.b+b.b)%mod;
return a;
}
node operator - (node a,node b)
{
a.a=(a.a-b.a+mod)%mod;
a.b=(a.b-b.b+mod)%mod;
return a;
}
node operator * (node a,node b)
{
node c;
c.a=(a.a*b.a%mod+a.b*b.b%mod*a.i%mod)%mod;
c.b=(a.b*b.a%mod+a.a*b.b%mod)%mod;
c.i=a.i;
return c;
}
node operator / (node a,node b)
{
node c=a*node(b.a,mod-b.b,b.i);
int inv=poww((b.a*b.a%mod-b.b*b.b%mod*b.i%mod+mod)%mod,mod-2);
c.a=c.a*inv%mod;c.b=c.b*inv%mod;
return c;
}
node poww(node a,int b)
{
node ans=node(1,0,a.i),base=a;
while(b){
if(b&1) ans=ans*base;
base=base*base;
b>>=1;
}
return ans;
}
node cal(node q,int n)
{
if(q.a==1&&q.b==0) return node(n%mod*q.a%mod,0,q.i);
node ans=node(1,0,q.i)-poww(q,n);
node tmp=node(1,0,q.i)-q;
ans=ans/tmp;ans=ans*q;
return ans;
}
signed main()
{
scanf("%lld%lld",&T,&m);
while(T--){
scanf("%lld%lld%lld",&l,&r,&k);
c[0][0]=fac=1;
for(i=1;i<=k;i++){
c[i][0]=1;fac=fac*i%mod;
for(j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
a[0]=1;
for(i=0;i<k;i++){
for(j=0;j<=i;j++) tmp[j+1]=a[j];
for(j=0;j<=i;j++) tmp[j]=(tmp[j]-i*a[j]%mod+mod)%mod;
for(j=0;j<=i+1;j++) a[j]=tmp[j],tmp[j]=0;
}
for(i=0;i<=k;i++) a[i]=a[i]*poww(fac,mod-2)%mod;
int ans=0;
if(m==2){
int inv2=poww(2,mod-2),inv5=poww(5,mod-2);
for(i=0;i<=k;i++){
node tmp=node(0,0,5);
for(j=0;j<=i;j++){
node q=poww(node(inv2,inv2,5),j)*poww(node(inv2,mod-inv2,5),i-j);
node res=cal(q,r+1)-cal(q,l);
res.a=res.a*c[i][j]%mod;res.b=res.b*c[i][j]%mod;
if((i-j)%2!=0) res.a=mod-res.a,res.b=mod-res.b;
tmp=tmp+res;
}
tmp=tmp*poww(node(0,inv5,5),i);
ans=(ans+a[i]*tmp.a%mod)%mod;
}
}
else{
int inv6=poww(6,mod-2),l1=l/2+l%2,r1=r/2;
for(i=0;i<=k;i++){
node tmp=node(0,0,3);
for(j=0;j<=i;j++){
node q=poww(node(2,1,3),j)*poww(node(2,mod-1,3),i-j);
node res=cal(q,r1)-cal(q,l1-1);
res=res*poww(node(3*inv6%mod,inv6,3),j);
res=res*poww(node(3*inv6%mod,mod-inv6,3),i-j);
res.a=res.a*c[i][j]%mod;res.b=res.b*c[i][j]%mod;
tmp=tmp+res;
}
ans=(ans+a[i]*tmp.a%mod)%mod;
}
}
printf("%lld
",ans*poww((r-l+1)%mod,mod-2)%mod);
}
return 0;
}