牛客国庆集训派对Day2（A F H）

链接： https://www.nowcoder.com/acm/contest/202#question

A. 矩阵乘法（分块）

题意： 给两个矩阵 A , B A, B A,B， A A A 是十进制矩阵， B B B 是二进制矩阵，问两个矩阵相乘之后得到的结果矩阵的每个元素的异或和。
思路： 因为 B B B 是二进制矩阵， B B B 矩阵最多只有 64 行，分块后，它的组合情况其实很少。 若对 A A A 分块， 每行每 8 个分一块，那 B B B 中就只有 256 种情况。 对矩阵 A A A 每行最多 8 个块的 256 种情况预处理，预处理时采用类似状压dp的方式，每个预处理的数只需要在之前的基础上加上二进制最后一位 1 对应的没被处理过的数就行了。（注意二进制全是0的时候一定是0不需要考虑）相乘的结果就是每行中的每块值对应查表，在加起来就是了。复杂度O(8 * n *m)。
（比赛时不会，看了题解，又看了别人代码才写出来。后来听说暴力也能过，我只能给牛客的评测机点个赞了。）

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
const int MAXN = 5000;
const int MAXP = 100;

int f[MAXN][10][300];
int n, p, m; 
int A[MAXN][MAXP]; 
int C[MAXN][MAXN];
unsigned long long B[MAXN];
int num[300];

int main(int argc, char const *argv[])
{
	scanf("%d%d%d", &n, &p, &m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < p; ++j) {
			scanf("%x", &A[i][j]);
		}
	}
	char c[100];
	for (int i = 0; i < m; ++i) {
		scanf("%s", c);
		for (int j = p-1; j >= 0; --j) {
			B[i] <<= 1;//|(c[j]^'0');
			B[i] += (c[j]^'0');
		}// cout<<B[i]<<endl;
	}

	for (int i = 1; i < 8; ++i) {
		num[1<<i] = i;//cout<<"num : "<<num[1<<i]<<endl;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 8; ++j) {
			for (int k = 1; k < 256; ++k) {// k == 0 的时候就是0， 从1开始
				f[i][j][k] = f[i][j][k^lowbit(k)] + A[i][j*8+num[lowbit(k)]];
				// cout<<f[i][j][k]<<" ";
			}// cout<<endl;
		}// cout<<endl<<endl;
	}
	// cout<<"sajdjas"<<endl;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			for (int k = 0; k < 8; ++k) {
				C[i][j] += f[i][k][B[j]>>(k*8)&255];				
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			ans ^= C[i][j];
			// cout<<C[i][j]<<" ";
		}//cout<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

F. 平衡二叉树（数据结构）

题意： 满足左右子树高度差不超过 d d d 的二叉树称为平衡二叉树。不平衡度是树中所有节点的左右子树的节点数之差的最大值。给定 d , n d, n d,n ，求不平衡度的最大值。
思路：
1.当 d > = n − 1 d >= n-1 d>=n−1 时，可以假定根节点的左子树是满二叉树，右子树是空树，直接输出 高度 n − 1 n-1 n−1 的满二叉树的节点个数 2 n − 1 − 1 2^{n-1} -1 2n−1−1 。
2.当 d &lt; n − 1 d &lt; n-1 d<n−1 时， 仿照之前的思路，假定根节点的左子树是满二叉树，右子树是符合平衡要求的节点最少的平衡二叉树。还记得最小平衡二叉树节点数公式吗
f ( h ) = { h   h ≤ d   f ( h − 1 ) + f ( h − 1 − d ) + 1   h &gt; d   f(h)= \begin{cases} h &amp; \text { $h \leq d$ } \\ f(h-1) + f(h-1-d) + 1 &amp; \text{ $h &gt; d$ } \end{cases} f(h)={hf(h−1)+f(h−1−d)+1​ h≤d  h>d ​
左子树的高度是 n − 1 n-1 n−1 , 所以右子树的高度只需要 n − 1 − d n-1-d n−1−d 就可以了，所以答案即 2 n − 1 − 1 − f ( n − 1 − d ) 2^{n-1} - 1 - f(n-1-d) 2n−1−1−f(n−1−d) 。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, d;

LL power(LL x, LL n) {
	LL res = 1;
	while(n) {
		if(n & 1) {
			res = (res*x);
		}
		x = x*x;
		n >>= 1;
	} 
	return res;
}

int main(int argc, char const *argv[])
{
	cin>>n>>d;
	LL f[100];
	if(n == 0) {
		cout<<0<<endl;
		return 0;
	}
	if(d >= n-1) {
		cout<<power(2, n-1)-1<<endl;
		return 0;
	}
	for (LL i = 0; i <= d; ++i) {
		f[i] = i;
	}
	for (LL i = d+1; i <= n-1-d; ++i) {
		f[i] = f[i-1] + f[i-1-d] + 1;
	}
	LL ans = power(2, n-1)-1 - f[n-1-d];
	cout<<ans<<endl;
	return 0;
}

H. 卡牌游戏（数论-期望）

题意 ： N N N 种牌， M M M 种稀有，每抽一次，会随机从 N N N 种牌选择一个，但 M M M 种牌不会重复抽到， 现在想得到 K K K 种稀有卡牌，问抽牌的次数的期望是多少。
思路：

1. 先考虑 K = = 1 K == 1 K==1 的情况，
   第一次抽到的概率是 M N \frac M N NM​
   第二次抽到的概率是 N − M N ∗ M N \frac {N-M} N * \frac M N NN−M​∗NM​
   …
   第 n n n 次抽到的概率是 ( N − M N ) n − 1 ∗ M N (\frac {N-M} N )^{n-1}* \frac M N (NN−M​)n−1∗NM​
   期望 E = 1 ∗ M N + 2 ∗ N − M N ∗ M N + . . . + n ∗ ( N − M N ) n − 1 ∗ M N E = 1 * \frac M N + 2 * \frac {N-M} N * \frac M N + ... + n * (\frac {N- M} N )^{n-1}* \frac M N E=1∗NM​+2∗NN−M​∗NM​+...+n∗(NN−M​)n−1∗NM​
   E = 1 − ( N − M N ) n 1 − N − M N − n ∗ ( N − M N ) n E = \frac {1 - (\frac {N-M} N)^n} {1 - \frac {N-M} N} - n * (\frac {N-M} N)^n E=1−NN−M​1−(NN−M​)n​−n∗(NN−M​)n
   当 n n n 趋于无穷时 E = N M E = \frac N M E=MN​
2. 当 K = = 2 K == 2 K==2 时， 因为 M M M 种稀有牌不会重复得到， 所以可以分解为两个子问题， 即可以理解为先从 N N N 种牌， M M M 种稀有中得到 1 1 1 种， 再从 N − 1 N-1 N−1种牌， M − 1 M-1 M−1 种稀有中得到 1 1 1 种。所以 E = N M + N − 1 M − 1 E = \frac N M + \frac {N-1} {M-1} E=MN​+M−1N−1​
3. 以此类推， 当 K = = K K == K K==K 时， E = ∑ i = 0 K − 1 N − i M − i E = \sum ^{K-1} _{i=0}\frac {N-i} {M-i} E=∑i=0K−1​M−iN−i​

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t, cas = 0;
    double n, m, k;
    cin>>t;
    while(t--) {
        cin>>n>>m>>k;
        double ans = 0;
        for(int i = 0; i < k; ++i) {
            ans += (n-i)/(m-i);
        }
        cout<<"Case #"<<++cas<<": "<<fixed<<setprecision(12)<<ans<<endl;
    }

    return 0;
}