我当然知道 CSP-S 前沉迷数数是不对的，但是就是停不下来啊……
一道比较套路的容斥题。
首先显然有 \(K\le\min(\lfloor\frac NS\rfloor,M)\)。
令 \(k = \min(\lfloor\frac NS\rfloor,M)\)。
设 \(f_i\) 表示至少 \(i\) 个颜色出现次数恰好为 \(S\) 的方案数。
则从 \(M\) 种颜色中选择 \(i\) 种颜色，再从 \(N\) 个位置中选择 \(iS\) 个位置，再考虑这 \(iS\) 个位置之间的颜色次序即多重集排列数，然后剩下 \(N - iS\) 个位置随便给一个这 \(m\) 个之外的颜色。
有 \[f_i = \binom Mi\binom N{iS}\frac{(iS)!}{(S!)^i}(m-i)^{N-iS}\]
再设 \(F_i\) 表示恰好有 \(i\) 个颜色出现次数恰好为 \(S\) 的方案数。
根据容斥原理易得 \[
\begin{align*}
F_i &= \sum\limits_{j=i}^k (-1)^{j-i}\binom ji F_j \\
&= \sum\limits_{j=i}^k (-1)^{j-i}\frac{j!}{i!(j-i)!} F_j \\
i! \cdot F_i &= \sum\limits_{j=i}^k j! \cdot f_j \cdot \frac{(-1)^{j-i}}{(j-i)!}
\end{align*}
\]
看起来有点卷积的味道了，但是还不能直接做。
令 \(A_i = i! \cdot f_i,B_i = \frac{(-1)^i}{i!}\)。
又 \(\sum\limits_{j=i}^k A_j \cdot B_{j-i} = \sum\limits_{j=0}^{k-i} A_{i+j} \cdot B_j\)。
注意到若令 \(A'_i = A_{k-i}\)，则原式化为 \(\sum\limits_{j=0}^{k-i} A'_{k-i-j} \cdot B_j\)。
熟悉的卷积，NTT 之后求 \(x^{k-i}\) 的系数即可。
答案即 \(\sum\limits_{i=0}^k W_i \cdot F_i\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using namespace std;
const int N = 1 << 18;
const int M = 1e7;
const int mod = 1004535809;
const int G = 3;
const int Gi = 334845270;
int n,m,s,k,w[N + 5];
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int f[N + 5],g[N + 5],omg[N + 5],inv[N + 5];
int fac[M + 5],ifac[M + 5],ans;
inline int C(int n,int m)
{
return (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
void ntt(int *a,int *omg,int n,int lg)
{
for(register int i = 0;i < n;++i)
{
int t = 0;
for(register int j = 0;j < lg;++j)
if(i & (1 << j))
t |= (1 << lg - j - 1);
if(i < t)
swap(a[i],a[t]);
}
for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
for(register int i = 0;i < n;i += w)
for(register int j = 0;j < m;++j)
{
int t = (long long)omg[n / w * j] * a[i + j + m] % mod;
a[i + j + m] = (a[i + j] - t + mod) % mod,a[i + j] = (a[i + j] + t) % mod;
}
}
void mul(int *a,int *b,int len)
{
int lg = 0,n = 1;
for(;n < len * 2;n <<= 1,++lg);
for(register int i = 0;i < n;++i)
omg[i] = fpow(G,(mod - 1) / n * i),inv[i] = fpow(Gi,(mod - 1) / n * i);
ntt(a,omg,n,lg),ntt(b,omg,n,lg);
for(register int i = 0;i < n;++i)
a[i] = (long long)a[i] * b[i] % mod;
ntt(a,inv,n,lg);
int n_inv = fpow(n,mod - 2);
for(register int i = 0;i < n;++i)
a[i] = (long long)a[i] * n_inv % mod;
}
int main()
{
scanf("%d%d%d",&n,&m,&s),k = min(n / s,m),fac[0] = 1;
for(register int i = 0;i <= m;++i)
scanf("%d",w + i);
for(register int i = 1;i <= max(n,m);++i)
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[max(n,m)] = fpow(fac[max(n,m)],mod - 2);
for(register int i = max(n,m);i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod;
for(register int i = 0;i <= k;++i)
f[i] = (long long)((i & 1) ? mod - 1 : 1) * ifac[i] % mod,g[i] = (long long)C(m,i) * C(n,i * s) % mod * fac[i * s] % mod * fpow(ifac[s],i) % mod * fpow(m - i,n - i * s) % mod * fac[i] % mod;
reverse(g,g + k + 1),mul(f,g,k + 1),reverse(f,f + k + 1);
for(register int i = 0;i <= k;++i)
ans = (ans + (long long)f[i] * ifac[i] % mod * w[i] % mod) % mod;
printf("%d\n",ans);
}