Luogu P1287 盒子与球 数学间接法

贴一个和其他题解不一样的做法 QWQ

题意：让我们求出 N 个球放入 R 个盒子且每个盒子都必须放球方案数。

首先，对于每一个球，可以将其放入的盒子数量共有 R 个，所以我们可以知道如果无需满足每个盒子都必须放球时的方案数共有 R^N 种方案数（球任意放，允许有空盒子）。

如果我们要满足题目给定的限制条件怎么办呢？

先定义 F[i] 为将 N 个球放入 i 个盒子且每个盒子都必须放球的方案数。

考虑要求每个 F[i]，我们只需要把球任意放且允许有空盒子的方案数减去有一个空盒子，有两个空盒子到有 i-1 个空盒子的方案数之和，并将每个减数项乘上其对应的组合数，即表示在 i 个盒子中选取 j (1<j<i) 个盒子空着的方案总数 C(i,j) 乘以在 j 个盒子里放 R 个球的方案数。（在高中组合数学中称为间接法）。

可以得到状态转移方程：

可以写出代码：

#include <bits/stdc++.h>
#define N 17
#define ll long long
using namespace std;
int n,r;
ll f[N],C[N][N];
ll quick_pow(ll a,ll b) //快速幂
{
    ll ret=1;
    while (b)
    {
        if (b&1) ret*=a;
        a*=a;
        b>>=1;
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&r);
    
    for (int i=0;i<=n;i++) C[0][i]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i;j++)
            C[j][i]=C[j-1][i-1]+C[j][i-1];
    //预处理组合数        
    for (int i=1;i<=n;i++)
    {
        f[i]=quick_pow(i,n); //计算 i^n
        for (int j=1;j<i;j++) f[i]-=C[j][i]*f[j]; //逐项减去
    }
    printf("%lld",f[r]);
    return 0;
}

时间复杂度 Θ(n^2)