分析

分析题意，我们可以发现它就是要让求 。而 是可以线性筛求出来的。所以现在问题就是如何维护矩阵中的 。因为 ，所以可以考虑二维莫队这样的时间复杂度为 。这道题卡空间，要注意线性筛时可以不用额外数组记录 。

后话

关于牛客挑战赛42的题就算补完了，可以说这套题还是不错的，只是有些题面稍微卡空间，题目本身不是太难，但融合和了各个方面的知识，大赞。

代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
const int N = 90,M = N*N*N*N,mod = 998244353;
int qpow(int x,int b) {
    int a = 1;for(;b;b>>=1,x = 1LL * x * x % mod) {
        if(b&1) a = 1LL * a * x % mod;
    }
    return a;
}
int a[N][N],n,m,limit,p[5000000],b[M],tot,pos[N];
int id[M],ans,Ans[100002],C[N*N];
struct Query{int l,r,u,d,id;}q[100002];
bool cmp(Query x,Query y) {
    if(pos[x.l] != pos[y.l]) return x.l < y.l;
    if(pos[x.r] != pos[y.r]) return x.r < y.r;
    if(pos[x.u] != pos[y.u]) return x.u < y.u;
    return x.d < y.d;
}
void add(int x) {
    if(C[x] == 0) ans = (1LL * ans + (mod - id[b[x]]) % mod + mod) % mod;
    C[x]++; 
}
void del(int x) {
    if(C[x] == 1) ans = (1LL * ans + id[b[x]] + mod) % mod;
    C[x]--;
}
void work() {
    ans = id[1] = 1;
    for(int i = 2;i <= limit;i++) {
        if(!id[i]) p[++p[0]] = i,id[i] = qpow(i,limit);
        for(int j = 1;j <= p[0] && p[j] * i <= limit;j++) {
            id[i * p[j]] = 1LL * id[p[j]] * id[i] % mod;
            if(!(i % p[j])) break;
        }
        ans = (ans + id[i]) % mod;
    }
}
int main()
{
    n = read();limit = read();
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            a[i][j] = read();b[++tot] = a[i][j];
        }
    }
    sort(b+1,b+1+tot);tot = unique(b+1,b+1+tot) - b - 1;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            a[i][j] = lower_bound(b+1,b+1+tot,a[i][j]) - b;
        }
    }
    work();
    m = read();
    int block = sqrt(n-1) + 1;
    for(int i = 1;i <= n;i++) pos[i] = (i-1)/block + 1;
    for(int i = 1;i <= m;i++) {
        int x = read(),y = read(),X = read(),Y = read();
        q[i].l = min(y,Y);q[i].r = max(y,Y);
        q[i].u = min(x,X);q[i].d = max(x,X);q[i].id = i;
    }
    sort(q + 1,q + 1 + m,cmp);
    for(int l = 1,u = 1,r = 0,d = 0,i = 1;i <= m;i++) {
        while(l > q[i].l) {l--;for(int j = u;j <= d;j++) add(a[j][l]);}
        while(r < q[i].r) {r++;for(int j = u;j <= d;j++) add(a[j][r]);}
        while(u > q[i].u) {u--;for(int j = l;j <= r;j++) add(a[u][j]);}
        while(d < q[i].d) {d++;for(int j = l;j <= r;j++) add(a[d][j]);}
        while(l < q[i].l) {for(int j = u;j <= d;j++) del(a[j][l]);l++;}
        while(r > q[i].r) {for(int j = u;j <= d;j++) del(a[j][r]);r--;}
        while(u < q[i].u) {for(int j = l;j <= r;j++) del(a[u][j]);u++;}
        while(d > q[i].d) {for(int j = l;j <= r;j++) del(a[d][j]);d--;}
        Ans[q[i].id] = ans;
    }
    for(int i = 1;i <= m;i++) printf("%d\n",(Ans[i]+mod)%mod);
    return 0;
}