百度之星2021 复赛1002题 (第二类斯特林数)

發表於 更新於 分類於 Disqus： 文章字數： 637 所需閱讀時間 ≈ 2 分鐘
第二类斯特林数

痛失1002只过了1001签到题

虽然凭空推出过一些定理，但多数定理还是难以凭空推出的 QAQ

https://acm.hdu.edu.cn/showproblem.php?pid=7095

题意

1e4组测试

每组测试给定(n,m <= 3k)

一个x，n个加法$+a_1,+a_2,…,+a_n$, $ \cdot b_1,\cdot b_2,\cdot b_m$，m个乘法

任意排列它们，计算从左向右，无优先级

如果 任意变量，两个表达式值都相同，那么两个表达式本质相同

求本质不同的方案数

例子

如2加1乘(注意无优先级从左向右算)

$x+a_1 + a_2 \cdot b_1 $

$x+a_1 \cdot b_1 + a_2 $

$x+a_2 \cdot b_1 + a_1 $

$x \cdot b_1 +a_1 + a_2 $

一共4种

思路

a和b间隔，

那么他们数量差不大于1

对于a分为k组，方案数

$f(a,k) * (f(b,k-1)+2f(b,k)+f(b,k+1))$

如果能线性算出 $f(a,b)$ 那么就能在时间内算出

问题变成了，把n个数拆分成k个非空集合的方案数如何算

这就是我卡住尝试自己想，但未想出方案(oi wiki都还没人加上这个)

第二类斯特林数

S(n,m) 表示把n个不同的小球放在m个相同的盒子里（且每个盒子至少一个）方案数

第一个球 单独在一个盒子里 S(n,m)+=S(n-1,m-1)

第一个球不单独放，那就是剩余放完以后，其中一个盒子中再放入1，对于所有剩余放完后，都有m种选法S(n,m)+=mS(n-1,m)

所以

S(n,m) = S(n-1,m-1) + mS(n-1,m)

这样我们可以直接初始化完整个S

回到原题

因为 原题还是有序

上面的S是无序的，所以 每次 S(n,m) 乘上 n! 就行

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);


ll S[3010][3010];
ll pwr[3010];


ll f(ll a,ll b){
    return (pwr[b]*S[a][b])%MOD;
}

void work(){
    int n,m;
    scanf("%d %d",&n,&m);
    if(n>m)swap(n,m);
    ll ans = 0;
    rep(k,1,n+1){
        (ans+= f(n,k) * (f(m,k-1) + 2*f(m,k)+f(m,k+1)))%=MOD;

    }
    printf("%lld\n",ans);
}


int main(){
    S[1][1] = 1;
    rep(i,2,3001){
        rep(j,1,i+1){
            (S[i][j] = S[i-1][j-1] + j * S[i-1][j])%=MOD;
        }
    }
    pwr[0]=1;
    rep(i,1,3001){
        pwr[i] = (pwr[i-1]*i)%MOD;
    }

    int t;
    cin>>t;
    while(t--){
        work();
    }
  return 0;
}