容斥原理专题(更新中……)

首先推荐一篇翻译过来的俄文论文
http://www.cnblogs.com/acSzz/archive/2012/11/18/2775923.html
uva10325
题意:整数区间[1,n],m个数a[1……m],且a[i]<=n,求区间[1,n]中不能被任意一个a[i]整除的数有多少
简单容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
ll a[17];
ll ans;
ll n,m;
ll gcd(ll a,ll b)
{
	if(!b) return a;
	while(b)
	{
		ll t=a;
		a=b;
		b=t%b;
	
	}
	return a;
}
ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}
void dfs(int flag,ll x,ll num)
{
	if(flag&1) ans+=n/num;
	else ans-=n/num;
	for(int i=x+1;i<=m;i++)
		dfs(flag+1,i,lcm(num,a[i]));
	return;
}
int main()
{
	int i;
	while(scanf("%lld %lld",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
			scanf("%lld",&a[i]);
		ans=0;
		for(i=1;i<=m;i++)
			dfs(1,i,a[i]);
		ans=n-ans;
		printf("%lld\n",ans);

	
	
	}

	return 0;
}

uva11806
题意:n*m的格子矩阵,要你涂色其中k个格子,使得第一行、最后一行、第一列、最后一列都至少有一格涂色(角上的格子代表着两行),问有多少种方案,结果mod 1000007
思路:思考它的逆问题,上述四行中至少一行没有被涂色的可能方案数。容斥解之。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int mod=1000007;
int c[510][510],a[5],b[5];
int ans,n,m,k;
void init()
{
    int i,j;
    memset(c,0,sizeof(c));
    for(i=0;i<=500;i++)
        c[i][0]=1;
    for(i=1;i<=500;i++)
        for(j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    return;
}
void dfs(int flag,int x,int row,int col)
{
    if(flag&1)
        ans=(ans+c[row*col][k])%mod;
    else
        ans=(ans-c[row*col][k]+mod)%mod;
    for(int i=x+1;i<=4;i++)
      dfs(flag+1,i,row+a[i],col+b[i]);
    return;

}
int main()
{
    int i,t,cases=0;
    a[1]=-1,a[2]=0,a[3]=-1,a[4]=0;
    b[1]=0,b[2]=-1,b[3]=0,b[4]=-1;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&m,&k);
        ans=0;
        for(i=1;i<=4;i++)
            dfs(1,i,n+a[i],m+b[i]);
        ans=(c[n*m][k]-ans+mod)%mod;
        printf("Case %d: %d\n",++cases,ans);
    }
    return 0;
}

TopCoder SRM 477
题意:n个数对应n个位置,其中k个确定的位置错排的方案有多少种
思路:思考反问题,设k个位置分别为pos[1],pos[2],……,pos[k].pos[i]不错排,其他k-1个位置错排的方案,pos[i]、pos[j]错排,其它k-2个位置不错排的方案,and so on……

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef long long ll;
const ll mod=1000000007;
ll n,k;
ll ans;
ll fact[1010];
ll mulmod(ll a,ll n,ll m)
{
    ll y=0;
    a%=m;
    while(n)
    {
        if(n&1) y+=a;
        if(y>=m) y-=m;
        n>>=1;
        a<<=1;
        if(a>=m) a-=m;
    }
    return y;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans=(ans+fact[n-num])%mod;
    else
        ans=(ans-fact[n-num]+mod)%mod;
    for(int i=x+1;i<=k;i++)
        dfs(flag+1,i,num+1);

}
int main()
{
    int i;
    fact[0]=1;
    for(i=1;i<=1000;i++)
    fact[i]=mulmod(fact[i-1],i,mod);
    while(scanf("%lld %lld",&n,&k)!=EOF)
    {
        ans=0;
        for(i=1;i<=k;i++)
            dfs(1,i,1);
        ans=(fact[n]-ans+mod)%mod;
        printf("%lld\n",ans);

    }
    return 0;
}

