游戏装备（equipment）题解

隐藏人物001 · 2021-08-27 19:51:07 · 个人记录

看似数论，实则排列组合dp

题目分析：

    首先观察题目，显然是需要我们推导一个做题的方法，首先尝试理解那些组合

和以前的组合是“本质相同的”，经过演算（建议自己来），我们发现当连续放入多

个相同种类的宝石时，显然只要这些宝石相同，顺序对结果是不会有影响的，而其

他的情况，都可能影响最后的结果。所以根据这一结论，我们就可以来找做法了！

    这里介绍cwj等dalao的方法：考虑将其中一种宝石分成多组，这些组之间不可

分开，之后分类讨论，将另外一种宝石分成与上对应的组数，这些组之间存在顺序

的区别，在算出两种分组后，根据乘法原理，就可以得出答案。

以上方法有很多的好处：

可以发现原先的问题变为了一些简（ju）单（nan）的子问题，可以通过循环实现，~~不太费脑子~~。
子问题显然是组合问题，组合问题除了可以用公式解决，也可以用思路清晰的动态规划解决，~~说白了还是不太费脑子~~。

那么子问题怎么解决呢？
```
 我们先简化这个问题，因为顺序是无关的，所以可以简化为“装盒问题”，每
```
个宝石都是不同的球，将所有的球装进盒子里，我们设f（i，j）表示将i个球装

进j个盒子里的方案数，易知f(1,1)=1,新加入一个球，既可以把它放入原先的某个

盒子里，那么就有f（i-1，j）*j个方案，或者新增一个盒子，那么又有f（i-1，j-1）

个方案，得到转移方程：f(i,j)=f(i-1,j)*j+f(i-1,j-1);

至于如何利用这个子问题完成接下来的子问题，我们需要回顾一下刚才我们想的方法。

如何利用以上组合数
```
  枚举其中一种宝石被分成几组，另一种宝石也分成几组插入其中，为了避免重
```
复，一定要将中间的i-1个空隙插满，所以有4种情况。
- 仅插满中间i-1个空隙。
- 插满中间i-1个空隙和左边开头的空隙。
- 插满中间i-1个空隙和右边结尾的空隙。
- ~~管他妈的全插满~~。
```
可以发现，譬如第一种情况，其的方案为一种宝石分为i组的情况乘i的阶乘（因为
```
  盒子的顺序是可以调换的），再乘上另一种宝石分为i-1组再乘上（i-1）的阶乘。
  
  另外几种同理，而且2,3两种可以连起来考虑。
  
  这样我们就将他完成了!!!
  
  代码实现：
  
  先用组合dp打表，再枚举分为几组（细节自己研究），根据以上方法计算方案
  
  注意每次都有取模，乘法和加法都可能爆long long。
  
  具体代码：
```
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,i,j,t;
long long s[3010][3010],s1[3010],ans,MOD=1e9+7;
int main()
{
s[0][1]=1;
s1[0]=1;
for (i=1;i<=3001;i++) s1[i]=(s1[i-1]*i)%MOD;
for (i=1;i<=3001;i++)
for (j=1;j<=i;j++)
s[i][j]=(s[i-1][j]*j%MOD+s[i-1][j-1])%MOD;
scanf("%d",&t);
for (;t>=1;t--)
{
scanf("%d%d",&n,&m);
ans=0;
for (i=1;i<=min(n,m);i++)
ans=(ans+1ll*s[n][i]*s[m][i]%MOD*s1[i]%MOD*s1[i]%MOD*2%MOD)%MOD;
for (i=1;i<=min(n,m-1);i++)
ans=(ans+1ll*s[n][i]*s[m][i+1]%MOD*s1[i]%MOD*s1[i+1]%MOD)%MOD;
for (i=2;i<=min(n,m+1);i++)
ans=(ans+1ll*s[n][i]*s[m][i-1]%MOD*s1[i]%MOD*s1[i-1]%MOD)%MOD;
printf("%lld\n",ans);
}
return 0;
}
```
  最后吐槽一下：~~这个游戏就没有自动配最强战力的快捷方式吗qaq~~

游戏装备（equipment）题解

看似数论，实则排列组合dp

题目分析：

那么子问题怎么解决呢？

如何利用以上组合数

这样我们就将他完成了!!!

代码实现：

具体代码：