题目解析

题意分析

这道题目要求计算$Frobozz$魔法锁的有效按钮组合序列总数。具体规则如下：

1. 按钮定义：

   • 锁具有$B$个按钮（$1 \leq B \leq 11$），标号为"1"到"$B$"

2. 组合规则：

   • 组合：同时按下$1$个或多个按钮
   • 序列：由若干个组合构成的有序集合
   • 每个序列至少包含$1$个组合
   • 每个按钮在序列中只能使用一次
   • 不必使用所有按钮

3. 示例说明：

   • 有效序列：$(1-2-3)(4)(7-8)$（包含$3$个组合，未使用按钮$5$和$6$）
   • 无效序列：$(1-2-3)(2-4)(5-6)$（按钮$2$被重复使用）

解题思路

1. 问题转化：

   • 将按钮视为集合元素
   • 有效序列对应于将集合划分为有序非空子集（即有序集合划分）

2. 数学推导：

   • 对于$B$个按钮，有效序列总数等于有序贝尔数（$Ordered Bell Number$）
   • 递推公式：$$a(B) = \sum_{k=1}^B \binom{B}{k} \cdot a(B-k)$$ 其中$a(0)=1$

3. 动态规划：

   • 使用动态规划预先计算所有可能$B$的有序贝尔数
   • 利用组合数性质优化计算

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define LL long long
#define N 105

int T,Case,n;
LL c[N][N],f[N][N],ans;

void clear()
{
    memset(f,0,sizeof(f));ans=0;
}
int main()
{
    scanf("%d",&T);
    for (int i=0;i<=11;++i) c[i][0]=1;
    for (int i=1;i<=11;++i)
        for (int j=1;j<=11;++j)
            c[i][j]=c[i-1][j]+c[i-1][j-1];

    while (T--)
    {
        clear();
        scanf("%d",&n);
        if (n>11)
        {
            printf("%d %d 0\n",++Case,n);
            continue;
        }
        for (int i=1;i<=n;++i) f[i][1]=1*c[n][i];
        for (int i=2;i<=n;++i)
            for (int j=2;j<=i;++j)
            {
                for (int k=1;k<=i;++k)
                    f[i][j]+=f[i-k][j-1]*c[n-i+k][k];
            }
        for (int i=1;i<=n;++i)
            for (int j=1;j<=i;++j)
                ans+=f[i][j];
        printf("%d %d %lld\n",++Case,n,ans);
    }
}