hdu 5116--Everlasting L(计数DP)
2024-10-10 04:12:56
Problem Description
Matt loves letter L.
A point set P is (a, b)-L if and only if there exists x, y satisfying:
P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1)
A point set Q is good if and only if Q is an (a, b)-L set and gcd(a, b) = 1.
Matt is given a point set S. Please help him find the number of ordered pairs of sets (A, B) such that:
Input
The first line contains only one integer T , which indicates the number of test cases.
For each test case, the first line contains an integer N (0 ≤ N ≤ 40000), indicating the size of the point set S.
Each of the following N lines contains two integers xi, yi, indicating the i-th point in S (1 ≤ xi, yi ≤ 200). It’s guaranteed that all (xi, yi) would be distinct.
Output
For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y is the number of pairs.
Sample Input
2
6
1 1
1 2
2 1
3 3
3 4
4 3
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
Sample Output
Case #1: 2
Case #2: 6
Hint
n the second sample, the ordered pairs of sets Matt can choose are:
A = {(1, 1), (1, 2), (1, 3), (2, 1)} and B = {(2, 2), (2, 3), (3, 2)}
A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (1, 3), (2, 1)}
A = {(1, 1), (1, 2), (2, 1), (3, 1)} and B = {(2, 2), (2, 3), (3, 2)}
A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (2, 1), (3, 1)}
A = {(1, 1), (1, 2), (2, 1)} and B = {(2, 2), (2, 3), (3, 2)}
A = {(2, 2), (2, 3), (3, 2)} and B = {(1, 1), (1, 2), (2, 1)}
Hence, the answer is 6.
题意:对于点集P 如果存在a,b使得P = {(x, y), (x + 1, y), . . . , (x + a, y), (x, y + 1), . . . , (x, y + b)}(a, b ≥ 1),并且a,b互质,则P is good 。可以发现对于符合要求(good)的集合P ,其构成一个L 型,且以(x,y)为拐点,从(x,y)向上长度和向右长度互质。现在给了N个点,求有多少对符合要求的L型集合不相交(集合交集为空)?
思路:先找到所有符合要求的L个数S,那么用S*S-相交的L对数 即为结果。
怎么算相交的所有L对数呢? 容斥,很妙的思想,遍历每一个点,如果当前的点是输入的点之一,那么是一个拐点,令这个拐点向右延伸最长为k,那么算出所有其它L的竖着部分与(x,y+k)相交的对数,乘以2,另外要考虑以(x,y)为拐点的L与自身相交的情况,把这两种相交情形减掉后既是结果。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=;
const int M=;
int R[M][M],U[M][M];
bool mp[M][M];
int dp[M][M],cnt[M][M];
int t[M][M]; int gcd(int a,int b) { return (b==)?a:gcd(b,a%b); } void init()
{
for(int i=;i<M;i++)
for(int j=;j<M;j++)
{
dp[i][j]=dp[i][j-]+((gcd(i,j)==)?:);
cnt[i][j]=cnt[i-][j]+dp[i][j];
}
}
int main()
{
init();
int T,Case=;
cin>>T;
while(T--)
{
int n; scanf("%d",&n);
memset(mp,,sizeof(mp));
memset(U,,sizeof(U));
memset(R,,sizeof(R));
memset(t,,sizeof(t));
for(int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
mp[x][y]=;
}
for(int i=;i>=;i--)
{
for(int j=;j>=;j--)
{
if(mp[i][j]){
if(mp[i+][j]) U[i][j]=U[i+][j]+;
if(mp[i][j+]) R[i][j]=R[i][j+]+;
}
}
}
LL s=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(mp[i][j]){
s+=cnt[U[i][j]][R[i][j]];
int d=;
for(int k=U[i][j];k>=;k--)
{
d+=dp[k][R[i][j]];
t[i+k][j]+=d;
}
}
}
}
LL ans=;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
if(mp[i][j]){
LL p=t[i][j];
LL pp=cnt[U[i][j]][R[i][j]];
p-=pp;
for(int k=;k<=R[i][j];k++)
{
p+=t[i][j+k];
ans+=*p*dp[k][U[i][j]];
}
ans+=pp*pp;
}
}
}
s=s*s-ans;
printf("Case #%d: %lld\n",Case++,s);
}
return ;
}
最新文章
- 项目中遇到的各种bug和踩过的坑
- cocos2d-x 第一篇 环境搭建
- ruby -- 进阶学习(四)paperclip上传中文命名图片
- Android图片缓存的框架ImageLoader的使用
- Jquery添加移除样式
- C++类型引用浅析
- Oracle VM VirtualBox 随系统自动启动虚拟机的方法
- ASP.NET MVC学习之路由篇
- (转+原)android获取系统时间
- chrome 开发人员工具
- iptables 端口转发规则
- IdentityServer4【Introduction】之支持的规范
- 【贪心】[hdu1052]Tian Ji -- The Horse Racing(田忌赛马)[c++]
- c++中transform()函数和find()函数的使用方法。
- DevExpress15.2+VS2015 破解、汉化
- Oracle 之 保留两位小数
- python 集合取最大最小值
- 简单服务端缓存API设计
- mysql赋值表结构和数据
- tomcat启动优化
热门文章
- TypeError: while_loop() got an unexpected keyword argument &#39;maximum_iterations&#39;
- jdk1.8 HashMap的实现
- Sass入门及知识点整理
- 4412 uboot上手
- HTML5表单_form
- [树状数组+逆序对][NOIP2013]火柴排队
- [JAVA]JAVA章3 如何获取及查看DUMP文件
- 关闭浏览器时提示的javascript事件
- activeMq-3 Spring整合activeMq
- win7启动时怎么自动进入桌面