杂项记录

本文主要是介绍杂项记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、格雷码

手动构造方法

\(k\)位格雷码可以由以下方法构造：
1.翻转最低位得到下一个格雷码（e.g. 000->001）
2.将最右位的1的左边的位翻转得到下一个格雷码（e.g. 001->011）
交替上述策略\(2^k-1\)次。

计算方法

观察\(G(n)\)与n的二进制，可以发现如果\(G(n)\)的\(i\)位是1，那么n的\(i\)位是1，\(i+1\)位是0||第\(i\)位是0，\(i+1\)位是1.
用代码实现：

int g(int n) {return n^(n>>1);}

证明

 考虑n和n+1的区别，n+1相当于是将n二进制末尾的k个连续的1变成0，k+1位由0变成1。

 而经过上文变化后，n和n+1的后k位都会变成10000...0(k个)，而k+1位不同。

代码

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> num;
        for(int i=0;i<=((1<<n)-1);i++){
            num.push_back(i^(i>>1));
        }
        return num;
    }
};

格雷码逆变换

二、第二类斯特林数

\(S(n,k)\)，表示将n个两两不同的元素，划分为k个互不区分的非空子集的方案数（即将n个不同小球放在k个相同盒子里）。
递推式为：\(S(i,j)=S(i-1,j)*j+S(i-1,j-1)\)
考虑将\(i-1\)个球放入\(j\)个盒子，可以分为两种情况：

1. 将插入的球放在\(j\)个已经放好的盒子里，有\(j\)种放法。
2. 先将\(i-1\)个球放在\(j-1\)个盒子里，在将插入的球放在剩下的盒子里，由于盒子是不同的，所以加上\(S(i-1,j-1)\)即可。

代码实现

int s[10][10];
int main(){
	int n,m;
	cin>>n>>m;
	s[0][1]=1;
	for(int i=0;i<=n;i++){     
		//从放0个球开始算,最后算到n个球放到n个盒子为止
		for(int j=1;j<=i;j++){
			s[i][j]=s[i-1][j]*j+s[i-1][j-1];
		}
	}
	cout<<s[n][m];
	//cout<<s[n][m]*factory[m];   如果盒子不同要乘上m！
	
	return 0;
}

公式计算

FFT卷积（我不会qwq）

int main() {
  scanf("%d", &n);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
  exgcd(fact[n], mod, ifact[n], ifact[0]),
      ifact[n] = (ifact[n] % mod + mod) % mod;
  for (int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
  poly f(n + 1), g(n + 1);
  for (int i = 0; i <= n; ++i)
    g[i] = (i & 1 ? mod - 1ll : 1ll) * ifact[i] % mod,
    f[i] = (ll)qpow(i, n) * ifact[i] % mod;
  f *= g, f.resize(n + 1);
  for (int i = 0; i <= n; ++i) printf("%d ", f[i]);
  return 0;
}

这篇关于杂项记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！