Disjoint-Set-Union Sum (诈骗题)(区间DP, 位置顺序!!!!)

题目大意:

• 给出一个序列P , n 个点
• 每次可以选择2个 相邻区间进行合并, 会产生一个贡献值,当然合并n-1就合并完了, 问在所有的情况下, 贡献和是多少

 思路:

• 易错点:
• 这个所有情况, 你枚举的合并的那个先后顺序是有关系的!!!
• 因此直接去区间dp只能把各个合并的情况给弄出来,但是他的先后顺序是给定的!!!!
• 将合并2个区间的操作 转化成-> 点亮 i 和 i+1之间的边, 这样就转化为了组合数问题, 
• 考虑 l-r区间的值 会被贡献几次,  从整体上看, 选的点,他一定是比左右端点连着的2个边先选, 就利用组合数去做就彳于了

#include <bits/stdc++.h>
using namespace std;
#define ri int 
#define M 2000005

int n,m;
long long arr[M];
long long dp[M];
const int mod=998244353;
long long inv[M];
long long ksn(long long  a,int b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        b>>=1;a=a*a%mod;        
    }
    return ans;
}
long long C(int a,int b)
{
    if(a<b) return 0;
    if(b==0) return 1;
    if(a==b) return 1;
    
    return dp[a]*inv[a-b]%mod*inv[b]%mod;
}
int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    for(ri i=1;i<=n;i++)
    {
        cin>>arr[i];
        arr[i]+=arr[i-1];
        arr[i]%=mod;
    }
    dp[0]=1;
    for(ri i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]*i%mod;
        inv[i]=ksn(dp[i],mod-2);
    }
    long long ans=0;
    for(ri k=2;k<=n;k++)
    {
        for(ri i=1;(i+k-1)<=n;i++)
        {
            int j=i+k-1;
            int tmp=0;
            if(i>1) tmp++;
            if(j<n) tmp++;
            for(ri g=(j-i);g<=n-1-tmp;g++)
            {
            
                ans+=(arr[j]-arr[i-1]+mod)%mod*C(g-1,j-i-1)%mod*dp[j-i]%mod*dp[n-1-j+i-tmp]%mod*dp[tmp]%mod*C(n-1-tmp-g+1+tmp-1,tmp)%mod;
                ans%=mod;
            }
        
        
        }
    }
    
    cout<<ans;
    
    
    
    
}