烷基计数

其实很早就想学一下这类问题了,不过因为各种原因鸽到现在...
links:
普通版 加强版 加强版的加强版

普通版

看大佬的博客学习了一下.
有一个很好懂的\(\mathjaxcal{O}(n^3)\)的\(dp\)方法.
设\(f-i\)表示大小为\(i\)的无标号树的组成方式.
儿子的子树大小为\(i-1\),假设有三个儿子大小为\(a,b,c\),\(0\leq a\leq b\leq c\leq i-1\).
分类讨论一下转移就可以了.因为无标号,所以不能简单的乘法原理.
1. \(a=b=c\),\(f-i+=\binom{f-a+3-1}{3}\)
2. \(a=b\), \(f-i+=\binom{f-a+2-1}{2}\times f-c\),\(b=c\)时也是同理.
3. \(a < b < c\), \(f-i+=f-a\times f-b \times f-c\).

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
int n, f[405];

inline int fpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) ans = ans * 1ll * a % MOD;
    return ans;
}
int inv2 = fpow(2, MOD - 2), inv6 = fpow(6, MOD - 2);
int C(int f, int d) {
    if (d == 2) {
        return (f + 1) * 1ll * f % MOD * inv2 % MOD;
    } else {
        return (f + 1) * 1ll * (f + 2) % MOD * 1ll * f % MOD * inv6 % MOD;
    }
}

int main() {
    scanf("%d", &n); f[0] = 1;
    for (int k = 1; k <= n; k++)
        for (int a = 0; a <= k; a++)
            for (int b = a; b <= k; b++) {
                int c = k - a - b - 1;
                if (c < b || b < a) break;
                if (a == b && b == c) f[k] = (f[k] * 1ll + C(f[a], 3)) % MOD;
                else if (a == b) f[k] = (f[k] * 1ll + (C(f[a], 2) % MOD * 1ll * f[c] % MOD)) % MOD;
                else if (b == c) f[k] = (f[k] * 1ll + (C(f[b], 2) % MOD * 1ll * f[a] % MOD)) % MOD;
                else f[k] = (f[k] * 1ll + f[a] * 1ll * f[b] % MOD * f[c] % MOD) % MOD;
            }
    printf("%d\n", f[n]);
    return 0;
}

加强版

因为\(n\leq 5000\),所以朴素的\(dp\)是过不了的.
考虑一下怎么优化.
普通的\(dp\)要去枚举所有子树的大小,那么有没有办法把大小一样的子树一起考虑,像树形\(dp\)一样去计算贡献.
设\(f[s][i][j]\)表示大小为\(i\)的树,根节点度数为\(j\),儿子的子树大小不超过\(s\)时的方案数.
考虑怎么转移, 假设大小为\(s\)的子树有\(k\)个.(\(k\times s<i\)且\(k\leq j\)).
这\(k\)个子树的形态的方案数是\(\binom{(\sum{f_{s-1,s,j}})+k-1}{k}\).
在乘上\(f_{s-1,i-s\times k,j-k}\)就是答案了.
用背包的方式来\(dp\),可以省去第一维空间.

石锤我不会写背包

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, MOD = 1e9 + 7;
ll f[N][4], n; // 1 -> 大小 2 -> 度数

inline ll fpow(ll a, ll b) {
    int ans = 1;
    for (; b; b >>= 1, a = a * a % MOD) if (b & 1) ans = ans * a % MOD;
    return ans;
}

ll inv2 = fpow(2, MOD - 2), inv6 = fpow(6, MOD - 2);

inline ll C(int now, int k) {
    if (k == 0) return 1;
    if (k == 1) return now % MOD;
    if (k == 2) return now * (now + 1ll) % MOD * inv2 % MOD;
    else return now * (now + 1ll) % MOD * (now + 2ll) % MOD * inv6 % MOD;
}

int main() {
    scanf("%lld", &n);
    f[1][0] = 1; ll now = 0;
    for (int s = 1; s <= n; s++) { // s -> 子树大小限制
        now = 0;
        for (int i = 0; i <= 3; i++) now = (now + f[s][i]) % MOD;
        if (n == s) break;
        // cout << now << endl;
        for (int i = n; i > 0; i--) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 1; k <= j && k * s < i; k++) {
                    f[i][j] = (f[i][j] + (f[i - s * k][j - k] * C(now, k) % MOD)) % MOD;
                }
            }
        }
    }
    printf("%lld\n", now);
    return 0;
}

加强版的加强版

...............
咕咕咕咕咕咕