hdoj2204
一直用g++提交,一直wa,后来用c++,终于ac了。。
1.a^k<=n,那么显然对于<=a的数t,t^k<=n
2.若a^(k*t),则(a^k)^t.所以只要考虑指数为素数的情况即可。
3.a^3与t^7可能相同,所以要用容斥

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef __int64 ll;
#define eps 1.0e-8
int a[5];
ll ans,n;
const int N=100;
int pr[N+10],p[N+10],lp;
void gp()
{
    for(int i=2;i<N;i++)
    {
        if(!pr[i])p[++lp]=pr[i]=i;
        for(int j=1;j<=lp && i*p[j]<N;j++)
        {
            pr[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
    }
    return;
}
void dfs(int flag,int x,int num)
{
    int i;
    if(num>=60)
        return;
    ll tmp=(ll)pow((double)n+eps,1.0/num);

    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(i=x+1;i<=17;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i;
    gp();
    while(scanf("%I64d",&n)!=EOF)
    {
        ans=0;
        for(i=1;i<=17;i++)
            dfs(1,i,p[i]);
        printf("%I64d\n",ans-1);
    }
    return 0;
}

zoj2836
简单那容斥,注意理解题意,any与every的区别。。

#include<stdio.h>
#include<stdlib.h>
typedef long long ll;
ll n,m,ans;
ll a[15];
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(ll flag,ll x,ll num)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=n;i++)
        dfs(flag+1,i,lcm(num,a[i]));
    return;
}
int main()
{
    int i,j;
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(i=1;i<=n;i++)
            dfs(1,i,a[i]);
        printf("%lld\n",ans);

    }
    return 0;
}

zoj3233
题意:分别给你n个正整数a[i],m个正整数b[i],数据范围[1,32767],同时给你两个整数low,up,数据范围[1,10^18],问你[low,up]区间内有多少个数满足:至少能被一个a[i]整除且至少能被一个b[i]不整除。
哈哈,这题独立想出来了特别高兴,应为感觉这题不是直接赤裸裸的容斥,而是要变化下。
思路:
1.[low,up]区间满足的数的个数=[1,up]区间满足的数的个数-[1,low-1]区间满足的数的个数。
2.能被a整除,且能被b整除,等价于能被lcm(a,b)整除
3.至少能被一个a[i]整除且至少能被一个b[i]不整除,转化一下:至少能被一个a[i]整除且不是能被所有b[i]整除。为了是思维清晰,符号化一下:
x:至少能被一个a[i]整除.
y:能被所有b[i]整除
原命题转化为:x && (非y)
发现还是不能直接用容斥,继续转化,最关键的转化:x && (非y)=x-(x && y)
也就是说:(a[1]表示能被a[1]整除的个数)
(能被所有b[i]整除,等价于能被lcm(b[1],b[2],b[3],……,b[m])整除(设为lcm))
(a[1] || a[2] || …… || a[n])-(a[1] || a[2] || …… || a[n]) && lcm就是答案
很显然,减号的前面部分是可以直接用容斥的,后面部分却带了一个 && lcm,肿么办呢?
其实这里考察的就是布尔代数的知识啦。
(a[1] || a[2] || …… || a[n]) && lcm=(a[1] && lcm) || (a[2] && lcm) || …… || (a[n] && lcm)
化成这样就可以使用容斥啦。
最后,分别对[1,up],[1,low-1]求解出满足的个数再相减就可以了。
本题这样就解决了吗?思路上这样确实对了,但是还有一个要注意的地方,这个地方往往被忽略(弱菜表示因为这个提交错了20次。。).
本题的a[i],b[i]是10^4级别,且b序列可能达到500个,这样最坏情况下,这些数的lcm是会llu溢出的,溢出说明区间中没有数能被这个数整除,因为这个数太大了。所以直接返回或continue即可。(可以lcm()函数里判断是否溢出,溢出返回0,这样在dfs等地方就很好判断是否溢出了,当然,也可以在溢出时,让lcm()返回一个>10^18的数,试了一下时间从690 ms升到1190 ms)
—————————————————我是分割线君————————————————
好吧,看了下网上别人的代码,其实可以更严格地考虑当a/gcd>up/b就返回up+1,也就是说当lcm大于up了,能被lcm整除的数一定为0了。

