题解 P7140 【[THUPC2021 初赛]区间矩阵乘法】

· · 题解

题意清晰思路简单码量少好评，卡常一万年 -9 差评。

成为了相同题目数量下罚时（可能）最长的队伍，顺便水一水题解。

似乎是目前的最优解，但估计马上就不是了（

题意很简单就是给一个序列， 每次询问给出 d,p_1,p_2，让你求这个玩意：

\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}\sum_{k=0}^{d-1}a_{p_1+d\cdot i+j}\times a_{p_2+d\cdot j+k}

(第一遍看成了 a_{p_1}+d\cdot i+ja_{p_2}+d\cdot j+k，然后愣了三秒（笑

首先是发现 k 与 a_{p_1+d\cdot i+j} 无关，然后就可以把式子变成这个形式：

\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}a_{p_1+d\cdot i+j}\times \sum_{k=0}^{d-1}a_{p_2+d\cdot j+k}

然后维护一个前缀和 sum，式子就变成了：

\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}a_{p_1+d\cdot i+j}\times (sum_{p2+d(j+1)-1}-sum_{p2+d\cdot j-1})

然后做到这里发现很难再继续化简，爬回去重新读题，发现询问保证 a 的下标在 [1,n] 内，而不是多余的下标不予计算。

这样的话，当 j=k=d-1 时，a_{p_2+d\cdot j+k}=a_{p_2+d(d-1)+d-1}=a_{p_2+d^2}；当 j=k=0 时，a_{p_2+d\cdot j+k}=a_{p_2}。然后又保证了下标在 [1,n] 内，所以 p_2+d^2∈[1,n]，p_2∈[1,n]。所以 d∈[1,\sqrt{n-1}]（所有数值为 [1,{10}^9] 以内的整数）。

所以维护一个 s_{i,j} 表示：

s_{i,j}=\sum_{k=0}^{\lfloor \frac{j-1}{i} \rfloor}a_{j-ki}

意义通俗一点说就是，从 j 到 1 的“隔 i 个的”前缀和。

显然，这个 s 递推的话就是：

a_j&1 \leq j\leq i\\ s_{i,j-i}&i< j \leq n \end{cases}

这样的话这个式子继续化简，发现只有 a_{p_1+d\cdot i+j} 含有 i 这一项，用同样的套路把它提出来：

\sum_{j=0}^{d-1}(sum_{p_2+d(j+1)-1}-sum_{p_2+d\cdot j-1})\times \sum_{i=0}^{d-1}a_{p_1+d\cdot i+j}

然后用维护的 s_{i,j} 改写一下：

\sum_{j=0}^{d-1}(sum_{p_2+d(j+1)-1}-sum_{p_2+d\cdot j-1})(s_{d,p_1+d(d-1)+j}-s_{d,p_1+j}+a_{p_1+j})

这样单次询问直接暴力枚举 j，做到 \mathcal{O}(d) 的复杂度。这种做法的时间复杂度为 \mathcal{O}(m \sqrt{n})，可以通过本题。

#include <bits/stdc++.h>
#define rgi register int
using namespace std;
namespace IO{
#define getchar() (P1_==P2_&&(P2_=(P1_=Ibuf)+fread(Ibuf,1,1<<21,stdin),P1_==P2_)?EOF:*P1_++)
#define putchar(c) (O-Obuf<8388608)?(*O++=c):(fwrite(Obuf,O-Obuf,1,stdout),O=Obuf,*O++=c)
    char Ibuf[8388608],*P1_=Ibuf,*P2_=Ibuf,Obuf[8388608],*O=Obuf;
    int f,ch,Onum[32],Ohd;long long K_;
    template<typename T>inline void read(T&x){
        x=f=ch=0;while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        f&&(x=-x);
    }
    template<typename T>inline void write(T x){
        if(x==0)return putchar('0'),void();
        if(x<0)putchar('-'),x=-x;
        while(x>0)K_=x/10,Onum[++Ohd]=(x-(K_<<1)-(K_<<3))^'0',x=K_;
        while(Ohd>0)putchar(Onum[Ohd]),--Ohd;
    }
    inline void _Exit0(){
        fwrite(Obuf,O-Obuf,1,stdout),exit(0);
    }
}using namespace IO;
int Block,n,m,p1,p2,d;
unsigned int a[200010],ans;
unsigned int s[450][200010],sum[200010];
int main(){
    read(n),Block=sqrt(n);
    for(rgi i=1;i<=n;++i)read(a[i]),sum[i]=sum[i-1]+a[i];
    for(rgi i=1;i<=Block;++i){
        for(rgi j=1;j<=i;++j)s[i][j]=a[j];
        for(rgi j=i+1;j<=n;++j)s[i][j]=s[i][j-i]+a[j];
    }
    read(m);
    for(rgi t=1;t<=m;++t){
        read(d),read(p1),read(p2),ans=0;
        for(rgi j=0;j<d;++j)ans+=(s[d][p1+(d-1)*d+j]-s[d][p1+j]+a[p1+j])*(sum[p2+d*(j+1)-1]-sum[p2+d*j-1]);
        write(ans),putchar('\n');
    }
    _Exit0();
}