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;
}