秒速赛车源码搭建下载【http://hubawl.com/】【1784662395】
知识点 - 容斥原理 鸽巢原理 乘法原理
解决问题类型：
容斥：算重了。
首位大于1，末尾小于8的排列数
长度为n的由 (0, 1, 2) 构成，且0，1，2至少出现一次的子序列个数
n元一次方程整数解个数。
给定区间互质数对个数
给n个，问给定区间中是某个ai a_{i}a
i
的倍数的个数
符合给定规则的串的个数
从一个格子走到另一个格子的方案数
互质四元组的个数
harmonic triplets的个数
错排问题
鸽巢：
题目给了n，考虑n+1的情况。
结论
容斥公式
（1）设A1,A2,⋅⋅⋅,An A_{1},A_{2}, \cdot \cdot \cdot ,A_{n}A
1
,A
2
,⋅⋅⋅,A
n
是集合 S SS 的子集，表示以集合 S SS 代表可能发生的事件中的 n nn 个子事件，∣Ai∣ \left| A_{i} \right|∣A
i
∣表示子事件Ai A_{i}A
i
发生的个数(0≤i≤n) \left( 0 \leq i \leq n \right)(0≤i≤n)，则有
∣A1∪A2∪A3∪⋅⋅⋅∪An∣=∑ni=1∣Ai∣−∑1≤i<j≤n∣Ai∩Aj∣+⋅⋅⋅+(−1)n−1∣A1∩A2∩A3∩⋅⋅⋅∩An∣ \left| A_{1} \cup A_{2} \cup A_{3} \cup \cdot \cdot \cdot \cup A_{n} \right| = \sum_{i = 1}^{n}\left| A_{i} \right| - \sum_{1 \leq i < j \leq n}^{}\left| A_{i} \cap A_{j} \right| + \cdot \cdot \cdot + \left( - 1 \right)^{n - 1}\left| A_{1} \cap A_{2} \cap A_{3} \cap \cdot \cdot \cdot \cap A_{n} \right|
∣A
1
∪A
2
∪A
3
∪⋅⋅⋅∪A
n
∣=
i=1
∑
n
∣A
i
∣−
1≤i<j≤n
∑
∣A
i
∩A
j
∣+⋅⋅⋅+(−1)
n−1
∣A
1
∩A
2
∩A
3
∩⋅⋅⋅∩A
n
∣
压缩版：
∣⋃ni=1Ai∣=∑∅≠J⊆1,2,…,n(−1)∣J∣−1∣⋂j∈JAj∣∣ \left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq \\{1,2,\ldots ,n\\}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}
∣
∣
∣
∣
∣
i=1
⋃
n
A
i
∣
∣
∣
∣
∣
=
∅
̸
=J⊆1,2,…,n
∑
(−1)
∣J∣−1
∣
∣
∣
∣
∣
j∈J
⋂
A
j
∣
∣
∣
∣
∣
概率版：
KaTeX parse error: Expected '}', got '\cal' at position 2: {\̲c̲a̲l̲ ̲P}(A)代表A事件发生的概率。
KaTeX parse error: Expected '}', got '\cal' at position 3: {\̲c̲a̲l̲ ̲P} \left(\bigcu…
补集公式：
（A上面有横线）
∣∣A1¯∩A2¯∩A3¯∩⋅⋅⋅∩An¯∣∣=S−∣A1∪A2∪A3∪⋅⋅⋅∪An∣ \left| \overset{\overline{}}{A_{1}} \cap \overset{\overline{}}{A_{2}} \cap \overset{\overline{}}{A_{3}} \cap \cdot \cdot \cdot \cap \overset{\overline{}}{A_{n}} \right| = S - \left| A_{1} \cup A_{2} \cup A_{3} \cup \cdot \cdot \cdot \cup A_{n} \right|
∣
∣
∣
A
1
∩
A
2
∩
A
3
∩⋅⋅⋅∩
A
n
∣
∣
∣
=S−∣A
1
∪A
2
∪A
3
∪⋅⋅⋅∪A
n
∣
补集版
∣∣⋂ni=1Ai¯¯¯¯∣∣=∑nm=0(−1)m∑∣X∣=m∣∣⋂i∈XAi∣∣ \left|\bigcap_{i=1}^n \overline{A_i}\right|=\sum_{m=0}^n (-1)^m \sum_{|X|=m} \left|\bigcap_{i\in X} A_{i}\right|
∣
∣
∣
∣
∣
i=1
⋂
n
A
i
∣
∣
∣
∣
∣
=
m=0
∑
n
(−1)
m
∣X∣=m
∑
∣
∣
∣
∣
∣
i∈X
⋂
A
i
∣
∣
∣
∣
∣
集合大小为r版
∣∣⋃∣B∣=r[⋂i∈BAi∩⋂j̸ ∈BAj¯¯¯¯]∣∣=∑nm=r(−1)m−r(mr)∑∣X∣=m∣∣⋂i∈XAi∣∣ \left|\bigcup_{|B|=r}\left[\bigcap_{i \in B} A_i \cap \bigcap_{j \not\in B} \overline{A_j}\right]\right|=\sum_{m=r}^n (-1)^{m-r}\dbinom{m}{r} \sum_{|X|=m} \left|\bigcap_{i \in X} A_{i}\right|
∣
∣
∣
∣
∣
∣
∣B∣=r
⋃
⎣
⎡
i∈B
⋂
A
i
∩
j
̸
∈B
⋂
A
j
⎦
⎤
∣
∣
∣
∣
∣
∣
=
m=r
∑
n
(−1)
m−r
(
r
m
)
∣X∣=m
∑
∣
∣
∣
∣
∣
i∈X
⋂
A
i
∣
∣
∣
∣
∣
容斥问题
上面所有公式证明和问题题解戳这里
错排问题
（1）设Dn D_{n}D
n
表示1,2,3,⋅⋅⋅,n 1,2,3, \cdot \cdot \cdot ,n1,2,3,⋅⋅⋅,n这n个数的一个排列的错排个数，有
Dn=n![1−11!+12!−13!+⋅⋅⋅+(−1)n1n!],D1=0,D2=1 D_{n} = n!\left\lbrack 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdot \cdot \cdot + \left( - 1 \right)^{n}\frac{1}{n!} \right\rbrack,D_{1} = 0,D_{2} = 1
D
n
=n![1−
1!
1
+
2!
1
−
3!
1
+⋅⋅⋅+(−1)
n
n!
1
],D
1
=0,D
2
=1
Dn=(n−1)[Dn−1+Dn−2],n>2 D_n=(n-1)[D_{n-1}+D_{n-2}],n>2
D
n
=(n−1)[D
n−1
+D
n−2
],n>2
Dn=nDn−1+(−1)n D_n=nD_{n-1}+(-1)^n
D
n
=nD
n−1
+(−1)
n
带有禁位的错排问题
（1）n个元素a1,a2,a3,⋅⋅⋅,an a_{1},a_{2},a_{3}, \cdot \cdot \cdot ,a_{n}a
1
,a
2
,a
3
,⋅⋅⋅,a
n
带有禁位X1,X2,X3,⋅⋅⋅,Xn X_{1},X_{2},X_{3}, \cdot \cdot \cdot ,X_{n}X
1
,X
2
,X
3
,⋅⋅⋅,X
n
的错排数为
P(X1,X2,X3,⋅⋅⋅,Xn)=n!−r1(n−1)!+r2(n−2)!−⋅⋅⋅+(−1)krk(n−k)!+⋅⋅⋅+(−1)nrn P\left( X_{1},X_{2},X_{3}, \cdot \cdot \cdot ,X_{n} \right) = n! - r_{1}\left( n - 1 \right)! + r_{2}\left( n - 2 \right)! - \cdot \cdot \cdot + \left( - 1 \right)^{k}r_{k}\left( n - k \right)! + \cdot \cdot \cdot + \left( - 1 \right)^{n}r_{n}
P(X
1
,X
2
,X
3
,⋅⋅⋅,X
n
)=n!−r
1
(n−1)!+r
2
(n−2)!−⋅⋅⋅+(−1)
k
r
k
(n−k)!+⋅⋅⋅+(−1)
n
r
n
式中rk r_{k}r
k
表示有 k kk 个元素在禁位上的个数
复杂度：
例题
HDU2204 容斥：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
分析：小于N NN的Mk M^kM
k
的个数为⌊N−−√k⌋ \lfloor \sqrt[k]{N}\rfloor⌊
k
N
⌋。枚举所有的k的话。显然有东西算重了。(比如1,我们可以每个k都不统计，最后加1)
首先，如果k不是质数e.g.Mk=Mp1p2 e.g.M^k=M^{p1p2}e.g.M
k
=M
p1p2
，则Mk M^kM
k
就以(Mp1)p2 (M^{p1})^{p2}(M
p1
)
p2
的形式被⌊N−−√p2⌋ \lfloor \sqrt[p_2]{N}\rfloor⌊
p
2
N
⌋统计过了。于是所有和数都不用统计。
其次，我们发现上面的例子里Mk M^kM
k
被⌊N−−√p1⌋ \lfloor \sqrt[p_1]{N}\rfloor⌊
p
1
N
⌋⌊N−−√p2⌋ \lfloor \sqrt[p_2]{N}\rfloor⌊
p
2
N
⌋都统计了。于是我们做容斥，K包含1个质数-K包含2个质数+3个…
最后，注意到260>1018 2^{60}>10^{18}2
60
>10
18
所以容斥到三个质数即可，最大的质数取到59。
hdu1205鸽巢：显然的想法题，但不会用鸽巢原理证明。
hdu5525 约数乘积: n=pe11⋅pe22⋯pekk n=p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}n=p
1
e
1
⋅p
2
e
2
⋯p
k
e
k
对于每个质数，它被乘入答案的次数为Σi≤ei=1i⋅d(npe) \Sigma_{i=1}^{i\leq e}i\cdot d(\frac{n}{p^e})Σ
i=1
i≤e
i⋅d(
p
e
n
),d(n)为因数个数。
∏i≤ki=1p(Σj≤eij=1j⋅d(npeii))i \prod_{i=1}^{i\leq k}p_i^{(\Sigma_{j=1}^{j\leq e_i}j\cdot d(\frac{n}{p_i^{e_i}}))}
i=1
∏
i≤k
p
i
(Σ
j=1
j≤e
i
j⋅d(
p
i
e
i
n
))
注意指数上要模p-1，所以不能用除法。对于/2有2∣(n+1)n 2|(n+1)n2∣(n+1)n 直接把2乘到模数上。对于(1+ei) (1+e_i)(1+e
i
)维护前后缀积。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
long long ans,n;
int i;
void dfs(int j,int num,int p){
if(p==0){
long long t=pow(n,1.0/num);
if(pow(t,0.0+num)>n) t--;
t--;
if(t>0)
//i为奇数则加，否则减
ans+=t*(i&1?1:-1);
return ;
}
if(j>=17)
return;//超出60以内素数，不予考虑
if(num*prime[j]<60) //仍在范围内，继续搜
dfs(j+1,num*prime[j],p-1);
dfs(j+1,num,p);
}
int main(){
while(scanf("%I64d",&n)!=EOF){
ans=0;
for(i=1;i<=3;i++)
dfs(0,1,i);
printf("%I64d\n",ans+1);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//T2
const int N=2e5+10,M=4e6+10,inf=2147483647;
const ll INF=1e18+10,mod=1e9+7;
/// 数组大小
int prime(int n)
{
if(n<=1)
return 0;
if(n==2)
return 1;
if(n%2==0)
return 0;
int k, upperBound=n/2;
for(k=3; k<=upperBound; k+=2)
{
upperBound=n/k;
if(n%k==0)
return 0;
}
return 1;
}
vector<int>p;
int si[N];
void init()
{
for(int i=2;i<=100000;i++)
if(prime(i))
p.push_back(i);
}
ll quick(ll a,ll b,ll c)
{
ll ans=1;
while(b)
{
if(b&1)ans=(ans*a)%c;
b>>=1;
a=(a*a)%c;
}
return ans;
}
int main()
{
init();
int n;
while(~scanf("%d",&n))
{
memset(si,0,sizeof(si));
for(int i=1;i<=n;i++)
{
int z;
int x=i;
scanf("%d",&z);
for(int j=0;j<p.size();j++)
{
if(1LL*p[j]*p[j]>x)break;
if(x==1)break;
while(x%p[j]==0)
{
si[j]+=z;
si[j]=(si[j])%(2*(mod-1));
x/=p[j];
}
}
if(x!=1)
{
int pos=lower_bound(p.begin(),p.end(),x)-p.begin();
si[pos]+=z;
}
}
ll sum=1;
for(int i=0;i<p.size();i++)
{
sum*=(si[i]+1);
sum%=(2*(mod-1));
}
//cout<<sum<<endl;
ll ans=1;
for(int i=0;i<p.size();i++)
{
ans=(ans*quick(p[i],((sum*si[i])%(2*(mod-1)))/2,mod))%(mod);
}
printf("%lld\n",ans);
}
return 0;
}
---------------------
版权声明：本文为CSDN博主「Best KeyBoard」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41848675/article/details/98993516
