感觉自己是傻子系列
为了锻炼自己的推式子能力就去网上搜 $stirling$数随机到了这一题
然后就开始愉快的推啦！
首先很容易发现每个数 $w_i$是等价的，我们只需要考虑一个数的贡献
由题意，我们就枚举这个数在大小为 $j$的集合里，那么有
$$\sum_{j=1}^n jC_{n-1}^jS_{n-j-1}^{k-1}$$
第一次竟然忘记了后面要乘 $stirling$数结果咕咕了好久
然后就想着能不能把 $stirling$数推出一个类似组合数一样的公式来由 $S_n^m$快速推到 $S_{n+1}^m$
然后发现我在痴心妄想.jpg
首先显然我们把 $stirling$数的公式化简弄出来
$$S_n^m=\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}$$
这个式子算一遍显然是 $O(mlogn)$复杂度 $gg$，递推公式也是没啥用的就自闭了
然后就去翻了题解
然后竟然只要改变一下枚举顺序神奇的事情就发生了！
我们考虑将当前的数分到大小为 $i$的集合里的方案数
如果当前集合大小为 $0$(也就是这个数被自分为一组)，显然此时的贡献为 $S_{n-1}^{k-1}$
如果当前集合的大小为 $i>0$，假设现在其它 $n-1$个集合被分成 $k$个集合以后每个集合有 $a_i$个元素，那么也就是把当前这个数随便丢到 $k$个集合中的一个，容易知道丢到第 $i$个集合的贡献为 $a_i+1$，那么所有的贡献就是 $\sum_{i=1}^k a_i+1=n-1+k$，于是这一段的贡献为 $(n-1+k)S_n^{k-1}$
记 $sum = \sum w_i$
则答案为 $S_{n-1}^{k-1} + (n-1+k)S_{n-1}^{k}$
感觉我想不到这种神奇的做法 $QAQ$
然后因为自己把 $\%=$打成 $\%$又 $WA$了好几次= =
#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define mod 1000000007
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 200005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
inline void read (int &x)
{
x = 0;
Re char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int n, w;
struct edge {
int nxt, v;
} e[N << 1];
int head[N], tot, k;
inline void addedge (int u, int v)
{
e[++tot] = (edge) { head[u], v };
head[u] = tot;
}
ll invfac[N], fac[N], ans, sum;
inline ll pow (ll x, int y)
{
ll ret = 1;
if (y < 0) return 0;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
inline ll C (int n, int m) { return fac[n] * invfac[m] % mod * invfac[n - m] % mod; }
inline ll S (int n, int m)
{
ll ret = 0;
fo (k, 0, m)
(ret += (k & 1 ? -1 : 1) * invfac[k] * invfac[m - k] % mod * pow(m - k, n)) %= mod;
return ret;
}
int main ()
{
read(n); read(k);
fo (i, 1, n)
{
read(w);
sum = (sum + w) % mod; }
fac[0] = invfac[0] = 1;
fo (i, 1, n) fac[i] = fac[i - 1] * i % mod;
invfac[n] = pow(fac[n], mod - 2);
fd (i, n - 1, 1) invfac[i] = invfac[i + 1] * (i + 1) % mod;
printf("%lld\n", ((S(n - 1, k - 1) + S(n - 1, k) * (n + k - 1)) % mod * sum % mod + mod) % mod);
return 0;
}
于是我们知道了一个新结论
$$\sum_{j=1}^n jC_{n-1}^jS_{n-j-1}^{k-1}=S_{n-1}^{k-1} + (n-1+k)S_{n-1}^{k}$$
超级好奇有没有非组合意义的证明方法 $QAQ$
然而就连高联组合恒等式的题目都做不出来的我还是洗洗睡吧
0 条评论