#include<stdio.h>
const unsigned long long inf=(1<<63)-1+(1<<63);
typedef unsigned long long ll;
int n,m;
ll a[20];
ll ans;
bool flag;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    ll tmp=a/gcd(a,b);
    if(tmp>(inf/b))
        return 0;
    return tmp*b;
}
void dfs(ll flag,int x,ll num,ll b)
{
    if(num==0)
        return;
    if(flag&1)
        ans+=b/num;
    else
        ans-=b/num;
    for(int i=x+1;i<=n;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]),b);
    }
    return;

}
ll solve(ll l,ll r)
{
    int i;
    ll result=0;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],l);
    result+=ans;
    ans=0;
    for(i=1;i<=n;i++)
        dfs(1,i,a[i],r);
    result=ans-result;
    if(flag)
    {
        for(i=1;i<=n;i++)
        {
            a[i]=lcm(a[i],a[n+1]);
        }
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],l);
        result+=ans;
        ans=0;
        for(i=1;i<=n;i++)
            dfs(1,i,a[i],r);
        result-=ans;
    }
    return result;
}
int main()
{
    int i;
    ll l,r;
    scanf("%d %d %llu %llu",&n,&m,&l,&r);
    while(!(n==0 && m==0 && l==0 && r==0))
    {
        flag=1;
        for(i=1;i<=n;i++)
        {
            scanf("%llu",&a[i]);
        }
        a[n+1]=1;
        ll tmp;
        for(i=1;i<=m;i++)
        {
            scanf("%llu",&tmp);
            if(a[n+1]==0)
            {
                flag=0;
                continue;
            }
            a[n+1]=lcm(a[n+1],tmp);
        }
        ll result=solve(l-1,r);
        printf("%llu\n",result);
        scanf("%d %d %llu %llu",&n,&m,&l,&r);
    }
    return 0;
}

hdoj1796
简单容斥

