「HAOI2018」染色
是个套路题..
考虑容斥
则恰好为\(k\)个颜色恰好为\(c\)次的贡献为
\[\binom{m}{k}\sum_{i\ge k}(-1)^{i-k}\binom{m-k}{i-k}\binom{n}{si}\frac{(si)!}{(s!)^i}(m-i)^{n-si}
\]
\]
有两项最开始搞忘了..\(\binom{n}{si}\frac{(si)!}{(s!)^i}\)就是这两个
代表钦定\(si\)个位置去染，然后染色本身是个可重排列
设\(d=\min(\lfloor \frac{n}{s}\rfloor,m)\)
那么答案就是
\[\begin{aligned}
ans&=\sum_{k=0}^dw_k\binom{m}{k}\sum_{i\ge k}(-1)^{i-k}\binom{m-k}{i-k}\binom{n}{si}\frac{(si)!}{(s!)^i}(m-i)^{n-si}\\
&=\sum_{i=0}^d(-1)^i(m-i)^{n-si}\binom{n}{si}\frac{(si)!}{(s!)^i}\sum_{k=0}^iw_k\binom{m}{k}(-1)^k\binom{m-k}{i-k}\\
&=\sum_{i=0}^d(-1)^i(m-i)^{n-si}\frac{m!}{(m-i)!}\binom{n}{si}\frac{(si)!}{(s!)^i}\sum_{k=0}^i\frac{w_k(-1)^k}{k!}\frac{1}{(i-k)!}
\end{aligned}
\]
ans&=\sum_{k=0}^dw_k\binom{m}{k}\sum_{i\ge k}(-1)^{i-k}\binom{m-k}{i-k}\binom{n}{si}\frac{(si)!}{(s!)^i}(m-i)^{n-si}\\
&=\sum_{i=0}^d(-1)^i(m-i)^{n-si}\binom{n}{si}\frac{(si)!}{(s!)^i}\sum_{k=0}^iw_k\binom{m}{k}(-1)^k\binom{m-k}{i-k}\\
&=\sum_{i=0}^d(-1)^i(m-i)^{n-si}\frac{m!}{(m-i)!}\binom{n}{si}\frac{(si)!}{(s!)^i}\sum_{k=0}^i\frac{w_k(-1)^k}{k!}\frac{1}{(i-k)!}
\end{aligned}
\]
然后随便预处理卷一下就好了
Code:
#include <cstdio>
#include <cctype>
#include <algorithm>
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=(1<<20)+10;
using std::min;
using std::max;
const int mod=1004535809,Gi=334845270;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int w[N],a[N],b[N],fac[N*10],inv[N*10],turn[N];
void NTT(int *a,int len,int typ)
{
int L=-1;for(int i=1;i<len;i<<=1) ++L;
for(int i=0;i<len;i++)
{
turn[i]=turn[i>>1]>>1|(i&1)<<L;
if(i<turn[i]) std::swap(a[i],a[turn[i]]);
}
for(int le=1;le<len;le<<=1)
{
int wn=qp(typ?3:Gi,(mod-1)/(le<<1));
for(int p=0;p<len;p+=le<<1)
{
int w=1;
for(int i=p;i<p+le;i++,w=mul(w,wn))
{
int x=a[i],y=mul(w,a[i+le]);
a[i]=add(x,y);
a[i+le]=add(x,mod-y);
}
}
}
if(!typ)
{
int inv=qp(len,mod-2);
for(int i=0;i<len;i++) a[i]=mul(a[i],inv);
}
}
int main()
{
int n,m,s,len=1,u,d;
read(n),read(m),read(s);
for(int i=0;i<=m;i++) read(w[i]);
d=min(n/s,m);
while(len<=d) len<<=1;
u=max(n,max(m,len));
fac[0]=1;for(int i=1;i<=u;i++) fac[i]=mul(fac[i-1],i);
inv[u]=qp(fac[u],mod-2);
for(int i=u-1;~i;i--) inv[i]=mul(inv[i+1],i+1);
int ans=0;
for(int i=0;i<len;i++)
{
a[i]=mul(w[i],inv[i]);
if(i&1) a[i]=add(mod,-a[i]);
b[i]=inv[i];
}
NTT(a,len<<1,1),NTT(b,len<<1,1);
for(int i=0;i<len<<1;i++) a[i]=mul(a[i],b[i]);
NTT(a,len<<1,0);
for(int i=0;i<=d;i++)
{
int sum=(i&1)?mod-1:1;
sum=mul(sum,mul(qp(m-i,n-s*i),mul(fac[m],mul(inv[m-i],a[i]))));
sum=mul(sum,mul(fac[n],mul(inv[n-s*i],qp(inv[s],i))));
ans=add(ans,sum);
}
printf("%d\n",ans);
return 0;
}
2019.3.8