Add or Multiply 1 题解(第二类斯特林数)

题目链接

题目思路

这个题目

首先一个算式肯定是加法和乘法交替的。对于每组连续的加法或者乘法，如果组内的元素是相同的，那么运算的结果也是一样的。假设分成了 (x)组加法和(y)组乘法，满足 (|x-y|leq 1)，那么加法和乘法的分组都是独立的。问题等价于将 (n)个有标号的球分到 (m) 个有标号的集合里面，使得每个集合都是非空的。这个问题可以用第二类斯特灵数简单解决。

然后直接枚举n分为了(i)组，那么m可能分为(i-1,i,i+1)组相乘即可

但是对于第(m)分为(i)组要乘以(2)

因为根据隔板法第一组可能为乘法或者加法

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug printf(" I am here
");
using namespace std;
#define S dp
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
mt19937 rnd(time(0));
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=3e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,m;
ll dp[maxn][maxn];
ll fac[maxn];
signed main(){
        for(int i=0;i<=3000;i++){
        if(i==0){
            fac[i]=1;
        }else{
            fac[i]=fac[i-1]*i%mod;
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=3000;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=(dp[i-1][j-1]+j*dp[i-1][j])%mod;
        }
    }
    for(int i=1;i<=3000;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i][j]*fac[j]%mod;
        }
    }
    int _;scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll temp=(dp[m][i-1]+2*dp[m][i]+dp[m][i+1])%mod;
            ans=(ans+temp*dp[n][i])%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}