\(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\)个盒子,可以分为两种情况:
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; }