Tag Archives: 容斥原理

POJ 1091(跳蚤-扩展欧几里德有解推论+容斥原理)

Posted on by
Language:
跳蚤
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 6911   Accepted: 1951

Description

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 

Input

两个整数N和M(N <= 15 , M <= 100000000)。

Output

可以完成任务的卡片数。

Sample Input

2 4

Sample Output

12

Hint

这12张卡片分别是： 
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4), 
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4) 

Source

HNOI 2001

假设

a1x1+a2x2+--anxn+a(n+1)M=1

则(a1,a2,..an,M)=1

所以用容斥原理计算出gcd≠1的情况的总数

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<functional>
using namespace std;
#define MAXN (15)
#define MAXM (100000000)
int n,m;
long long ans=0,temp=0;
int a[MAXM],tot=0;
long long pow2(long long a,int b)
{
	if (b==1) return a;
	else if (b%2)
	{
		long long p=pow2(a,b/2);
		return p*p*a;
	}
	else
	{
		long long p=pow2(a,b/2);
		return p*p;
	}
}
void dfs(int j,int c,int cost,int l)
{
	if (c==l)
	{
		int p=m/cost;
		if (l&1) ans+=pow2(p,n);
		else ans-=pow2(p,n);
		return;
	}
	for (int i=j+1;i<=tot+1-l+c;i++)
		dfs(i,c+1,cost*a[i],l);



}
int main()
{
	scanf("%d%d",&n,&m);
	int m2=m;
	for (int i=2;i<=(int)sqrt((double)m2);i++)
		if (0==m2%i)
		{
			a[++tot]=i;
			while (0==m2%i) m2/=i;
		}
	if (m2^1) a[++tot]=m2;
//	for (int i=1;i<=tot;i++) cout<<a[i]<<' ';
	for (int i=1;i<=tot;i++) dfs(0,0,1,i);
//	ans=pow(m,n)-ans;
	printf("%lldn",(long long)pow2(m,n)-ans);


	return 0;
}

UVA 10209(Is This Integration ?-容斥原理)

Posted on by

Problem C
Is This Integration ?
Input: Standard Input
Output: Standard Output
Time Limit: 3 seconds

 

In the image below you can see a square ABCD, where AB = BC = CD = DA = a. Four arcs are drawn taking the four vertexes A, B, C, Das centers and a as the radius. The arc that is drawn taking A as
center, starts at neighboring vertex B and ends at neighboring vertex D. All other arcs are drawn in a similar fashion. Regions of three different shapes are created in this fashion. You will have to determine the total area
if these different shaped regions.  

 

Input

The input file contains a floating-point number a (a>=0 a<=10000) in each line which indicates the length of one side of the square. Input is terminated by end of file.  

 

Output

For each line of input, output in a single line the total area of the three types of region (filled with different patterns in the image above). These three numbers will of course be floating point numbers with three digits after the decimal point. First
number will denote the area of the striped region, the second number will denote the total area of the dotted regions and the third number will denote the area of the rest of the regions.

 

Sample Input:

0.1
0.2
0.3

Sample Output:

0.003 0.005 0.002
0.013 0.020 0.007
0.028 0.046 0.016

Shahriar Manzoor

设中间那块面积为x，四个角的面积为y，四个凹形的面积为z


则有

x+4y+4z=a^2

x+3y+2z=pi/4*a^2

x+2y+z=(pi/3-√3/4)a^2 (2个扇形-中间重叠的三角形)

解出：

x=(1+pi/3-√3)*a^2

y=(pi/12+√3/2-1)*a^2

z=(-pi/6+1-√3/4)*a^2

另：注意pi的精度

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define MAXa (10000)
double a;
const double pi=3.141592653589793;
int main()
{
	while (scanf("%lf",&a)!=EOF)
	{
		printf("%.3lf %.3lf %.3lfn",a*a*(1+pi/3-sqrt(3.0)),a*a*(pi/3+2*sqrt(3.0)-4),a*a*(-2*pi/3+4-sqrt(3.0)));
	}
	return 0;
}


调色盘 (3维k点最小最远点对-容斥原理）

Posted on by

调色盘(pastele)

题目描述

Albus得到了一份礼物：来自Polaris的水彩油墨包。

Polaris的油墨包里面有N个颜色，现在Albus打算选其中的K种来作一幅风景画。

既然是风景画，颜色就不能太突兀。因此Albus进行了如下的定义：

每个颜色由三个属性刻画：R[i],G[i],B[i]。

两个颜色的“距离”指它们三个属性的最大差值，也就是Max(|Ri-Rj|,|Gi-Gj|,|Bi-Bj|)。

而K个颜色的距离，指的是其中任意两个颜色的最大距离。

你的任务是求出可能的最小距离。

 

输入

第一行两个整数N和K。

接下来N行，每行三个整数R[i],G[i],B[i]。

输出

可能的最小距离。

 

样例输入

5 3

6 6 4

6 2 7

3 1 3

4 1 5

6 2 6

样例输出

2

解释

选1,4,5三个颜色。

数据范围

对于10%的数据，N<=10

对于50%的数据，0<=Ri,Gi,Bi<=20，2<=K<=N<=100

对于80%的数据，0<=Ri,Gi,Bi<=50,2<=K<=N<=10000

对于100%的数据，2<=K<=N<=100000,0<=Ri,Gi,Bi<=150

a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

容斥原理

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (150+10)
#define MAXX (151)
int n,k,a[MAXN][MAXN][MAXN]={0},c[MAXN][MAXN][MAXN]={0};
int Node_count(int x,int y,int z,int l)
{
	if (z-l<0||y-l<0||z-l<0) return 0;
	return c[x][y][z]+c[x-l][y-l][z]+c[x][y-l][z-l]+c[x-l][y][z-l]-c[x-l][y][z]-c[x][y-l][z]-c[x][y][z-l]-c[x-l][y-l][z-l];

}
int main()
{
	freopen("pastele.in","r",stdin);
	freopen("pastele.out","w",stdout);

	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x+1][y+1][z+1]++;
	}


	/*
		a[x][y][z]=c[x][y][z]+c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1];
		c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

	*/

	for (int x=1;x<=MAXX;x++)
		for (int y=1;y<=MAXX;y++)
			for (int z=1;z<=MAXX;z++)
				c[x][y][z]=a[x][y][z]-(c[x-1][y-1][z]+c[x][y-1][z-1]+c[x-1][y][z-1]-c[x-1][y][z]-c[x][y-1][z]-c[x][y][z-1]-c[x-1][y-1][z-1]);

	/*
	for (int i=1;i<=10;i++)
	for (int j=1;j<=10;j++)
	for (int k=1;k<=10;k++)
		if (c[i][j][k]) cout<<i<<' '<<j<<' '<<k<<' '<<c[i][j][k]<<endl;
	cout<<Node_count(6,6,6,6);
	*/

	int ans=MAXX;//成立 区间  (0 ,MAXX]
	for (int x=MAXX;x>=1;x--)
		for (int y=MAXX;y>=1;y--)
			for (int z=MAXX;z>=1;z--)
			{
				if (ans&&k<=Node_count(x,y,z,ans)) ans--;
			}
	cout<<ans<<endl;


//	while (1);
	return 0;
}