贺题记录 - 组合数学

• 2^k进制数 典 难　(值得一做!)

  简析

  1. 对于条件"作为 2^k 进制数，除最后一位外，r 的每一位严格小于它右边相邻的那一位"
     即 从左到右 数字为升序.　即 求组合数. (由于组合数对应的方案是无序的, 我们可以将之看作有序的)

  2. "将 r 转换为二进制数 q 后， q的总位数不超过 w"
     即r最多位数为 1. w/k 位 　2. w/k+1 位
     对于第 1 类(w/k位) 个数为: \(\displaystyle\sum_{i=2}^{w/k} C_{2^k-1}^i\)
     对于第 2 类(w/k+1位) 个数为 \(\displaystyle\sum_{i=1}^{2^{w\%k}-1} C_{2^k-1-i}^{w/k}\)

  AC代码: 直接约分 需要支持高精度(加 与 乘).
  AC代码: 消去因子 更快!

计算

• 求\(C_n^m\) 的几种方式

  1. \(C_n^m = \frac{(n)..(n-m+1)}{m!}\) \(O(M^2\log N)\) 直接约分.

     BIG CC(int m, int n){	// 常常会 需要用到 大整数
     	BIG res; if(m>n) return res;
     
     	int a[M], b[M];						// M: 最大的m
     	REP(i, 1, m) a[i]=n-m+i, b[i]=i;    // a: 分子的因子;  b: 分母的因子
     
         REP(i, 1, m){       				// 约分
             if(b[i]==1) continue;
             REP(j, 1, m){
                 int x=gcd(a[j], b[i]);
                 a[j]/=x, b[i]/=x;
     			if(b[i]==1) break;
     		}
     	}
     
     	res.init_int(1);
         REP(i, 1, m) res=res*a[i]; 			// 将 分母剩余的因子乘起来
     	return res;
     }
     

  2. 质因数分解, 约分 \(O(n\log n)\)

     BIG CC(int m, int n){
     	memset(P, 0, sizeof(P)); // 初始化 啊喂!!!!!!!!!
     	BIG res; if(m>n) return res;
     
     	REP(i, 1, pm){
     		ll p=prime[i], t;
     		if(p>n) break;
     		t=p; while(t<=n) P[i]+=n/t, t*=p;
     		t=p; while(t<=m) P[i]-=m/t, t*=p;
     		t=p; while(t<=(n-m)) P[i]-=(n-m)/t, t*=p;
     	}
     
     	res.init_int(1);
     	REP(i, 1, pm){
     		int k=0;
     		while(k