斯特林数和分拆数
2022/4/16 6:19:09
本文主要是介绍斯特林数和分拆数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
上升幂与下降幂
- 上升幂:\(x^{\overline{n}}=\prod_{k=0}^{n-1}(x+k)=x(x+1)(x+2)...(x+n-1)\)
- 下降幂:\(x^{\underline{n}}=\frac{x!}{(x-n)!}=\prod_{k=0}^{n-1}(x-k)\)
第一类斯特林数(无符号)
-
定义:第一类斯特林数(斯特林轮换数)\(n\brack k\),也可记做\(s(n,k)\) ,表示将\(n\)个两两不同的元素,划分为\(k\)个互不区分的非空轮换的方案数。一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换\([A,B,C,D]\) ,并且我们认为\([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\) ,即,两个可以通过旋转而互相得到的轮换是等价的。注意,我们不认为两个可以通过翻转而相互得到的轮换等价,即\([A,B,C,D]\neq [D,C,B,A]\) 。(另一种理解:将 \(n\) 个元素,划分为 \(k\) 个圆排列的方案数)
-
递推式:\({n\brack k}={n-1\brack k-1}+(n-1){n-1 \brack k}\)。边界\({n\brack 0}=[n=0]\)
组合意义:将该新元素置于一个单独的轮换中,共有\({n-1\brack k-1}\)中方案;将该元素插入到任何一个现有的轮换中,共有\((n-1){n-1 \brack k}\)种方案。
-
性质
\(\sum_{k=0}^n{n\brack k}=n!\)
\({n\brack n-1}=\binom{n}{2}\)
\({n\brack 2}=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}\)
\({n\brack 1}=(n-1)!\)
生成函数(同行) 上升幂:\(F_n(x)=x^{\overline{n}}=\prod_{i=0}^{n-1}(x+i)=\frac{(x+n-1)!}{(x-1)!}=\prod_{i=0}^n{n\brack i}x^i\)
\(O(nlogn)\)
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //freopen("gen.in","r",stdin); Poly::init(19); auto CDQ=[&](auto self,int l,int r)->Poly::poly{ if(l==r) return Poly::poly({l,1}); int mid=l+r>>1; return Poly::poly_mul(self(self,l,mid),self(self,mid+1,r)); }; int n; cin>>n; Poly::poly F=CDQ(CDQ,0,n-1); for(int i=0;i<=n;i++) cout<<F[i]<<" "; return 0; }
生成函数(同列):\(F(x)=\sum_{i=1}^n\frac{(i-1)!x^i}{i!}=\sum_{i=1}^n\frac{x^i}{i}=\sum_{i=1}^n{i \brack k}x^i\)
第二类斯特林数(无符号)
-
定义:第二类斯特林数(斯特林子集数)\(n \brace k\),也可记做\(S(n,k)\) ,表示将\(n\)个两两不同的元素,划分为\(k\) 个互不区分的非空子集的方案数
-
递推式:\({n\brace k}={n-1\brace k-1}+k{n-1\brace k}\)
组合意义:插入一个新元素时,可以将这个元素单独放入一个子集,也可以将这个元素放入现有的一个非空子集
-
通项公式:\({n\brace m}=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}\)
-
性质
\(\sum_{k=0}^n{n\brace k}=B_n\),\(B_n\)为贝尔数
\(n^k=\sum_{i=1}^k{k\brace i}\times i!\times \binom{n}{i}=\sum_{i=1}^k{k\brace i}\times n^{\underline{i}}\),这个可以用来求自然数数幂和:\(\sum_{i=1}^n i^k=\sum_{i=1}^n\sum_{j=0}^k{k\brace j}\times j!\times \binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\sum_{i=1}^n\binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\times \binom{n+1}{j+1}=\sum_{j=0}^k{k\brace j}\frac{(n+1)^{\underline{j+1}}}{(j+1)!}\)
-
同一行第二类斯特林数通项公式计算\(O(nlogn)\)
int main() { scanf("%d", &n); poly f(n + 1), g(n + 1); for (int i = 0; i <= n; ++i) g[i] = (i & 1 ? mod - 1ll : 1ll) * infac[i] % mod, f[i] = 1ll * qpow(i, n) * infac[i] % mod; poly F=poly_mul(f,g); F.resize(n + 1); for (int i = 0; i <= n; ++i) printf("%d ", F[i]); return 0; }
分拆数
-
定义:将正整数\(n\)进行整数拆分的方案数
-
求法:
- 完全背包,把数字\(1-n\)看做价值为\(1\),容量为\(i\)的物品,进行完全背包
- 五边形定理
#include <stdio.h> long long a[100010]; long long p[50005]; int main() { p[0] = 1; p[1] = 1; p[2] = 2; int i; for (i = 1; i < 50005;i++) /*递推式系数1,2,5,7,12,15,22,26...i*(3*i-1)/2,i*(3*i+1)/2*/ { a[2 * i] = i * (i * 3 - 1) / 2; /*五边形数为1,5,12,22...i*(3*i-1)/2*/ a[2 * i + 1] = i * (i * 3 + 1) / 2; } for ( i = 3; i < 50005; i++) /*p[n]=p[n-1]+p[n-2]-p[n-5]-p[n-7]+p[12]+p[15]-...+p[n-i*[3i-1]/2]+p[n-i*[3i+1]/2]*/ { p[i] = 0; int j; for (j = 2; a[j] <= i; j++) /*有可能为负数,式中加1000007*/ { if (j & 2) { p[i] = (p[i] + p[i - a[j]] + 1000007) % 1000007; } else { p[i] = (p[i] - p[i - a[j]] + 1000007) % 1000007; } } } int n; while (~scanf("%d", &n)) { printf("%lld\n", p[n]); } }
-
\(k\)个部分的分拆,记作\(p(n,k)\)
\(p(n,k)=p(n-1,k-1)+p(n-k,k)\)
例题
2021CCPC Guangzhou A
参考:OIWiki
这篇关于斯特林数和分拆数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)