ECNU 2018.10 月赛 C（数学统计）

原题： https://acm.ecnu.edu.cn/contest/113/problem/C/

题意：

01矩阵，$Cost(i,j)$为i行和j列的0的个数，$Sum={\sum }_{i=1}^n{\sum }_{j=1}^{n}Cost(i,j)$
每次操作为反转一个位置的数，求开始的Sum和每次操作后的Sum

解析：

设$R_i$为i行的0数量，$C_j$为j列的0数量，$B_{ij}$表示ij位置是否为0，$A$为矩阵中0的数量
（${\sum }_{i=1}^n{B}_{ij}=C_j,{\sum }_{j=1}^n{B}_{ij}=R_i,{\sum }_{i=1}^n{C}_j={\sum }_{j=1}^n{R}_i=A$）
那么接下来化简题目表达式：
$$\begin{gathered} Sum=\sum _{i=1}^n\sum _{j=1}^{n}Cos{t}^2(i,j) \\ =\sum _{i=1}^n\sum _{j=1}^n(R_i+C_j-B_{ij}{)}^2 \\ =\sum _{i=1}^n[(R_i+C_1-B_{i1}{)}^2+\dots (R_i+C_n-B_{in}{)}^2] \\ =\sum _{i=1}^n[(R_i+C_1{)}^2+B_{i1}-2B_{i1}(R_i+C_1)+\dots ] \\ =\sum _{i=1}^n[(n{R}_i^2+(C_1^2+\dots C_n^2)+2R_{i}A)+R_i-2R_i^2-\sum _{j=1}^{n}2B_{ij}{C}_j] \end{gathered}$$
$$\begin{gathered} =(n-2)\sum _{i=1}^n{R}_i^2+n\sum _{j=1}^n{C}_j^2+2A^2+A-2\sum _{i=1}^n\sum _{j=1}^n{B}_{ij}{C}_j \\ =(n-2)\sum _{i=1}^n{R}_i^2+(n-2)\sum _{j=1}^n{C}_j^2+2A^2+A \end{gathered}$$

所以每次修改的时候找到原来的$R,C,A$，再算出现在的比较计算就是答案。判断为1或0可以用set，注意每次操作后需要维护set。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL mod=1e9+7;
LL a[N],b[N];

struct node{
    int x,y;
}e[N];
set<int>S[N];

int main(){
    LL n,k,q;
    scanf("%lld%lld%lld",&n,&k,&q);
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=1;i<=k;i++){
        int x,y;scanf("%d%d",&x,&y);
        e[i].x=x,e[i].y=y;
        S[x].insert(y);
        a[y]++,b[x]++;
    }
    for(int i=1;i<=n;i++)a[i]=n-a[i],b[i]=n-b[i];//num of 0

    LL A=(n*n-k)%mod;
    LL All=(2*A*A+A)%mod;
    for(int i=1;i<=n;i++)All=(All+(n-2)*a[i]*a[i]%mod+(n-2)*b[i]*b[i]%mod)%mod;
    printf("%lldn",All);

    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);

        LL pre=((n-2)*a[y]*a[y]%mod+(n-2)*b[x]*b[x]%mod+2*A*A%mod+A)%mod;
        LL now;
        if(S[x].find(y)==S[x].end()){//0->1
            now=((n-2)*(a[y]-1)%mod*(a[y]-1)%mod+(n-2)*(b[x]-1)%mod*(b[x]-1)%mod+2*(A-1)*(A-1)%mod+A-1)%mod;
            A--,a[y]--,b[x]--;
            S[x].insert(y);
        }
        else{
            now=((n-2)*(a[y]+1)%mod*(a[y]+1)%mod+(n-2)*(b[x]+1)%mod*(b[x]+1)%mod+2*(A+1)*(A+1)%mod+A+1)%mod;
            A++,a[y]++,b[x]++;
            S[x].erase(y);
        }
        All=((All+now-pre)%mod+mod)%mod;
        printf("%lldn",All);
    }
}

最后

以上就是欢呼龙猫最近收集整理的关于ECNU 2018.10 月赛 C（数学统计）的全部内容，更多相关ECNU内容请搜索靠谱客的其他文章。