#include<stdio.h>
typedef long long ll;
ll a[15];
ll n;
int m;
ll ans;
ll gcd(ll a,ll b)
{
    if(a>b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}
void dfs(int flag,int x,ll num)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=m;i++)
    {
        if(a[i]==0)
            continue;
        dfs(flag+1,i,lcm(num,a[i]));
    }
    return;
}
int main()
{
    int i;
    while(scanf("%lld %d",&n,&m)!=EOF)
    {
        n--;
        ans=0;
        for(i=1;i<=m;i++)
        {
            scanf("%lld",&a[i]);
        }
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        for(i=1;i<=m;i++)
        {
            if(a[i]==0)
                continue;
            dfs(1,i,a[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj2841
开始把这题想的太简单了。
开始的错误思路,如图:

只考虑了和蓝色线共线的点,没考虑紫色线共线的点。
正确思路:可以发现,两个点与(0,0)在一条线上,那么a1/b1=a2/b2,也就是说加入两个点坐标(a,b),a与b不互质,则设a=a1*d,b=b1*d,那么a/b=a1/b1,也就是说(a,b)与(a1,b1)共线。那么本体就转化为找[1,n]、[1,m]有多少个互素对(交换位置算不同的互素对)

#include<stdio.h>
#include<string.h>
const int N=100000;
int pr[N+10],p[N];
int pi[N+5][30],ki[N+5][30];//这里数组大小开成log2(N)左右即可
int cnt,lp;
int ans;
int n,m;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(int n,int* pi,int* ki)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
    while(n!=1)
	{
        int t=pr[n];
        pi[++cnt]=t;
        ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[cnt]++;
        }
    }
    pi[0]=cnt;
    return;
}
void dfs(int flag,int x,int num,int d)
{
    if(flag&1)
        ans+=m/num;
    else
        ans-=m/num;
    for(int i=x+1;i<=pi[d][0];i++)
        dfs(flag+1,i,num*pi[d][i],d);
    return;
}
int rongchi(int n)
{
    ans=0;
    for(int i=1;i<=pi[n][0];i++)
        dfs(1,i,pi[n][i],n);
    ans=m-ans;
    return ans;
}
__int64 solve()
{
    int i;
    __int64 result=0;
    for(i=1;i<=n;i++)
    {
        result+=(__int64)rongchi(i);
    }

    return result;
}
int main()
{
    int i;
    int t;
    gp();
    for(i=2;i<=N;i++)
        fenjie(i,pi[i],ki[i]);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        if(n==1 || m==1)
        {
            int ans=(n==1?m:n);
            printf("%d\n",ans);
            continue;
        }
        __int64 result=solve();
        printf("%I64d\n",result);






    }

    return 0;
}

ural1091
题意:在[1,s]取k个不同的数,要求,这k个数有>1的公约数,给出k、s,求组数
思路:如果k个数含公因子p[i]、p[j],那么这些组肯定会重复计算。
ans=∑c(s/p[i],k)-∑c(s/(p[i]*p[j]),k)+……(p[i]是素数)

#include<stdio.h>
typedef long long ll;
int p[16]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int s,k;
ll  ans;
int cc[45][45];
int c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
void dfs(int flag,int x,int num)
{
    if(num>s)
        return;
    if(flag&1)
        ans+=(ll)c(s/num,k);
    else
        ans-=(ll)c(s/num,k);
    for(int i=x+1;i<=15;i++)
        dfs(flag+1,i,num*p[i]);
    return;
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];

    while(scanf("%d %d",&k,&s)!=EOF)
    {
        ans=0;
        for(i=1;i<=15;i++)
            dfs(1,i,p[i]);
        if(ans<10000)
            printf("%lld\n",ans);
        else
            printf("10000\n");

    }
    return 0;
}

URAL 1114
题意:a个相同的红球和b个相同的篮球放入n个不同的盒子,每个盒子可以为空,球可以不放。问有几种放球方案。
思路:
1.对于没放的球,可以抽象出一个盒子,这个盒子用于放没放的球,这样就解决了球可以不放的问题。
2.对于球的颜色,可以分别计算放红球的方法数,放篮球的方法数,乘法原理即可,可以这样做的原因在于:对于不同的红球方法,必有至少一个盒子里面的红球数不同,而对于每种红球方法,加上不同的篮球放法必然形成不同的放法。这样就解决了颜色问题
3.最后就是插板法计算每种球的方法了:c(n+a,n)、c(n+b,n)。最后答案两者相乘
4.注意要用高精度。。(尼玛,这次这个大数模板没出错,看来刚才wa的几题不是大数部分出错。。)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	BigNum(const char*);
	BigNum(const BigNum &);
	BigNum &operator=(const BigNum &);
	friend istream& operator>>(istream&,  BigNum&);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
	BigNum operator-(const BigNum &) const;
	BigNum operator*(const BigNum &) const;
	BigNum operator/(const int  &) const;
	BigNum operator^(const int  &) const;
	int    operator%(const int  &) const;
	bool   operator>(const BigNum & T)const;
	bool   operator==(const BigNum & T)const;
	bool   operator==(const int & t)const;
	bool   operator>(const int & t)const;
};
istream& operator>>(istream & in,  BigNum & b)
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;

}
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)
{
	int t,k,index,l;
	memset(a,0,sizeof(a));
	l=strlen(s);
	len=l/DLEN;
	if(l%DLEN)len++;
	index=0;
	for(int i=l-1;i>=0;i-=DLEN)
	{
		t=0;k=i-DLEN+1;
		if(k<0)k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)  a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
	len = n.len;
	memset(a,0,sizeof(a));
	for(int i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const
{
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{
			j = i + 1;
			while(t1.a[j] == 0) j++;
			t1.a[j--]--;
			while(j > i) t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i];
		}
		else t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[len - 1] == 0 && t1.len > 1)
	{
		t1.len--;
		big--;
	}
	if(flag)t1.a[big-1]=0-t1.a[big-1];
	return t1;
}
BigNum BigNum::operator*(const BigNum & T) const
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;
	for(i = 0 ; i < len ; i++)
	{
		up = 0;
		for(j = 0 ; j < T.len ; j++)
		{
			temp = a[i] * T.a[j] + ret.a[i + j] + up;
			if(temp > MAXN)
			{
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
				up = temp / (MAXN + 1);
				ret.a[i + j] = temp1;
			}
			else
			{
				up = 0;
				ret.a[i + j] = temp;
			}
		}
		if(up != 0)
			ret.a[i + j] = up;
	}
	ret.len = i + j;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int & b) const
{
	BigNum ret;
	int i,down = 0;
	for(i = len - 1 ; i >= 0 ; i--)
	{
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
	}
	ret.len = len;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
int BigNum::operator %(const int & b) const
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const
{
	BigNum t,ret(1);
	int i;
	if(n<0)exit(-1);
	if(n==0)return 1;
	if(n==1)return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1){
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const
{
	int ln;
	if(len > T.len) return true;
	else if(len == T.len)
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln >= 0) ln--;
		if(ln >= 0 && a[ln] > T.a[ln]) return true;
		else return false;
	}
	else return false;
}
bool BigNum::operator==(const BigNum & T) const
{
	int ln;
	if(len != T.len) return false;
	else
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln-- );
		if(ln < 0) return true;
		else return false;
	}
}
bool BigNum::operator >(const int & t) const
{
	BigNum b(t);
	return *this>b;
}
bool BigNum::operator==(const int & t) const
{
	BigNum b(t);
	return *this==b;
}
typedef BigNum ll;
ll cc[45][45];
ll c(int n,int m)
{
    if(m>n)
        return 0;
    return cc[n][m];
}
int main()
{
    int i,j;
    for(i=0;i<=40;i++)
        cc[i][0]=1;
    for(i=1;i<=40;i++)
        for(j=1;j<=i;j++)
            cc[i][j]=cc[i-1][j-1]+cc[i-1][j];
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF)
    {
        ll ans=c(n+a,n)*c(n+b,n);
        cout<<ans<<endl;
    }
    return 0;
}

