[2016北京集训测试赛17]crash的游戏-[组合数+斯特林数+拉格朗日插值]
DescriptionSolution核心思想是把组合数当成一个奇怪的多项式，然后拉格朗日插值。。；哦对了，还要用到第二类斯特林数（就是把若干个球放到若干个盒子）的一个公式：$x^{n}=\sum _{i=0}^{n}C(n,i)*i!*S(i,x)$围观大佬博客（qaq公式太难打了）Code#in...
CF932E Team Work（第二类斯特林数）
传送门：CF原网 洛谷题意：给定 $n,k$，求 $\sum\limits^n_{i=1}\dbinom{n}{i}i^k\bmod(10^9+7)$。$1\le n\le 10^9,1\le k\le 5000$。很水的一道题。根据第二类斯特林数的性质：$$n^k=\sum^k_{i=1}\beg...
GDOI2018 滑稽子图 [斯特林数，树形DP]
传送门并没有思路见到那么小的\(k\)次方，又一次想到斯特林数。\[ans=\sum_{T} f(T)^k = \sum_{i=0}^k i!S(k,i)\sum_{T} {f(T)\choose i}\]很套路地，考虑后面那个式子的组合意义：对于每一个点集的导出子图，选出\(i\)条边的方案数。很...
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）题面51NOD\[\sum_{i=1}^n\sum_{j=1}^nsgcd(i,j)^k\]其中\(sgcd\)表示次大公约数。题解明摆着\(sgcd\)就是在\(gcd\)的基础上除掉\(gcd\)的最小因...
HDU 4372 Count the Buildings [第一类斯特林数]
有n(<=2000)栋楼排成一排，高度恰好是1至n且两两不同。现在从左侧看能看到f栋，从右边看能看到b栋，问有多少种可能方案。T组数据， (T<=100000)自己只想出了用DP搞发现最高的楼一定能看到，分成了左右两个问题f[i][j]表示i栋楼从左面可以看到j栋方案数，转移枚举最高楼左...
【XSY1519】彩灯节 DP 数学 第二类斯特林数
题目大意有\(n\)盏灯，\(m\)个限制。每个限制\((x,y)\)表示第\(x\)盏灯与第\(y\)盏灯之间必须且只能亮一盏。记一种情况\(x\)亮着的灯的数量为\(f_x\)，求\(\sum {(f_x)}^k\)\(n\leq 200000,k\leq 100\)题解我们先把整张图黑...
【BZOJ5119】【CTT2017】生成树计数 DP 分治FFT 斯特林数
CTT=清华集训 题目大意 有 n 个点，点权为 ai ，你要连接一条边，使该图变成一颗树。 对于一种连边方案 T ，设第 i 个点的度数为 di ，那么这棵树的价值为： val(T)=(∏i=1nadiidmi...
HDU4625 JZPTREE 【树形DP】【第二类斯特林数】
题目大意:对1到n求题目中描述的那个式子。题目分析：幂不好处理，转化为斯特林数。根据$ n^k= \sum_ { i=0 }^k S(k,i)×i!×C(n,i) $。我们可以将问题转化为对每个u和$ j=1 \sim k $求$ \sum_ { i=1 }^n \binom{dist(u,i)}{...
【BZOJ2159】Crash的文明世界（第二类斯特林数，动态规划）
【BZOJ2159】Crash的文明世界（第二类斯特林数，动态规划）题面BZOJ洛谷题解看到\(k\)次方的式子就可以往二项式的展开上面考，但是显然这样子的复杂度会有一个\(O(k^2)\)，因此需要换别的方法。注意到自然指数幂和第二林斯特林数之间的关系：\[n^k=\sum_{i=0}^k \be...
51nod1847 奇怪的数学题 (Min_25筛+第二类斯特林数)
link\(\sum_{i=1}^n\sum_{j=1}^n\mathrm{sgcd}(i,j)^k=\sum_{p=1}^ns(p)^k\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=p]=\sum_{p=1}^ns(p)^k(-1+2\sum_{i=1}^{n/p}\var...
BZOJ5093 图的价值（NTT+斯特林数）
显然每个点会提供相同的贡献。于是现在只考虑1号点的贡献。若其度数为i，则在2~n号点选i个连上，剩下的边随便连，这样可以算出答案为这个式子可以O(n)计算。发现k比较小，于是考虑如何将这个式子化为与k有关的求和。显然前面一部分可以直接提走。考虑后面一部分的组合意义：n-1个有标号盒子里面选i个，放进...
BZOJ.2159.Crash的文明世界(斯特林数 树形DP)
BZOJ洛谷挺套路但并不难的一道题\(Description\)给定一棵\(n\)个点的树和\(K\)，边权为\(1\)。对于每个点\(x\)，求\(S(x)=\sum_{i=1}^ndis(x,i)^K\)。\(n\leq50000,\ k\leq150\)。\(Solution\)和其它求\(x...
[BJOI2019]勘破神机（斯特林数+二项式定理+数学）
题意：f[i],g[i]分别表示用1*2的骨牌铺2*n和3*n网格的方案数，求ΣC(f(i),k)和ΣC(g(i),k)，对998244353取模，其中l<=i<=r，1<=l<=r<=1e18题解：显然打表发现f[i]为斐波那契数列，g[2i+1]=0,g[2i]=4...
Codeforces 1097G Vladislav and a Great Legend [树形DP，斯特林数]
洛谷Codeforces这题真是妙的很。通过看题解，终于知道了\(\sum_n f(n)^k\)这种东西怎么算。update：经过思考，我对这题有了更深的理解，现将更新内容放在原题解下方。思路发现\(\sum_S (f(S))^k\)这东西因为有个\(k\)次方，所以特别难算，考虑拆开：\[x^k...
【BZOJ4555】【TJOI2016】【HEOI2016】求和 第二类斯特林数 NTT
题目大意求\(f(n)=\sum_{i=0}^n\sum_{j=0}^i2^j\times j!\times S(i,j)\\\)对\(998244353\)取模\(n\leq 100000\)。题解\[\begin{align}S(n,k)&=\frac1{k!}\sum_{i=0}^k{...
【CF715E】Complete the Permutations 第一类斯特林数
题目大意有两个排列 \(p,q\)，其中有一些位置是空的。你要补全这两个排列。定义 \(s(p,q)\) 为 每次交换 \(p\) 中的两个数，让 \(p=q\) 的最小操作次数。求 \(s(p,q)=0,1,2,\ldots,n-1\) 的方案数。\(n\leq 300\)题解考虑 \(s(p,q...
斯特林数 - 环排列 学习小记 Hdu 3625 Examining the Rooms + LightOJ 1326 Race
环排列 定义 从n个不同的元素中仅取m（1≤m≤n）个不同的元素按照圆圈排列，这种排列叫做从n个元素里取m个元素的环排列。两个环排列，如果元素间的位置没有改变，就是同一排列。 计算公式 把一个m个元素的环在m个不同的位置拆开记得到m个不同的线排列。由于n个不同元素中任取m个元素的排列方法为...
BZOJ5093图的价值(斯特林数)
题目描述“简单无向图”是指无重边、无自环的无向图（不一定连通）。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大，请对998244353取模输出。题解因为懒得敲公式了，所以就直接粘题解了。我们发现在这张图中每个点都是等价的，所...
洛谷P4827 [国家集训队] Crash 的文明世界 [斯特林数，组合数，DP]
传送门思路又见到这个\(k\)次方啦！按照套路，我们将它搞成斯特林数：\[ans_x=\sum_{i=0}^k i!S(k,i)\sum_y {dis(x,y) \choose i}\]前面可以枚举，考虑后面那东西怎么求。我们不知道为什么但就是考虑DP：设：\[dn_{x,t}=\sum_{y\in...