题面

大力统计题

考虑把和的平方拆开，最终就是许多对位置乘起来求和。所以考虑每对位置的贡献，对于$a_{i,j}$和$a_{k,h}(1<=i<=k<=n,1<=j<=h<=m)$，它们的贡献就是在$a_{i,j}$左上角和$a_{k,h}$右下角选两个点构成一个矩形把两个位置框起来的方案数再乘上对应系数，所以一般来说其贡献为

$2*a_{i,j}*a_{k,h}*i*j*(n-k-1)*(m-h-1)$

用前缀和维护二维乘积的和$sum[i][j]$，就可以更新答案了：

$sum[i][j]=a[i][j]*i*j-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1]$

$ans+=2*a[i][j]*sum[i][j]*(n-i+1)*(m-j+1)$

但是平方项的系数都是1，所以对于每个位置$i,j$还要扣掉一个$a[i][j]*i*j*(n-i+1)*(m-i+1)$

还没完......我们上面为了好写默认$1<=i<=k<=n,1<=j<=h<=m$，然后就成功地把$i<=k,j>h$和$i>j,j<=h$的情况给漏掉了，所以还要把每行翻过来再算一次，注意这次没有等于号了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=5010,mod=998244353;
 6 long long n,m,ans,seed,a[N][N],sum[N][N];
 7 long long get() 
 8 {
 9     seed=(seed*9301+49297)%233280;
10     return seed%101;
11 }
12 int main() 
13 {
14     scanf("%lld%lld%lld",&n,&m,&seed);
15     for(int i=1;i<=n;i++)
16         for(int j=1;j<=m;j++) 
17         {
18             a[i][j]=get();
19             sum[i][j]=(a[i][j]*i*j%mod+mod-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1])%mod;
20             ans+=2*a[i][j]*sum[i][j]%mod*(n-i+1)*(m-j+1)%mod; ans%=mod;
21             ans+=mod-a[i][j]*a[i][j]%mod*i*j%mod*(n-i+1)*(m-j+1)%mod;
22         }
23     for(int i=1;i<=n;i++)
24         for(int j=1;j<=m/2;j++)
25             swap(a[i][j],a[i][m-j+1]);
26     for(int i=1;i<=n;i++)
27         for(int j=1;j<=m;j++) 
28         {
29             sum[i][j]=(a[i][j]*i*j%mod+mod-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1])%mod;
30             ans+=2*a[i][j]*sum[i-1][j-1]%mod*(n-i+1)*(m-j+1)%mod; ans%=mod;
31         }
32     printf("%lld",ans);
33     return 0;
34 }

View Code