10分求助,不知道是不是取模的问题
  • 板块P6692 出生点
  • 楼主lcbridgeAK CSP-S
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/15 11:21
  • 上次更新2023/11/3 03:41:36
查看原帖
10分求助,不知道是不是取模的问题
546681
lcbridgeAK CSP-S楼主2023/8/15 11:21
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N=5*1e5+5;
const int mod=1e9+7;
int n,m,k,x[N],y[N];
int f[N],f1[N];
void scan(__int128 &x){
    x=0;int f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
void _print(__int128 x){
    if(x>9) _print(x/10);
    putchar(x%10 + '0');
}
void print(__int128 x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    _print(x);
}
signed main(){
	scan(n);
	scan(m);
	scan(k);
	for(int i=1;i<=k;i++){
		scan(x[i]);
		scan(y[i]);
	} 
	int Si=(1+n)%mod*n%mod/2;
	int Sii=n%mod*(n+1)%mod*(2*n+1)%mod/6%mod;
	int Sj=(1+m)%mod*m%mod/2;
	int Sjj=m%mod*(m+1)%mod*(2*m+1)/6%mod;
	int S=(m*m%mod*n*Si%mod-m*m*Sii%mod+m*n%mod*n*Sj%mod-n*n*Sjj%mod)%mod;
	for(int i=1;i<=k;i++){
		int Lx=x[i]%mod*(x[i]-1)/2*m%mod;
		int Rx=(1+n-x[i])%mod*(n-x[i])/2*m%mod;
		int Ly=y[i]%mod*(y[i]-1)/2*n%mod;
		int Ry=(1+m-y[i])%mod*(m-y[i])/2*n%mod;
		S=(S-Lx-Rx-Ly-Ry)%mod;
	}
	sort(x+1,x+k+1);
	f[1]=0;
	for(int i=1;i<k;i++){
		f[i+1]=(f[i]+i%mod*(x[i+1]-x[i])%mod)%mod;
		S=(S+f[i+1]%mod)%mod;
	}
	sort(y+1,y+k+1);
	f1[1]=0;
	for(int i=1;i<k;i++){
		f1[i+1]=(f1[i]+i%mod*(y[i+1]-y[i]))%mod;
		S=(S+f1[i+1]%mod)%mod;
	}
	S%=mod;
	print((S+mod)%mod);
	return 0;
} 
2023/8/15 11:21
加载中...