VJ 点击打开链接
参考 点击打开链接
非常好的译文:点击打开链接
容斥原理的想法就是求多个集合的并集.所以要先设计好集合.
组合数学问题中,正面解决会困难,常用方法是正难则反,使用容斥原理求反向在用全集减去.将对立面的限制条件分析清楚.
eg 求区间互质的数的个数,则用除法等计算出一个数的倍数的方法再减去.
UVa 11806 Cheerleaders
求k个石子放在n*m的矩阵里 并且第一行 最后一行 第一列 最后一列都要有石子
考虑反面 求出所有的 减去不满足的情况
容斥原理总共4个 集合A(第一行没有石子) B(最后行没有石子)C(第一列没有石子)D(最后一列没有石子)
减去1个集合的 加上2个集合的 减去3个集合的 加上4个集合的
#include <cstring>
#include <cstdio>
const int maxn = 510;
const int mod = 1000007;
int C[maxn][maxn];
int main()
{
C[0][0] = 1;
for(int i = 0; i <= 500; i++){
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) %mod;
}
int T;
int cas = 1;
scanf("%d", &T);
while(T--)
{
int n, m, k, sum = 0;
scanf("%d %d %d", &n, &m, &k);
for(int s = 0; s < 16; s++){
int b = 0, r = n, c = m;
if(s&1)
r--,b++;
if(s&2)
r--,b++;
if(s&4)
<span style="white-space:pre"> </span>c--,b++;
if(s&8)
c--,b++;
if(b&1)
sum = ((sum - C[r*c][k]) % mod + mod) % mod;
else
sum = (sum + C[r*c][k]) % mod;
}
printf("Case %d: %d\n", cas++, sum);
}
return 0;
}练习DFS式列举
#include<stdio.h>
#include<string.h>
int a[20], N, M, la ;
int hash[20];
__int64 gcd(__int64 a, __int64 b)
{
__int64 c ;
while(b)
{
c = a % b ;
a = b ;
b = c ;
}
return a ;
}
// 当前点 已经加入容斥的个数，记录容斥的过程值 结果
void dfs(int now, int count, __int64 lcm, __int64 &sum)
{
lcm = a[now] / gcd(lcm, a[now]) * lcm ;
if(count & 1)
sum += (N - 1) / lcm ;
else sum -= (N - 1) / lcm ;
for(int i = now + 1; i < M; i++)
dfs(i, count + 1, lcm, sum);
}
int main()
{
int b,i ;
while(scanf("%d%d", &N, &M) != EOF)
{
for(i = 0, la = 0; i < M; i++)
{
scanf("%d", &b);
if(b)
{
a[la++] = b ;
}
}
M = la ;
__int64 sum = 0 ;
//memset(hash,0,sizeof(hash));
for(i = 0; i < M; i++) //枚举起点
dfs(i, 1, a[i], sum);
printf("%I64d\n", sum);
}
return 0 ;
}在(a,b) ,(c,d) 区间内选两个数使得GCD(X,Y)=k 那么我们直接将区间范围/k,则求互质的数字即可,枚举时注意控制X<Y 就行.
/* ***********************************************
Author :bingone
Created Time :2015-1-26 11:47:59
File Name :HDU1685.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define eps 1e-8
#define inf 0x3f3f3f3f
#define maxn (10+100000)
#define zero(x) (fabs(x)<eps)
typedef long long ll;
using namespace std;
int N,M,T,CNT;
int num[maxn];
vector<int> yz[maxn];
ll ans;
void DEBUG(){
for(int i=0;i<maxn;i++){
cout<<i<<endl;
for(int j=0;j<yz[i].size();j++)
printf("%d ",yz[i][j]);
cout<<endl;
}
}
void init(){
memset(num,0,sizeof(num));
for(int i=0;i<maxn;i++) yz[i].clear();
for(int i=2;i<maxn;i++) if(num[i]==0){
for(int j=i;j<maxn;j+=i){
yz[j].push_back(i);
num[j]=1;
}
}
///DEBUG();
}
void dfs(int loc,int pos,int cnt,int num,int t){
if(pos>=yz[loc].size()) return;
if(cnt & 1) ans+=t-t/num;
else ans-=t-t/num;
for(int i=pos+1;i<yz[loc].size();i++)
dfs(loc,i,cnt+1,num*yz[loc][i],t);
}
int main()
{
//freopen("1.out","r",stdin);
//freopen("out.txt","w",stdout);
init();int cas=1;
scanf("%d",&T);
while(T--){
int a,b,c,d,k;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0){printf("Case %d: 0\n",cas++);continue;}
if(b>d) swap(b,d);
b/=k;d/=k;ans=0;
if(b) ans=d;
for(int i=2;i<=b;i++)
for(int j=0;j<yz[i].size();j++)
dfs(i,j,1,yz[i][j],d-i);
printf("Case %d: %I64d\n",cas++,ans);
}
return 0;
}任何一个数字被表示乘一个数的质数次幂是唯一的.M^K K位质数.还有就是两个质数的乘积这种情况减去,奇加偶减.
因为三个质数乘积2*3*7=42 2^42>10^18 所以就到三就满足了.
/* ***********************************************
Author :bingone
Created Time :2015-1-26 11:47:59
File Name :HDU1685.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define eps 1e-8
#define inf 0x3f3f3f3f
#define maxn (10+1000)
#define zero(x) (fabs(x)<eps)
typedef long long ll;
using namespace std;
int N,M,T,CNT;
int num[100];
int prim[100];
void init(){
memset(num,0,sizeof(num));
CNT=0;
for(int i=2;i<100;i++){
if(num[i]==0) prim[CNT++]=i;
for(int j=0;j<CNT;j++){
if(i*prim[j]>100) break;
num[i*prim[j]]=1;
if(i%prim[j]==0) break;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ll n;
init();
while(~scanf("%I64d",&n)){
ll ans=1;
for(int i=0;i<CNT;i++){
ll tmp=(ll)(pow((double)n,1./prim[i])+eps);
if(pow((double)tmp,prim[i])>n) tmp--;
if(tmp<2) break;
ans+=(ll)tmp-1;
}
for(int i=0;i<CNT;i++)
for(int j=i+1;j<CNT;j++){
int tt=prim[i]*prim[j];
ll tmp=(ll)(pow((double)n,1./tt)+eps);
if(pow((double)tmp,tt)>n) tmp--;
if(tmp<2) break;
ans-=(ll)tmp-1;
}
ll tmp=(ll)((double)pow(n,1./30)+eps);
if(pow((double)tmp,30)>n) tmp--;
if(tmp>=2) ans+=(ll)tmp-1;
tmp=(ll)(pow((double)n,1./42)+eps);
if(pow((double)tmp,42)>n) tmp--;
if(tmp>=2) ans+=(ll)tmp-1;
printf("%I64d\n",ans);
}
return 0;
}这个一样的道理,但是有个更新操作,规模1000,用map最后在计算下就OK了. 注意map 操作 ->的运算级别比较低
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<28
#define M 100005
#define N 400005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
map<int,int>mp;
map<int,int>::iterator it;
int n,q;
int prime[N][15]={0},flag[N]={0};
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void Prime(){
for(int i=2;i<N;i++){
if(flag[i]){continue;}
prime[i][++prime[i][0]]=i;
for(int j=2;j*i<N;j++){
flag[i*j]=1;
prime[i*j][++prime[i*j][0]]=i;
}
}
}
LL ans;
void dfs(int idx,int num,int cnt,int m,int n,int p){
if(cnt==m){
int k=n/num;
if(m&1) ans-=(LL)num*k*(k+1)/2;
else ans+=(LL)num*k*(k+1)/2;
return ;
}
if(idx>prime[p][0]) return;
if(num>n) return ;
dfs(idx+1,num,cnt,m,n,p);
dfs(idx+1,num*prime[p][idx],cnt+1,m,n,p);
}
LL slove(int n,int p){
if(n<=0) return 0;
ans=(LL)n*(n+1)/2;
for(int i=1;i<=prime[p][0];i++){
// cout<<prime[p][i]<<endl;
dfs(1,1,0,i,n,p);
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
Prime();
while(t--){
scanf("%d%d",&n,&q);
mp.clear();
while(q--){
int k,x,y,c;
scanf("%d",&k);
if(k==1){
scanf("%d%d%d",&x,&y,&c);
LL ret=slove(y,c)-slove(x-1,c);
for(it=mp.begin();it!=mp.end();it++){
if((*it).first>=x&&y>=(*it).first){
if(gcd(c,(*it).first)==1) ret-=(*it).first;
if(gcd(c,(*it).second)==1) ret+=(*it).second;
}
}
printf("%I64d\n",ret);;
}
else{
scanf("%d%d",&x,&y);
mp[x]=y;
}
}
}
return 0;
}HDU 2841
还是乘法分解因子问题.
HDU 4135
这个是很基本的问题,不知道我的代码哪里错了,随机了1W组数据对拍都一样,无语.贴上我的,看哪位路过大神指点.
/* ***********************************************
Author :bingone
Created Time :2015-1-27 18:35:05
File Name :HDU4135.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define eps 1e-8
#define inf 0x3f3f3f3f
#define maxn (10+1000)
#define zero(x) (fabs(x)<eps)
typedef long long ll;
using namespace std;
int N,M,T;
ll A,B,NN,ans;
ll yz[1000005],yznum;
void dfs(int pos,int cnt,ll num){
if(pos>=yznum) return;
if(cnt & 1) ans+=B-B/num-A+A/num;
else ans-=B-B/num-A+A/num;
for(int i=pos+1;i<yznum;i++)
dfs(i,cnt+1,num*yz[i]);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%I64d%I64d%I64d",&A,&B,&NN);
A--;ans=yznum=0;
for(int i=2;i*i<=NN;i++) if(NN%i==0){
yz[yznum++]=i;
while(NN%i==0) NN/=i;
}
if(NN>1) yz[yznum++]=NN;
for(int i=0;i<yznum;i++)
dfs(i,1,yz[i]);
printf("Case #%d: %I64d\n",cas,ans);
}
return 0;
}求1...m中有多少个元组 满足aA+bB...+zZ=1 .正难则反.求不互质数
/* ***********************************************
Author :bingone
Created Time :2015-1-26 11:47:59
File Name :HDU1685.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define eps 1e-8
#define inf 0x3f3f3f3f
#define maxn (10+10000)
#define zero(x) (fabs(x)<eps)
typedef long long ll;
using namespace std;
int N,M,T,CNT;
int num[maxn];
int yz[100],yznum;
void getyz(){
yznum=0;int t=M;
for(int i=2;i*i<=t;i++) if(t%i==0){
yz[yznum++]=i;
while(t%i==0) t/=i;
}
if(t>1) yz[yznum++]=t;
}
int main()
{
while(~scanf("%d%d",&N,&M)){
getyz();
double ans=pow(M,N);
for(int i=1;i<(1<<yznum);i++){
int cnt=0, mul=1;
for(int j=0;j<yznum;j++) if(i&(1<<j))
cnt++,mul*=yz[j];
mul=M/mul;
if(cnt & 1) ans-=pow(mul,N);
else ans+=pow(mul,N);
}
printf("%.0f\n",ans);
}
return 0;
}原文：http://blog.csdn.net/gg_gogoing/article/details/43635057