[LOJ3083] [GXOI2019] 与或和
2024-09-22 04:29:12
题目链接
LOJ:https://loj.ac/problem/3083
洛谷:https://www.luogu.org/problemnew/show/P5300
Solution
逐位考虑,可以发现问题就是求一个\(\rm 01\)矩阵的全\(\rm 0\)子矩形个数。
那么我们可以用一个上升的单调栈来求这个,总复杂度\(O(n^2\log v)\)。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
#define lf double
#define ll long long
#define pii pair<int,int >
#define vec vector<int >
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
const int maxn = 1e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}
int s[maxn][maxn],a[maxn][maxn],in[maxn][maxn],n,ans1,ans2,top,sta[maxn];
int calc() {
FOR(i,1,n) FOR(j,1,n) s[i][j]=a[i][j]*(s[i-1][j]+1);
ll res=0;
FOR(i,1,n) {
sta[top=0]=0;ll tmp=0;
FOR(j,1,n) {
tmp+=s[i][j];
while(top&&s[i][sta[top]]>=s[i][j])
tmp-=(s[i][sta[top]]-s[i][j])*(sta[top]-sta[top-1]),top--; //弹栈的时候把不合法贡献减去
sta[++top]=j;res+=tmp;
}
}return res%mod;
}
void solve(int x) {
FOR(i,1,n) FOR(j,1,n) a[i][j]=(in[i][j]>>x)&1;
ans1=add(ans1,mul(calc(),1<<x));
FOR(i,1,n) FOR(j,1,n) a[i][j]^=1,ans2=add(ans2,mul(i*j,1<<x));
ans2=del(ans2,mul(calc(),1<<x));
}
int main() {
read(n);FOR(i,1,n) FOR(j,1,n) read(in[i][j]);
FOR(i,0,30) solve(i);printf("%d %d\n",ans1,ans2);
return 0;
}
最新文章
- Atitit.自然语言处理--摘要算法---圣经章节旧约39卷概览bible overview v2 qa1.docx
- 关于watir-webdriver中文乱码问题
- Linux From Scratch - Version 7.7-systemd (中文)
- Maven学习笔记(1)之安装Maven
- Ubuntu Java Envrioment
- 【转】万网域名查询接口(API)的说明
- oracle 10g 安装时字符集的选择,和后边的修改
- 一步步学Mybatis-告别繁琐的配置之Mybatis配置文件生成工具 (7)
- mybatis 插入日期类型精确到秒的有关问题
- bzoj2243-染色(动态树lct)
- JMeter-使用Badboy录制Web测试脚本
- Spark SQL原理及实战
- Java中单例实现
- 该问题是需要导包!!!需要pom中添加依赖The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- PYTHON-模块 sys os random shutil-练习
- 团队作业——Alpha冲刺 3/12
- linux 内核升级 转
- C++中的new、operator new与placement new
- CCSUOJ评测系统
- fiddler抓包工具教程
热门文章
- 第03组 Alpha冲刺(1/4)
- Cocos CreatorUI系统下
- Idea 编译项目异常 Error:java: Compilation failed: internal java compiler error
- 【POJ1573】Robot Motion
- OpenFOAM——设置自定义非均匀场区域
- (一)Cisco DHCP Snooping原理(转载)
- java spring学习
- html 获取项目根路径
- codeDecodeError ascii codec can&#39;t decode byte 0xe2 in position 44 ordinal not in range(128)
- C# 获取文件扩展信息-应用名称/作者等