1 条题解

  • 7
    @ 2021-12-27 11:17:37

    咋没人做啊(

    考虑从 nnn+1n+1 递推:

    4          o
               
    3       o  o
           /    
    2    o--o  o
        /      
    1 o--o--o  o
      1  2  3  4
    

    已知 (n,1)(n,1)(n,n)(n,n) 都连通,则只需要数 (n+1,1)(n+1,1)(n+1,n+1)(n+1,n+1) 有多少种方案连边。而由于每一个点只能从前面最多一个连边,我们可以枚举 1in1\le i\le n(n,1)(n,1)(n,i)(n,i)(n+1,1)(n+1,1)(n+1,i)(n+1,i)(n,i)(n,i)(n,n)(n,n)(n+1,i+1)(n+1,i+1)(n+1,n+1)(n+1,n+1)

    则答案为 1×2××n11\times 2\times\dots\times n-1,可以分段打表。

    信息

    ID
    55
    时间
    2000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    23
    已通过
    2
    上传者