题解
好像 $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);
}
0 条评论