YOJ1 二人从空中落下

暂时没时间放上YOJ，先寄存在luogu上

几乎全原创的一道题，感受到了出题的艰难。。。

欢迎各位帮忙验题！

题意:

现有n个无区别的点，他们可能随机连边成为一棵特殊的树

这种树满足它的每个非叶子节点都有且只有两个儿子

现给出a和b

问这些点所生成的所有特殊的树，能满足高度$\in\left [ a,b \right ]$的概率是多少（约定单个节点高度为1）

对998244353取模

题解：

灵感来源于P1472奶牛家谱

一道简短的dp，暴力给了30

SUB1：

a与b正好卡满所有可能情况，100%能安全降落

输出1即可

SUB2：

从1到(n+1)/2枚举降落点进行爆搜

给出暴力的大致代码：


int dfs(int cnt, int height){
    if (cnt == 1) return height == 1;
    if (height > (cnt + 1) / 2) return 0;
    if (height <= 1) return 0;
    int state=0;
    for (int i(1); i < cnt; i += 2){
        for (int j(1); j < height; ++j){
            state += dfs(i, height - 1) * dfs(cnt - i - 1, j);
            state %= MOD;
            if (height - 1 != j){
                state += dfs(i, height - 1) * dfs(cnt - i - 1, j);
                state %= MOD;
            }
        }
    }
    return state;
}
signed main(){
    scanf("%lld%lld%lld", &n, &a,&b);
    m=n+1>>1;
     if(a>m){
         puts("0");
         return 0;
     }
     if(a==ceil(log2(n+1))&&b==m){
         puts("1");
         return 0;
     }
     b=min(b,m);
    for(int i=1;i<=m;i++) s[i]=s[i-1]+dfs(n,i);
    cout<<(((s[b]-s[a-1])%mod+mod)%mod)*fpow(s[m],mod-2,mod)%mod;
    return 0;
}

SUB3：

给想出标程但没处理b导致RE的人

SUB4：

给想出标程但没有差分答案的人

标算：

令m=(n+1)/2

画图易知m是n个点的最大合法深度

设f[i][j]表示i个点深度小于等于j的树有几种

初始f[1][]=1

转移$O(n^2*m)$

三层循环分别枚举深度，枚举总点数，枚举左子树分配点数

$f[i][k]=sum{f[j][k-1]*f[i-j-1][k-1]}$

若j为左子树点数则i-j-1为右子树点数

乘法原理，两者相乘

答案的分子部分显然可以由f[n][b]-f[n][a-1]差分得到

而分母部分就是f[n][m]

要注意的是，有些点a,b很大，需要特判：

若a>m则输出0，因为一种都不满足

否则若b>m则需要先将b取min改为m再继续做，以防止RE爆下标，因为>m的部分都一定是不满足的

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=1005,mod=998244353;
int n,m,f[N][605],a,b;

int fpow(int x,int y,int mod){
    int res=1;
    for(;y;y>>=1,mod?(x*=x)%=mod:x*=x) if(y&1) mod?(res*=x)%=mod:res*=x;
    return res;
}

signed main(){
    read(n);read(a);read(b);
    m=(n+1)>>1;
    if(a>m){ //对a特判
        puts("0");
        return 0;
    }
    b=min(b,m); //对b特判
    for(int i=1;i<=m;i++) f[1][i]=1; //初始
    for(int k=1;k<=m;k++) //枚举深度
        for(int i=3;i<=n;i+=2) //枚举总点数
            for(int j=1;j<i;j+=2) //枚举左子树分配点数
                (f[i][k]+=f[j][k-1]*f[i-j-1][k-1]%mod)%=mod; //累加
    write((((f[n][b]-f[n][a-1])%mod+mod)%mod)*fpow(f[n][m],mod-2,mod)%mod); //差分得答案
}
赏

fighter