传送门

感觉自己是傻子系列

为了锻炼自己的推式子能力就去网上搜 $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$

然而就连高联组合恒等式的题目都做不出来的我还是洗洗睡吧

分类: 文章

quhengyi11

AFO 有缘再见

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注