M_sea

洛谷4492 [HAOI2018]苹果树
LuoguBZOJ分析考虑每条边的贡献,显然为 $size\times (n-size)$ 。假设一个点 $u$...
扫描右侧二维码阅读全文
12
2019/03

洛谷4492 [HAOI2018]苹果树

Luogu

BZOJ

分析

考虑每条边的贡献,显然为 $size\times (n-size)$ 。

假设一个点 $u$ 有一颗大小为 $k$ 的子树,考虑方案数。

首先,要从 $n-u$ 个点中选出 $k$ 个点作为该子树,方案数是 $C_{n-u}^k$ ,子树的方案数是 $K!$ 。

然后还剩下 $n-u-k$ 个点,考虑这些节点随便放的方案数。

首先把选出来的 $k$ 个点拿出来,按顺序考虑剩下的点。显然,第 $n-u-k$ 个的方案数是 $u+n-u-k-1$ ,那么总的方案数就是 $\frac{(n-k-1)!}{(i-1)!}$ 。
于是总的答案就是 $\large\sum\limits_{i=1}^ni!\times2\sum\limits_{j=1}^{n-i}j\cdot(n-j)\cdot C_{n-i}^j\cdot j!\cdot\frac{(n-j-1)!}{(i-1)!}$ 。

因为这里有个除,然后可能不存在逆元,于是稍微变形一下,得到 $\large\sum\limits_{i=1}^n\sum\limits_{j=1}^{n-i}2\cdot i!\cdot j\cdot(n-j)\cdot C_{n-i}^j\cdot j!\cdot C_{n-j-1}^{i-1}\cdot(n-j-i)!$ 。

时间复杂度 $O(n^2)$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int n,mod,ans=0;
int C[N][N],fac[N];

int main() {
    n=read(),mod=read();
    C[0][0]=fac[0]=1;
    for (re int i=1;i<=n;++i) {
        C[i][0]=1;
        for (re int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n-i;++j)
            ans=(ans+2ll*fac[i]*j%mod*(n-j)%mod*C[n-i][j]%mod*fac[j]%mod*C[n-j-1][i-1]%mod*fac[n-j-i]%mod)%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 07 月 13 日 10 : 15 PM

发表评论