Description：

有一个序列，为每个位置染上 $m$ 种颜色中的一种，如果恰好出现了 $s$ 次的颜色有 $k$ 种, 则会产生 $w[k]$ 的愉悦度。

求对于所有可能的染色方案，能获得的愉悦度的和对 $1004535809$ 取模的结果是多少。

$1\leqslant n\leqslant 10^7,1\leqslant m\leqslant 10^5$

Solution：

首先要知道 $1004535809$ 的原根是 $3$ ，出题人出一个计数题模数用了一个 $NTT$ 模数但是没有用常见的 $998244353$ 说明这题一定是 $NTT$ 。

先列式子，设 $x=\min(\lfloor\frac n S\rfloor,m)$ 出现了恰好 $s$ 次有一个经典的组合数型容斥： $$ \begin{align} ans&=\sum_{k=0}^xw[k]\times \sum_{i=k}^x(-1)^{i-k}{i\choose k}{m\choose i}{n\choose si}\times\frac{(si)!}{(s!)^i}\times(m-i)^{n-si} \end{align} $$ 如果设 $a[i]=\frac{(-1)^i}{i!},b[i]=\frac{(m-i)^{n-si}}{(m-i)!(n-si)!(s!)^i}$ ，那么： $$ ans=\sum_{k=0}^xw[k]\times\frac{m!n!}{k!}\sum_{i=k}^xa[i-k]\times b[i] $$ 也就是说我们要求两个下标差是一定的位置对应相乘再求和，根据套路把 $b$ 串反过来后面那部分就是： $$ \sum_{i=k}^xa[i-k]\times b[i]=\sum_{i=k}^xa[i-k]\times b'[x-i]=\sum_{i=0}^{x-k}a[i]\times b'[x-k-i] $$ 于是就构成了一个卷积形式，用 $NTT$ 求解即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,s;

#define MAXN 10000010

#define MAXM 400010

typedef long long ll;

ll w[MAXM];

ll fac[MAXN],inv[MAXN];

#define P 1004535809

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

ll ni(ll k){return power(k,P - 2);}

ll C(int n,int m)

{

	return fac[n] * inv[m] % P * inv[n - m] % P;

}

ll a[MAXM],b[MAXM];

int rev[MAXM];

ll ww[MAXM << 1],*g = ww + MAXM;

void NTT(ll f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		ll wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			ll w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i] = f[i] * ni((ll)l) % P;

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	for(int i = 0;i <= m;++i)scanf("%lld",&w[i]);

	fac[0] = 1;for(int i = 1;i < MAXN;++i)fac[i] = fac[i - 1] * i % P;

	inv[MAXN - 1] = ni(fac[MAXN - 1]);

	for(int i = MAXN - 2;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % P;

	ll ans = 0;

	int x = min(m,n / s);

	for(int i = 0;i <= x;++i)

	{

		b[i] = inv[m - i] * inv[n - s * i] % P * ni(power(fac[s],i)) % P * power(m - i,n - s * i) % P;

		a[i] = power(-1,i) * inv[i] % P;

	}

	for(int i = 0,j = x;i < j;++i,--j)swap(b[i],b[j]);

	int l = 0,len = 1;

	for(;len <= 2 * x;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	NTT(a,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)a[i] = a[i] * b[i] % P;

	NTT(a,len,-1);

	for(int k = 0;k <= x;++k)

	{

		ans = (ans + w[k] * a[x - k] % P * fac[m] % P * fac[n] % P * inv[k] % P) % P;

	}

	cout << ans << endl;

	return 0;

}