容斥原理训练 (16.04.10)

容斥原理训练 (16.04.10)

这又是一篇训练系列的博文，主题是容斥原理。 题目： UVA 10325 A - The Lottery poj 3904 Sky Code uvalive 7040 color hdu 4059 The Boss on Mars H - Visible Trees

UVA 10325 A - The Lottery

​​ 大意：给出一堆数字A，求在1-N内不被A中任意一个数字整除的个数。 分析：看到第二个样例，瞬间觉得不简单。假设这样一个例子：N=25, A=(6,8) 6：6、12、18、24 8：8、16、24 那么既能被6整除又能被8整除的数（最小数）难道是 6*8=48：0 吗？ 显然这是不对的，既能被6整除又能被8整除的最小正整数该是24——最大公约数

多写写样例测试自己的程序很重要！！

poj 3904 Sky Code

​​ 大意：求得在n个数字中最大公约数是1的四元组的个数

分析：正着求解是肯定不行的，逆向求解——容斥原理。用所有的素因子去求解所有的倍数，如果有四个数字的最大公约数是大于1的，那么一定存在素因子的组合是最大公约数的因子。所以对每一个数字素因子分解，记录每个因子，统计每个因子在这n个数中出现的次数和其素因子的组合个数。然后容斥，求出所有的非1四元组个数，最后总数减去它即可。

#include #include #include using namespace std;typedef long long LL;const int N=10010;LL record[N],sum[N];LL calc(LL n){ return 1LL*n*(n-1)*(n-2)*(n-3)/4/3/2;}LL fac[N],top;void solve(LL n){ top=0; for(LL i=2;i*i<=n;i++){ if(n%i==0){ fac[top++]=i; while(n%i==0) n/=i; } } if(n>1) fac[top++]=n;}int main(int argc, char *argv[]) { LL n,w; while(~scanf("%lld",&n)){ memset(record,0,sizeof(record)); memset(sum,0,sizeof(sum)); LL maxs=0; for(LL i=0;is?maxs:s; record[s]++; } } LL ans=calc(n),temp=0; for(LL i=1;i<=maxs;i++){ if(sum[i]>0){ if(sum[i]&1) temp=temp+calc(record[i]); else temp=temp-calc(record[i]); } } ans=ans-temp; printf("%lld\n",ans); } return 0;}

uvalive 7040 color

​​ 大意：N个物品排成一列，现在有m种颜色，从中选出k种颜色。要求相邻物品颜色不同地涂色。 分析：首先从m种颜色中选出k种颜色，Ckm 两两不同的涂色：第一个物品涂色k种选择,，第二个物品涂色k-1种选择，第三个物品涂色k-1种选择……所以，得到Ckmk(k−1)n−1，但是这样的结果还包含了只用2种颜色涂色，只用3种颜色涂色，只用4种颜色涂色……用k-1种颜色涂色。所以，我们需要除去这些不相干的情况。所以在选出k种颜色，Ckm后，要再考虑Ciki(i−1)n−1 的情况，同时Ciki(i−1)n−1又涉及到新的子集问题（我们不能直接Ckmk(k−1)n−1−CkmCk−1k(k−1)(k−2)n−1 因为有选择的步骤Cmn ),什么能解决这种树叶的投影类问题呢？容斥原理。 设f(i)=Ciki(i−1)n−1 如k=5时，C5m(f(1)−f(2)+f(3)−f(4)+f(5)) k=4时，C4m(−f(1)+f(2)−f(3)+f(4)) 即，括号里一定是 f(n)−f(n−1)+f(n−2)−f(n−3)⋯f(1) 注意：能预处理的预处理，不要造成不必要的多重循环，以免TLＥ。

#include #include using namespace std;typedef long long LL;const LL N=1e6+10,mod=1e9+7;LL C1[N],C2[N],inv[N],p[N];LL power(LL a,LL p){ LL ans=1; while(p){ if(p&1) ans=ans*a%mod; a=a*a%mod; p>>=1; } return ans;}void init(LL C[],LL n,LL m){ C[0]=1; C[1]=n; for(int i=2;i<=m;i++){ //LL ni=power(i,mod-2); C[i]=C[i-1]*(n-i+1)%mod*inv[i]%mod; }}int main(){ for(int i=1;i>t; while(t--){ LL n,m,k; scanf("%lld %lld %lld",&n,&m,&k); init(C1,m,k); init(C2,k,k); LL ans=C2[k]*k%mod*power(k-1,n-1)%mod; LL temp=0; for(int i=1;i

hdu 4059 The Boss on Mars

​​求出 ∑x=1kx4 其中x和n互质 几个常用的求和公式：

∑x=1nx2=n(n+1)(2n+1)6∑x=1nx3=n2(n+1)24∑x=1nx4=n(n+1)(2n+1)(3n2+3n−1)30

他们均能由牛顿二项展开式+列项相消推出。

现在题目要求求出∑x4其中x和n互质，那么可以先求出所以的∑x4，然后减去非互质的数。例如n=10. 那么，先求出∑x=110x4，然后减去2的倍数，5的倍数即可。但是这里有重复，于是容斥闪亮登场，2的倍数的4次方的和可以写成 24∑x=1kx4。

#include #include #include using namespace std;typedef long long LL;const LL N=1e4+10,mod=1e9+7;LL fac[N],top;void solve(LL n){ top=0; for(LL i=2;i*i<=n;i++){ if(n%i==0){ fac[top++]=i; while(n%i==0) n/=i; } } if(n>1) fac[top++]=n;}LL quick(LL a,LL p){ LL ans=1; while(p){ if(p&1) ans=ans*a%mod; a=a*a%mod; p>>=1; } return ans;}LL ni;LL sum(LL n){ return n*(n+1)%mod*(2*n%mod+1)%mod*(3*n*n%mod+3*n%mod-1)%mod*ni%mod;}int main(){ LL t,n; ni=quick(30,mod-2); cin>>t; while(t--){ scanf("%I64d",&n); solve(n); LL ans=sum(n); LL t=0; for(LL i=1;i<(1<

hdu 2841 - Visible Trees

​​ 大意：人站在(0,0), 矩阵左上角是(1,1)，求解对于规模是m*n的矩阵人能看到的点数。 分析：如果一个点被另一个点挡住了，那么他们过（0,0）的斜率一定是一样的。即yx一定相等（最简形式），所以问题就变成了求解有多少个(x，y)互质对。 设m<0, 一部分的点数是2∑i=2mϕ(i)+1

#include #include using namespace std;const int N=1e5+10;typedef long long LL;LL phi[N];void init(){ for(LL i=1;i1) fac[top++]=n;}int main(){ init(); LL t,m,n; cin>>t; while(t--){ scanf("%lld%lld",&m,&n); if(m>n){ m=m^n; n=m^n; m=m^n; } LL ans=0; for(LL i=2;i<=m;i++){ ans=ans+phi[i]; } ans=ans<<1; ans++; for(LL i=m+1;i<=n;i++){ solve(i); LL temp=0; for(LL j=1;j<(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。