hdu 7095 Add or Multiply 1 第二类Stirling数

本文主要是介绍hdu 7095 Add or Multiply 1 第二类Stirling数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://acm.hdu.edu.cn/showproblem.php?pid=7095
给出若干个加法和乘法的操作次数，问有多少个本质不同的操作序列

比如说如果有两个加法和一个乘法，那么得到的操作序列可以是下面的几种 $\text{\textcircled{1}}((x+a_1)+a_2)\times a_3\\\text{\textcircled{2}}((x+a_1)\times a_3)+a_2\\\text{\textcircled{3}}((x+a_2)+a_1)\times a_3\\\text{\textcircled{4}}((x+a_2)\times a_3)+a_2\\\text{\textcircled{5}}((x\times a_3)+a_1)+a_2\\\text{\textcircled{6}}((x\times a_3)+a_2)+a_1$
容易看出，在这些操作序列当中，本质不同的操作序列有 $1, 2, 4, 5$ 这样四种，当然可能有其他情况，但是种类的总数是固定的
如何看待这个问题呢？加法有 $n$ 个，乘法有 $m$ 个，那么就存在下面几种情况，

1. $++\times \times$
2. $\times \times ++$
3. $+\times +\times +$
4. $\times +\times +\times$

这里仅仅代表分组情况，前两种情况数量相同，那么现在需要枚举加法和乘法的分组数量，前两种情况分组数量相同，后两种情况分组数量相差为 $1$
利用第二类斯特林数也就是 $p$ 个元素划分到 $n$ 个不可区分盒子中且没有空盒子的方法数，枚举每一个分组数量，求和即可，但这里盒子与盒子之间是可区分的，所以还要乘上 $n$ 个元素的全排列 $A_n^n=n!$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 100;
const int INF = 0x3f3f3f3f;
int Data[MAXN];
ll Stirling2[3100][3100];
ll fac[3100];
const ll MOD = 1e9 + 7;
void init(){Stirling2[0][0] = 1;fac[0] = 1;for(int i=1;i<=3000;i++){for(int j=1;j<=i;j++){Stirling2[i][j] = Stirling2[i - 1][j - 1] + j * Stirling2[i - 1][j];if(Stirling2[i][j] >= MOD) Stirling2[i][j] %= MOD;}fac[i] = fac[i - 1] * i;if(fac[i] >= MOD) fac[i] %= MOD;}for(int i=1;i<=3000;i++){for(int j=1;j<=3000;j++){Stirling2[i][j] = Stirling2[i][j] * fac[j] % MOD;Stirling2[i][j] %= MOD;}}
}
int main(){#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifios::sync_with_stdio(false);int t, n, m;init();cin >> t;while(t--){cin >> n >> m;ll ans = 0;int tmp = min(n, m);for(int i=1;i<=tmp;i++){ans += 2 * Stirling2[n][i] * Stirling2[m][i] % MOD;ans %= MOD;}for(int i=1; i<=n && i+1 <= m; i++){ans += Stirling2[n][i] * Stirling2[m][i + 1] % MOD;ans %= MOD;}for(int i=1; i+1 <= n && i <= m; i++){ans += Stirling2[n][i + 1] * Stirling2[m][i] % MOD;ans %= MOD;}cout << ans << '\n';}return 0;
}