poj1091
关键是要知道最大公约数相关定理,本博客中已转载

#include<stdio.h>
typedef long long ll;
ll n,m;
const ll N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(ll i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(ll j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
ll cnt;//b数组用来存放n分解后的素因子
ll b[50];
void gn(ll n)
{
	ll i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			b[++cnt]=t;
	}
	return;
}
ll ans;
ll cal(ll x)
{
    ll result=1;
    for(ll i=1;i<=n;i++)
    {
        result*=x;
    }
    return result;

}
void dfs(int flag,ll x,ll num)
{
    ll tmp=cal(m/num);
    if(flag&1)
        ans+=tmp;
    else
        ans-=tmp;
    for(ll i=x+1;i<=cnt;i++)
    {
        dfs(flag+1,i,num*b[i]);
    }
    return;
}
int main()
{
    ll i;
    gp();
    while(scanf("%lld %lld",&n,&m)!=EOF)
    {
        ans=0;
        gn(m);
        for(i=1;i<=cnt;i++)
            dfs(1,i,b[i]);
        ans=cal(m)-ans;
        printf("%lld\n",ans);
    }
    return 0;
}

hdoj4135
简单容斥

#include<stdio.h>
typedef __int64 ll;
ll n,a,b;
const int N=1000000;
ll pr[N+10],p[(N+10)/10],lp;
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i]) p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0) break;
		}
	}
	return;
}
int cnt;
ll pp[30];//b数组用来存放n分解后的素因子
void gn(ll n)
{
	int i,t;
	cnt=0;
	while(n>1)
	{
		if(n<=N) //判断n是否小于等于10^6,当大于10^6时,它肯定含有p[1—lp]范围内的素数(如果不含,那么必然是素数,否则它含有大于10^6的素数,则它>10^12)
			t=pr[n];//小于的时候直接log级别分解
		else
		{
			t=n;
			for(i=1;i<=lp && p[i]<=n/p[i];i++)
				if(n%p[i]==0)
				{
					t=p[i];
					break;
				}
		}
		while(n%t==0) n/=t;
			pp[++cnt]=t;
	}
	return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(num>n)
        return;
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pp[i]<=n)
            dfs(flag+1,i,num*pp[i],n);
    }
    return;
}
int main()
{
    int t,i,cases=0;
    gp();
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld %lld %lld",&a,&b,&n);
        gn(n);
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],a-1);
        ll tmp=ans;
        ans=0;
        for(i=1;i<=cnt;i++)
            dfs(1,i,pp[i],b);
        ans=ans-tmp;
        ans=b-a+1-ans;
        printf("Case #%d: %lld\n",++cases,ans);
     }
    return 0;
}

