bzoj 5305 [Haoi2018]苹果树

bzoj 5305 [Haoi2018]苹果树

​​​​​ 考虑每条边对答案的贡献 设i节点的子树大小为sizei s i z e i 那么对于答案的贡献就是n∗(n−sizei) n ∗ ( n − s i z e i ) 发现如果不考虑生成树的顺序那么生成树的方案是节点的阶乘种方案 那么可以考虑枚举每个节点 然后再枚举他子树大小是多少来计算答案这样算出方案 然后再*对答案的贡献即可 那么子树的方案数自然就是sizei!∗Csizei−1n−i s i z e i ! ∗ C n − i s i z e i − 1 因为需要保证子树内的节点编号比i大 子树外生成方式自然是 首先生成i 有i!种方式 (i+1−2)×(i+2−2)×...(n−sizei+1−2) ( i + 1 − 2 ) × ( i + 2 − 2 ) × . . . ( n − s i z e i + 1 − 2 ) 相当于仍然用同样的方法考虑只不过这时不可以考虑i节点下放的放置方案 那么i!×(i+1−2)×(i+2−2)×...(n−sizei+1−2) i ! × ( i + 1 − 2 ) × ( i + 2 − 2 ) × . . . ( n − s i z e i + 1 − 2 ) 可以化简i×(i−1)×(n−sizei−1)! i × ( i − 1 ) × ( n − s i z e i − 1 ) ! 然后n2 n 2 计算即可

#include#include#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 N=2200;int c[N][N],n,mod,jc[N],ans;inline int inc(int &x,int v){return x+v>=mod?x+v-mod:x+v;}int main(){ freopen("bzoj5305.in","r",stdin); n=read();mod=read();jc[0]=1; for (int i=0;i<=n;++i) c[i][0]=1; for (int i=1;i<=n;++i) for (int j=1;j<=i;++j) c[i][j]=inc(c[i-1][j-1],c[i-1][j]); for (int i=1;i<=n;++i) jc[i]=(ll)jc[i-1]*i%mod; for (int i=2;i<=n;++i){ for (int sz=1;sz<=n-i+1;++sz){ ans=inc(ans,(ll)sz*(n-sz)*i*(i-1)%mod*c[n-i][sz-1]%mod*jc[sz]%mod*jc[n-sz-1]%mod); } }printf("%d\n",ans); return 0;}

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