CCPC-Wannafly Winter Camp Day8 (Div2, onsite) G 穗乃果的考试 容斥+求和公式展开

G - 穗乃果的考试

先对方块求一个二维前缀和，这样就相当于枚举前缀和中每一个小块的和了。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
char s[2200][2200];
ll a[2200][2200],sum[2200][2200];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",s[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[i][j]=s[i-1][j-1]-'0';

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

    ll ans=0;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)ans=(ans+sum[i][j]*(i*j))%mod;

    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)ans=(ans+sum[i][j]*(n-i)*(m-j))%mod;

    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)ans=(ans-sum[i][j]*i*(m-j))%mod;

    for(int i=0;i<=n;i++)
    for(int j=1;j<=m;j++)ans=(ans-sum[i][j]*((n-i)*j))%mod;

    while(ans<0)ans+=mod;
    printf("%lld\n",ans%mod);
    return 0;
}