组合数学

  1. 1 【bzoj 3505】[Cqoi2014]数三角形
  2. 2 【bzoj 1005】[HNOI2008]明明的烦恼
  1. 抽屉原理(鸽笼原理)
  2. 容斥原理
  3. 加法原理
  4. 乘法原理
  5. 排列 A(n,m)=n!(nm)!A(n,m)=\frac{n!}{(n-m)!}
  6. 组合 C(n,m)=n!m!×(nm)!C(n,m)=\frac{n!}{m!\times (n-m)!}
    公式:
    C(n,m)=C(n,nm)C(n,m)=C(n,n-m)
    C(n,m)=C(n1,m)+C(n1,m1)C(n,m)=C(n-1,m)+ C(n-1,m-1)
  7. 可重复组合 方程x1+x2+…+xn=r的非负整数解的个数:
    可以理解为,将r个1排成一排,插入n-1个分隔符,把r个1分成n段,n段中的1的个数即是方程的一个解。
    插入n-1个分隔符的过程,实际上就是从n+r-1个位置中选择n-1个位置放分隔符,其余r个位置放1,
    共有C(n+r1,n1)=C(n+r1,r)C(n+r-1,n-1)=C(n+r-1,r)
  8. Catalan数 C(2n,n)n+1\frac{C(2n,n)}{n+1}
  9. CnmC_n^m中每个元素出现的次数为Cnm×m÷n=C(n1,m1)C_n^m \times m \div n=C(n-1,m-1)

1 【bzoj 3505】[Cqoi2014]数三角形

给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

总共有 C((n+1)×(m+1),3)C((n+1)\times (m+1),3)种方法
然后减去三点共线的
横着的和竖着的 C(m+1,3)×(n+1)+C(n+1,3)×(m+1)C(m+1,3) \times (n+1)+C(n+1,3) \times (m+1)
还有斜着的,对于点(i,j),要减去 (gcd(i,j)1)×2×(ni+1)×(mj+1)(gcd(i,j)-1)\times 2\times (n-i+1)\times (m-j+1)
gcd(i,j)1gcd(i,j)-1是因为对于(0,0)和(i,j)这条线,一定要选(0,0)和(i,j)两点,剩下还有gcd(i,j)-1个整点可选
22是因为左右对称后得到另一条线,即左上到右下和右上到左下
ni+1n-i+1是因为把这条线向下平移之后得到n-i+1条一样的线
mj+1m-j+1是向右平移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
using namespace std;
int n,m; long long ans;
long long C(int a,int b)
{
if(a-b<b) b=a-b;
if(b<=0) return !b;
long long aa=1,bb=1;
for(int i=1;i<=b;i++) aa*=a-b+i,bb*=i;
return aa/bb;
}
int gcd(int x,int y)
{
return !y?x:gcd(y,x%y);
}
int main()
{
scanf("%d%d",&n,&m);
ans=C((n+1)*(m+1),3)-C(n+1,3)*(m+1)-C(m+1,3)*(n+1);
for(int i=1,t;i<=n;i++)
for(int j=1;j<=m;j++)
ans-=(gcd(i,j)-1)*2*(n-i+1)*(m-j+1);
printf("%lld",ans);
}

2 【bzoj 1005】[HNOI2008]明明的烦恼

给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

Prüfer编码与Cayley公式
求在n-2个位置插入i使i出现di-1次的情况即可
在n-2中插入sure个数,共有C(n2,sure)C(n-2,sure)种方法
在sure位置中插入所有数字的排列为A(sure,sure)=sure!A(sure,sure)=sure!
但对于每一个i,有C(di1,di1)=(di1)!C(di-1,di-1)=(di-1)!个是重复的
而剩下不确定的,有unsuren2sureunsure^{n-2-sure}种情况

不想写高精就要分解质因数了
n!的分解质因数,质数p在n!中出现的次数为
如n=1000,p=3时,有:
1000/3+1000/9+1000/27+1000/81+1000/243+1000/729
=333+111+37+12+4+1
=498
所以每次除以p然后加起来就行了

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
using namespace std;
const int N=1005;
int n,tot,prime[N],sure,unsure,du[N],sum[N],len=1,ans[N]={0,1};
bool not_p[N];
void pre()
{
not_p[1]=1;
for(int i=2;i<=n;i++)
{
if(!not_p[i]) prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]*i<=n;j++)
{
not_p[prime[j]*i]=1;
if(!(i%prime[j])) break;
}
}
}
void fac(int a,int b)
{
for(int i=1;prime[i]<=a&&i<=tot;i++)
for(int j=a/prime[i];j;j/=prime[i])
sum[i]+=j*b;
}
void power(int a,int b)
{
for(int i=1,j;prime[i]<=a&&a&&i<=tot;i++)
while(!(a%prime[i])) sum[i]+=b,a/=prime[i];
}
int main()
{
scanf("%d",&n);pre();
for(int i=1;i<=n;i++)
{
scanf("%d",&du[i]);
if(!du[i]) {printf("%d\n",n==1);return 0;}
if(du[i]==-1) unsure++;
else sure+=du[i]-1;
}
if(n==1) {printf("%d",du[1]==-1?1:0);return 0;}
if(!unsure&&sure!=n-2) {printf("0");return 0;}
if(sure>n-2) {printf("0");return 0;}
fac(n-2,1);
fac(n-2-sure,-1);
for(int i=1;i<=n;i++)
if(du[i]>2) fac(du[i]-1,-1);
power(unsure,n-2-sure);
for(int i=1;i<=tot;i++)
while(sum[i])
{
for(int j=1;j<=len;j++) ans[j]*=prime[i];
for(int j=1;j<=len;j++)
if(ans[j]>=100000)
{
ans[j+1]+=ans[j]/100000;ans[j]%=100000;
if(j==len&&ans[j+1]) len++;
}
sum[i]--;
}
printf("%d",ans[len]);
for(int i=len-1;i>=1;i--) printf("%05d",ans[i]);
}