poj2773
二分+容斥
一开始以为二分完就可以了,其实还要判断当前答案是否与m互质,如果不互质,还要继续减下去。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000;
const int N=1000000;
ll pr[N+10],p[N];
ll pi[N],ki[N];//这里数组大小开成log2(N)左右即可
int cnt,lp;
ll m,k;
ll gcd(ll a,ll b)
{
    if(a<b) a=a^b,b=a^b,a=a^b;
    if(!b) return a;
    while(b)
    {
        ll t=a;
        a=b;
        b=t%b;
    }
    return a;
}
void gp()
{
	for(int i=2;i<=N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<=N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	memset(ki,0,sizeof(ki));
	while(n!=1)
	{
		ll t=pr[n];
        pi[++cnt]=t;ki[cnt]=0;
        while(n%t==0)
        {
            n/=t;ki[cnt]++;
        }
    }
    return;
}
ll ans;
void dfs(int flag,int x,ll num,ll n)
{
    if(flag&1)
        ans+=n/num;
    else
        ans-=n/num;
    for(int i=x+1;i<=cnt;i++)
    {
        if(num*pi[i]<=n)
            dfs(flag+1,i,num*pi[i],n);
    }
    return;
}
int main()
{
    int i,j;
    gp();
    while(scanf("%lld %lld",&m,&k)!=EOF)
    {
        ans=0;
        ll result=0;
        fenjie(m);
        ll l=1,r=inf,mid;
        while(l<=r)
        {
            ans=0;
            mid=l+(r-l)/2;
            for(i=1;i<=cnt;i++)
                dfs(1,i,pi[i],mid);
            ans=mid-ans;
            if(ans==k)
            {
                result=mid;
                break;
            }
            else if(ans>k)
                r=mid-1;
            else
                l=mid+1;
        }
        result=mid;

        while(gcd(result,m)!=1)
        {
            result--;
        }

        printf("%lld\n",result);




    }

    return 0;
}

zoj3687
终于ac了,纠结了好一阵子,居然是变量名错了。
关键点:冲突的条件不可能同时成立,所以要判断这种情况。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mod 55566677
using namespace std;
bool day[55],cha[55];
bool hash[55][55];
typedef long long ll;
typedef struct node{
    int d,c;
}node;
node a[30];
ll fact[55];
int n,m;
ll ans;
void dfs(int flag,int x,int num)
{
    day[a[x].d]=1;cha[a[x].c]=1;
    if(flag&1)
    {
        ans=((ans-fact[n-num])%mod+mod)%mod;
    }
    else
    {
        ans=(ans+fact[n-num])%mod;
    }
    for(int i=x+1;i<=m;i++)
    {
        if((day[a[i].d]==1) || (cha[a[i].c]==1)) continue;
        dfs(flag+1,i,num+1);
        day[a[i].d]=0;cha[a[i].c]=0;
    }
    return;
}
int main()
{
    int i;
    fact[0]=1;fact[1]=1;
    for(i=2;i<=50;i++)
        fact[i]=fact[i-1]*(ll)i%mod;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(day,0,sizeof(day));
        memset(cha,0,sizeof(cha));
        memset(hash,0,sizeof(hash));
        int cnt=0;
        for(i=1;i<=m;i++)
        {
            int d,c;
            scanf("%d%d",&d,&c);
            if(hash[d]1) continue;
            a[++cnt].d=d;a[cnt].c=c;
            hash[d]1=1;
        }
        m=cnt;
        ans=fact[n];
        for(i=1;i<=m;i++)
        {
            dfs(1,i,1);
            day[a[i].d]=0;cha[a[i].c]=0;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>