BZOJ5305 [Haoi2018]苹果树

BZOJ5305 [Haoi2018]苹果树

大家好,又见面了,我是你们的朋友全栈君。

可以发现一个\(n\)节点的树的方案数是\(n!\)

因为对于第\(i\)个点有\(i\)种选择方式 可以归纳证明 第\(i\)个点选择一个位置之后又新加入了他的左右子树 即可选择位置变为\(i+1\)

那么我们对于一个点\(i\)枚举它的子树大小\(j\) 统计要经过他和父亲的连边的点对数

它的子树的方案数即为\(j!*C_{n-i}^{j-1}\)

子树外首先要先构造出大小为\(i\)的子树 方案数\(i!\)

之后我们再在外面这棵树上添加新节点 容易发现点\(i\)的子树不能再填充 相当于少了\(2\)个填充位置 于是对于剩下的\(n-i-j+1\)个点的方案数即为\(\sum_{k=1}^{n-i-j+1}(k+i-2)\)

当然对于每一种方案它的点对数都是\(j*(n-j)\)

将以上各式相乘并化简即得\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n-i+1}(j! * (n-j)! * \binom{n-i}{j-1} * i * (i-1) * j)\)

#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=2e3+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}
int n,mod,ans,fac[N],C[N][N];
void init(){
    fac[0]=fac[1]=1;
    for(int i=2;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}
int calc(int a,int b){
    return (ll)a*(a-1)*b%mod;
}
int main(){
#ifdef Devil_Gary
    freopen("in.txt","r",stdin);
#endif
    n=read(),mod=read(),init();
    for(int i=2;i<=n;i++) for(int j=n-i+1;j;--j) (ans+=(ll)fac[j]*fac[n-j]%mod*C[n-i][j-1]%mod*calc(i,j)%mod)%=mod;//,bug(ans); 
    printf("%d\n",ans);
}

转载于:https://www.cnblogs.com/devil-gary/p/9067329.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107501.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 如何优雅地打印Java数组?「建议收藏」

    如何优雅地打印Java数组?「建议收藏」在逛StackOverflow的时候,发现了一些访问量像‎安第斯山一样高的问题,比如说这个:打印Java数组最优雅的方式是什么?访问量足足有220W+,想不到啊,这么简单的问题竟然有这么多程序员被困扰过。来回顾一下提问者的问题吧:在Java中,数组虽然是一个对象,但并未明确的定义这样一个类,因此也就没有覆盖toString()方法的机会。如果尝试直接打印数组的话,输出的结…

  • dsp定时器初始化程序C语言,C语言定时器实验

    dsp定时器初始化程序C语言,C语言定时器实验C语言定时器实验实验三C语言定时器实验一、实验目的1.进一步熟悉DSP的中断机制2.在掌握中断服务程序编写的基础上进一步熟悉定时器的运用3.进一步掌握如何编写DSP中断服务子程序二、实验设备1.具有USB接口的PC机一台2.USB仿真器一台3.ARM/DSP/FPGA实验箱一台三、实验原理本实验是在我们基本上掌握DSP中断机制的基础上,进一步学习如何在DSP内部实现定时器的正确操作以及定时器中…

  • 自动化运维平台功能大纲

    自动化运维平台功能大纲

  • Android NDK开发:打包so库及jar包供他人使用

    Android NDK开发:打包so库及jar包供他人使用Android的NDK开发相信各位已经精通各种姿势了。不过基本上都是那种native代码和java代码都在同一个工程中,因为应用从头到脚都是我们自己的,也不需要分离。但有时候可能需要我们自己把某些库打包起来供别人使用,或者使用别人提供给我们的库。本篇文章及下篇文章就讲讲so库如何打包。一、目标及方式这篇文章会讲第一种方式来打包so库,这种方式是基于jni层的,需要我们同时提供接口的jar包…

  • java中解析json格式数据

    今天在项目中需要接收json格式数据进行数据库保存,长时间没有使用json格式的数据,今天突然用到还有写棘手,现在我来写一下在java中解析json格式数据的代码publicvoidsaveData(){jsonData= {“TSR_TOTAL”:1,”TSR_ITEMS”:[{“UDID”:”1″,”major”:”a”,”minor”:”1″}{“UDID”:”2″,”majo

  • C# 开发上位机软件[通俗易懂]

    C# 开发上位机软件[通俗易懂]目前正进行上位机软件开发,有兴趣的朋友,可以一起参与,联系qq-19066432

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号