传送门

题解

好像 $GD$考这种计数题考的还是蛮多的呢。

不过这题还算比较简单吧,至少 $qhy$能列对式子 (不过有些化简过程还是参考了一些题解)

首先考虑 $\geq k$个颜色出现 $s$次的方案数,即

$$
\left(
\begin{array}{c}
m\\k
\end{array}
\right)
\left(
\begin{array}{c}
n\\ks
\end{array}
\right)
\frac{(ks)!}{(s!)^k}
(m-k)^{n-sk}
$$

大概就是选下颜色,选下位置,因为位置是有标号的所以排列一下,然后把剩余的位置用剩余颜色乱填的方案数

然后根据容斥原理,我们很容易求出 $k$个颜色出现 $s$次的方案数

这里具体来讲,容斥的东西是在 $m-k$个颜色中 $\geq i-k$个颜色出现 $s$次,根据 $i-k$的奇偶性来确定正负,所以 $C_m^k$要提出来

$$
\left(
\begin{array}{c}
m\\k
\end{array}
\right)
\sum_{i\geq k}
(-1)^{i-k}
\left(
\begin{array}{c}
m-k\\i-k
\end{array}
\right)
\left(
\begin{array}{c}
n\\is
\end{array}
\right)
\frac{(is)!}{(s!)^i}
(m-i)^{n-si}
$$

然后枚举一下 $k$就是答案了,显然 $k$的范围是比较小的,我们记它的上界为 $up$,则 $up=min(m,\frac n s)$

$$
ans=\sum_{k=0}^{up}
w_k
\left(
\begin{array}{c}
m\\k
\end{array}
\right)
\sum_{i\geq k}
(-1)^{i-k}
\left(
\begin{array}{c}
m-k\\i-k
\end{array}
\right)
\left(
\begin{array}{c}
n\\is
\end{array}
\right)
\frac{(is)!}{(s!)^i}
(m-i)^{n-si}
$$

因为第二个求和后面都是关于 $i$的,所以提不出来什么东西能化简,如果这样就是 $O(n^2)$的复杂度,就是 $40$分

有一句话说的好,上帝给你关了一扇门,就会给你开一扇窗,这个窗便是交换枚举顺序 (雾)

$$
\sum_{i=0}^{up}
(-1)^i
\left(
\begin{array}{c}
n\\is
\end{array}
\right)
\frac{(is)!}{(s!)^i}
(m-i)^{n-si}
\sum_{k=0}^i
w_k(-1)^{k}
\left(
\begin{array}{c}
m\\k
\end{array}
\right)
\left(
\begin{array}{c}
m-k\\i-k
\end{array}
\right)
$$

注意一下这里 $-1$提了一些出来

可是你发现还是复杂度很高呀

然后你就会发现

$$
\left(
\begin{array}{c}
m\\k
\end{array}
\right)
\left(
\begin{array}{c}
m-k\\i-k
\end{array}
\right)
=\frac{m!}{k!(i-k)!}
$$

代回去看看

$$
\sum_{i=0}^{up}
(-1)^i
\left(
\begin{array}{c}
n\\is
\end{array}
\right)
\frac{(is)!}{(s!)^i}
(m-i)^{n-si}
\frac{m!}{(m-i)!}
\sum_{k=0}^i
\frac{w_k(-1)^{k}}{k!}
\frac{1}{(i-k)!}
$$

后面那个东西用 $NTT$卷积一下就可以 $O(mlogm)$求了

总复杂度 $O(mlogm + n + m)$

然而这道数学题竟然被我写代码写炸了

原因是自己的 $fac[]$和 $invfac[]$没开够,在算组合数的时候这两个都要算到与 $n$同阶

这么蠢的错误要记住了 $QwQ$

#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define N 400005
#define mod 1004535809
#define ll long long 
const double pi = acos(-1);
int R[N], L, len, n, m;
ll c1[N], c2[N], w[N], iw[N], invlen;
inline ll pow (ll x, int y)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
inline void init ()
{
    len = 1;
    while (len <= m + m) len = len << 1, ++L;
    invlen = pow(len, mod - 2);
    for (int i = 0; i < len; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << L - 1);
    w[0] = 1; w[1] = pow(3, (mod - 1) / len);
    for (int i = 2; i < len; ++i) w[i] = w[i - 1] * w[1] % mod;
    iw[0] = 1; iw[1] = pow(w[1], mod - 2);
    for (int i = 2; i < len; ++i) iw[i] = iw[i - 1] * iw[1] % mod;
}
inline void ntt (ll *c, int len, bool opt)
{
    for (int i = 0; i < len; ++i) if (i < R[i]) std::swap(c[i], c[R[i]]);
    for (int l = 2; l <= len; l <<= 1)
    {
        int mid = l >> 1, now = len / l;
        for (ll *p = c; p != c + len; p += l)
            for (Re int i = 0; i < mid; ++i)
            {
                ll tmp = (opt ? w[now * i] : iw[now * i]) * p[mid + i] % mod;
                p[mid + i] = (p[i] - tmp) % mod;
                p[i] = (p[i] + tmp) % mod;
            }
    }
}
int s;
ll W[N], fac[10000005], invfac[10000005], ans;
int sgn (int x) {return x & 1 ? -1 : 1;}
ll C (int x, int y) {return fac[x] * invfac[y] % mod * invfac[x - y] % mod;}
int main()
{
    scanf("%d %d %d", &n, &m, &s);
    fo (i, 0, m) scanf("%lld", &W[i]);
    invfac[0] = fac[0] = 1;
    int q = std::max(n, m);
    fo (i, 1, q) fac[i] = fac[i - 1] * i % mod;
    invfac[q] = pow(fac[q], mod - 2);
    fd (i, q - 1, 1) invfac[i] = invfac[i + 1] * (i + 1) % mod;
    init();
    fo (i, 0, m)
    {
        c1[i] = W[i] * sgn(i) * invfac[i] % mod;
        c2[i] = invfac[i];
    }
    ntt(c1, len, 1);
    ntt(c2, len, 1);
    fo (i, 0, len) c1[i] = c1[i] * c2[i] % mod;
    ntt(c1, len, 0);
    fo (i, 0, len) c1[i] = c1[i] * invlen % mod;
    int up = std::min(n / s, m);
    fo (i, 0, up)
    {
        int si = s * i;
        ans = (ans + sgn(i) * pow(m - i, n - si) * fac[m] % mod * invfac[m - i] % mod * C(n, si) % mod * fac[si] % mod * pow(invfac[s], i) % mod * c1[i] % mod) % mod;
    }
    printf("%lld", (ans + mod) % mod);
}
分类: 文章

quhengyi11

AFO 有缘再见

0 条评论

发表评论

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