Petrozavodsk Winter Camp, Day 8, 2014, Rectangle Count
2024-10-14 00:00:28
给一个n*m的格点图,问其中有多少个矩形?
$ \sum_{x=1}^{nm} \sum_{ab=x} [a + b \leq n](n - a - b + 1)\sum_{cd=x} [c + d \leq m](m - c - bd + 1)$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
const int N = ;
LL f[N * N], g[N * N]; int main() {
LL n, m;
cin >> n >> m;
n --; m --;
rep(i, , n) rep(j, , n - i)
if (i * j < N * N) f[i * j] += (LL)(n - i - j + );
rep(i, , m) rep(j, , m - i)
if (i * j < N * N) g[i * j] += (LL)(m - i - j + );
LL ans = ;
rep(i, , N * N - ) {
// if (f[i] * g[i]) cout << i << '\n';
ans += f[i] * g[i];
}
ans += (n * (n + ) / ) * (m * (m + ) / );
cout << ans << '\n';
}
最新文章
- 查看mysql语句运行时间
- ExpandableListView 里面嵌套GridView实现高度自适应
- 从oracle数据表中读取表结构
- Class类的理解
- Spring的注入问题
- bzoj1019 [SHOI2008]汉诺塔
- C#调用存储过程详解
- nodejs hello world (调用文件执行没反应)
- angularjs uigrid 中celltemplate的写浮动框
- java关于jdbc的配置与使用步骤
- Java动态代理实现及实际应用
- 重新使用linux的一些事情
- 区间dp(入门题)
- shell读取mysql数据库
- Jquery 图片延迟加载技术
- HTML for android 移动小球
- Exception的ToString()方法究竟返回的是什么
- Kafka:ZK+Kafka+Spark Streaming集群环境搭建(二十)ES6.2.2 Client API
- Python - WebDriver 识别登录验证码
- Java IO流-File类