CCPC-Wannafly Winter Camp Day7 (Div2, onsite) G 穗乃果的考试（二维前缀和，求和公式展开）

怼烎@ 2021-09-17 23:36 121阅读 0赞

**1**.二维前缀和  
**2**.求和公式展开  
 ∑ i = 1 n ∑ j = 1 i f i ∗ g j = ∑ j = 1 n ∑ i = j n f i ∗ g j \\sum\_\{i=1\}^n \\sum\_\{j=1\}^i f\_i \* g\_j= \\sum\_\{j=1\}^n \\sum\_\{i=j\}^n f\_i \* g\_j ∑i=1n∑j=1ifi∗gj=∑j=1n∑i=jnfi∗gj  
对于这题  
 ∑ i = 1 n ∑ j = 0 i − 1 f i ∗ g j = ∑ j = 0 n ∑ i = j + 1 n f i ∗ g j \\sum\_\{i=1\}^n \\sum\_\{j=0\}^\{i-1\} f\_i\*g\_j= \\sum\_\{j=0\}^n \\sum\_\{i=j+1\}^nf\_i\*g\_j ∑i=1n∑j=0i−1fi∗gj=∑j=0n∑i=j\+1nfi∗gj

**这题转化为定义一个矩阵的权值为其中1的个数，然后求权值和。**

∑ i = 1 n ∑ j = 1 m ∑ k = 0 i − 1 ∑ l = 0 j − 1 ( s u m ( i , j ) − s u m ( k , j ) − s u m ( i , l ) + s u m ( k , l ) ) \\sum\_\{i=1\}^n \\sum\_\{j=1\}^\{m\} \\sum\_\{k=0\}^\{i-1\} \\sum\_\{l=0\}^\{j-1\} (sum(i,j) − sum(k,j) − sum(i,l) + sum(k,l)) ∑i=1n∑j=1m∑k=0i−1∑l=0j−1(sum(i,j)−sum(k,j)−sum(i,l)\+sum(k,l))  
 s u m ( i , j ) sum(i,j) sum(i,j)为前缀和  
根据公式展开统计即可

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    typedef long long ll;
    const ll mod=998244353;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    const int maxn = 2e3+100;
    
    int n,m;
    int ma[maxn][maxn];
    ll f[maxn][maxn];
    ll ans;
    int main(int argc, char const *argv[])
    { 
    	scanf("%d%d",&n,&m);
    	rep(i,1,n+1)
    	{ 
    		rep(j,1,m+1)
    		{ 
    			scanf("%01d",&ma[i][j]);
    		}
    	}
    	rep(i,1,n+1)
    	rep(j,1,m+1)
    	f[i][j] = f[i][j-1] + f[i-1][j] - f[i-1][j-1] + ma[i][j];
    
    	ll ans = 0;
    
    	rep(i,1,n+1)
    	rep(j,1,m+1)
    	ans = (ans + f[i][j]*(i*j))%mod;
    
    	rep(i,1,n+1)
    	rep(j,0,m+1)
    	ans = (ans - f[i][j]*i*(m-j))%mod;
    
    	rep(i,0,n+1)
    	rep(j,1,m+1)
    	ans = (ans - f[i][j]*j*(n-i))%mod;
    
    	rep(i,0,n+1)
    	rep(j,0,m+1)
    	ans = (ans + f[i][j]*(n-i)*(m-j))%mod;
    
    	ans = (ans + mod)%mod;
    
    	printf("%lld\n",ans);
    
    	return 0;
    }