安徽网站建设案例,瓯海建设网站,亚当学院网站建设视频教程,东莞建站模板代理传送门:洛谷
解题思路:
写本题需要知道一个前置知识:
假设恰好选 k k k个条件的方案数为 f ( k ) f(k) f(k);先钦定选 k k k个条件,其他条件无所谓的方案数为 g ( k ) g(k) g(k) 那么存在这样的一个关系: g ( k ) ∑ i k n C i k f ( i ) g(k)\sum_{ik}^nC_{i}^kf(i) g(k)…传送门:洛谷
解题思路:
写本题需要知道一个前置知识:
假设恰好选 k k k个条件的方案数为 f ( k ) f(k) f(k);先钦定选 k k k个条件,其他条件无所谓的方案数为 g ( k ) g(k) g(k) 那么存在这样的一个关系: g ( k ) ∑ i k n C i k f ( i ) g(k)\sum_{ik}^nC_{i}^kf(i) g(k)∑iknCikf(i) 上述式子的含义是可以枚举实际上选了几个,然后再这 i i i个中选择 k k k个作为钦定的计算方案数.因为钦定这种方式是存在重复方案的 然后使用二项式反演可以实现钦定和恰好之间的转化. 经过二项式反演可以得到: f ( k ) ∑ i k n C i k ∗ ( − 1 ) i − k ∗ g ( i ) f(k)\sum_{ik}^nC_{i}^{k}*(-1)^{i-k}*g(i) f(k)∑iknCik∗(−1)i−k∗g(i).
对于本题来说,我们的 g ( i ) g(i) g(i)其实很容易写出.设 g ( i ) g(i) g(i)为恰好出现 i i i个的出现次数为 s s s的颜色的方案数.不难写出 g ( i ) C m i A n s ∗ i ( s ∗ i ) ! ∗ ( m − i ) n − s ∗ i g(i)C_m^i\frac{A_n^{s*i}}{(s*i)!}*(m-i)^{n-s*i} g(i)Cmi(s∗i)!Ans∗i∗(m−i)n−s∗i 然后我们反演一下就得到了: f ( k ) ∑ i k n C i k ( − 1 ) i − k g ( i ) f(k)\sum_{ik}^{n}C_{i}^{k}(-1)^{i-k}g(i) f(k)ik∑nCik(−1)i−kg(i) 稍微化解一下就能得到: f ( k ) ∗ k ! ∑ i k n g ( i ) ∗ i ! ∗ ( − 1 ) i − k ( i − k ) ! f(k)*k!\sum_{ik}^ng(i)*i!*\frac{(-1)^{i-k}}{(i-k)!} f(k)∗k!ik∑ng(i)∗i!∗(i−k)!(−1)i−k 然后我们设 G ( i ) g ( i ) ∗ i ! , H ( i ) ( − 1 ) i − k ( i − k ) ! G(i)g(i)*i!,H(i)\frac{(-1)^{i-k}}{(i-k)!} G(i)g(i)∗i!,H(i)(i−k)!(−1)i−k就能得到 F ( k ) ∑ i k n G ( i ) ∗ H ( i − k ) F(k)\sum_{ik}^nG(i)*H(i-k) F(k)ik∑nG(i)∗H(i−k) 我们使用经典套路将 G G G数组 r e v e r s e reverse reverse一下,就得到了 F ( K ) ∑ i k n G ( n − i ) ∗ H ( i − k ) F(K)\sum_{ik}^nG(n-i)*H(i-k) F(K)ik∑nG(n−i)∗H(i−k) PS:需要注意的是此时翻转的n可以不为n,不熟悉的人可能会搞不清楚 然后这是一道很显然的卷积式子.此时我们使用 N T T NTT NTT卷一下即可.此时我们的的 f ( k ) f(k) f(k)就是卷积完之后第 n − k n-k n−k项的系数. 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 10001000
#define int long long
const int mod1004535809;
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {int ans1;while(b) {if(b1) ansans*a%mod;b1;aa*a%mod;}return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {for(int i0;in;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int len1;len(n1);len1) {int gnqpow(inv1?3:qpow(3,mod-2),(mod-1)/(len1));for(int i0;in;i(len1)) {int g01;for(int j0;jlen-1;j) {int xa[ij],ya[ijlen]*g0%mod;a[ij](xy)%mod;a[ijlen]((x-y)%modmod)%mod;g0g0*gn%mod;}}}
}
int fac[maxn],in_fac[maxn];
void init(int limit) {fac[0]1;for(int i1;ilimit;i) {fac[i]fac[i-1]*i%mod;}in_fac[limit]qpow(fac[limit],mod-2);for(int ilimit-1;i0;i--) {in_fac[i]in_fac[i1]*(i1)%mod;}
}
int C(int a,int b) {return fac[a]*in_fac[b]%mod*in_fac[a-b]%mod;
}
int A(int a,int b) {return fac[a]*in_fac[a-b]%mod;
}
int w[maxn];int g[maxn];int G[maxn],H[maxn];int F[maxn];
signed main() {int nread();int mread();int sread();init(max(n,m));for(int i0;im;i) {w[i]read();}int kmin(m,n/s);for(int i0;ik;i) {g[i]C(m,i)*A(n,s*i)%mod*qpow(in_fac[s],i)%mod*qpow(m-i,n-s*i)%mod;}for(int i0;ik;i) {G[i]g[i]*fac[i]%mod;H[i]((i1?-1:1)*in_fac[i]%modmod)%mod;}reverse(G,Gk1);int limit1,len0;while(limitkk) limit1,len;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(len-1));NTT(G,limit,1);NTT(H,limit,1);for(int i0;ilimit;i) F[i]G[i]*H[i]%mod;NTT(F,limit,-1);int invqpow(limit,mod-2);for(int i0;ilimit;i) {F[i]F[i]*inv%mod;}int ans0;for(int i0;ik;i) {ans(ansF[k-i]*in_fac[i]%mod*w[i]%mod)%mod;}coutansendl;return 0;
}
