bzoj5306 [HAOI2018]染色

bzoj5306 [HAOI2018]染色

​​ 题目背景 HAOI2018 Round2 第二题

题目描述 为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可 以抽象为一个长度为

N

N 的序列, 每个位置都可以被染成

M

M 种颜色中的某一种.

然而小 C 只关心序列的

N

N 个位置中出现次数恰好为

S

S 的颜色种数, 如果恰 好出现了

S

S 次的颜色有

K

K 种, 则小 C 会产生

W_k

Wk 的愉悦度.

小 C 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对

1004535809

1004535809 取模的结果是多少.

输入输出格式 输入格式：

从标准输入读入数据. 第一行三个整数

N, M, S

N,M,S .

接下来一行

M + 1

M+1 个整数, 第

i i 个数表示

Wi−1Wi−1

输出格式：

输出到标准输出中. 输出一个整数表示答案．

输入输出样例 输入样例#1： 复制

8 8 3 3999 8477 9694 8454 3308 8961 3018 2255 4910 输出样例#1： 复制

524070430 输入样例#2： 复制

见 ​​ 输出样例#2： 复制

231524284 说明 特殊性质:

∀1≤i≤m,Wi=0 ∀ 1 ≤ i ≤ m , W i = 0

对于 100% 100 %

0≤Wi<1004535809 0 ≤ W i < 1004535809

设lim=min(m,n/s)即 最多放多少个S长度的颜色 假设现在有k个s长度的颜色尝试求方案数 Ckm×(Csm×Csm−s...)×(m−k)n−ks C m k × ( C m s × C m − s s . . . ) × ( m − k ) n − k s 可以发现这样会有重复的计算 那么不妨分成两段来计算 设g[m][n]表示不包含k种颜色中的颜色的随意组合且不会再出现s长度这种情况的方案数 那么我们可以把后面这段来容斥计算 带入 ∑i=0limm!(m−i)!×i!n!(s!)i(n−s)!∑j=0m−i(−1)j(m−i)!(m−i−j)!j!×(n−is)!(s!)j(n−js−is)!×(m−i−j)n−js−is ∑ i = 0 l i m m ! ( m − i ) ! × i ! n ! ( s ! ) i ( n − s ) ! ∑ j = 0 m − i ( − 1 ) j ( m − i ) ! ( m − i − j ) ! j ! × ( n − i s ) ! ( s ! ) j ( n − j s − i s ) ! × ( m − i − j ) n − j s − i s 考虑i和lim互换是并不影响什么的所以我们将i看成lim-i此外 将j替换为j-i ∑i=0limm!(m−i)!i!n!(s!)i(n−s)!∑j=ilim(−1)j−i(m−i)!(m−j)!(j−i)!×(n−is)!(s!)j−i(n−js−is)!(m−j)n−is ∑ i = 0 l i m m ! ( m − i ) ! i ! n ! ( s ! ) i ( n − s ) ! ∑ j = i l i m ( − 1 ) j − i ( m − i ) ! ( m − j ) ! ( j − i ) ! × ( n − i s ) ! ( s ! ) j − i ( n − j s − i s ) ! ( m − j ) n − i s 考虑构造卷积形式 m!n!∑j=1lim(m−j)n−js(m−j)!(s!)j(n−js)!∑i=0jwii!(−1)j−i(j−i)! m ! n ! ∑ j = 1 l i m ( m − j ) n − j s ( m − j ) ! ( s ! ) j ( n − j s ) ! ∑ i = 0 j w i i ! ( − 1 ) j − i ( j − i ) !

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int g=3;const int N=1e5+10;const int mod=1004535809;inline int ksm(ll b,int t){static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;}inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}int n,m,s,S,jc[N*100],inv[N*100],nn,a[N<<2],b[N<<2],R[N<<2],ans,w[N];inline void ntt(int *x,int f){ for (int i=0;i>1]>>1)|((i&1)<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。