#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=3e5+7;
const int Mod=998244353;
int n,k,Q;
int a[Maxn];
ll f[Maxn][110];

namespace IO{
    template<typename T>
    inline void qread(T &x){
        char ch;int f=1;
        while((ch=getchar())&&(ch>'9'||ch<'0')) if(ch=='-') f=-1;x=(ch^48);
        while((ch=getchar())&&(ch>='0'&&ch<='9')) x=(x<<1)+(x<<3)+(ch^48);
        x*=f;
    }
    template<typename T>
    void write(T x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10); 
        putchar('0'+x%10);
    }
};
using namespace IO;

struct ques{
    int l,r,id;
    ques(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
};
int ans[Maxn];

inline int mod(int x){
    return (x%k+k)%k;
}
void solve(vector<ques>q,int l,int r){
    if(!q.size()) return ;
    if(l==r){
        for(auto i:q) ans[i.id]=(a[l]==0)+1;
        return ;
    }
    int mid=l+r>>1;
    vector<ques>q1,q2,q3;
    for(auto i:q){
        if(i.l>mid) q1.emplace_back(i);
        else if(i.r<=mid) q2.emplace_back(i);
        else q3.emplace_back(i);
    }
    for(int i=0;i<k;i++) f[mid][i]=f[mid+1][i]=0;
    f[mid][0]=f[mid+1][0]=1;
    f[mid][a[mid]]++,f[mid+1][a[mid+1]]++;
    for(int i=mid-1;i>=l;i--){
        for(int j=0;j<k;j++)
            f[i][j]=(f[i+1][j]+f[i+1][mod(j-a[i])])%Mod;
    }
    for(int i=mid+2;i<=r;i++){
        for(int j=0;j<k;j++)
            f[i][j]=(f[i-1][j]+f[i-1][mod(j-a[i])])%Mod;
    }
    
    for(auto i:q3){
        ll ret=0;
        for(int j=0;j<k;j++)
            ret=(ret+f[i.l][j]*f[i.r][(k-j)%k]%Mod)%Mod;
        ans[i.id]=ret;
    }

    solve(q1,mid+1,r);solve(q2,l,mid);
}

vector<ques>q;

int main(){
    qread(n),qread(k);
    for(int i=1;i<=n;i++) qread(a[i]);
    qread(Q);
    for(int i=1;i<=Q;i++){
        int l,r;
        qread(l),qread(r);
        q.emplace_back(ques(l,r,i));
    }
    solve(q,1,n);

    for(int i=1;i<=Q;i++) write(ans[i]),putchar(' ');

    return 0;
}

题目：https://acm.hdu.edu.cn/showproblem.php?pid=7421

TLE 了