杂项记录

2022/4/13 23:18:13

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

一、格雷码

手动构造方法

\(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。
741af9a83ba61984f3002681a4e97715.png
 而经过上文变化后,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;
}


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


扫一扫关注最新编程教程